使用“N 选择 K"的字符串字母组合使用Java [英] String Letter Combinations Using "N choose K" using Java
问题描述
所以我遇到了一个问题，我有一个 ArrayList，其中 List 由一个字母字符串组成.在这种情况下 (A,B,C,D,F,J,N) 列表的大小为 7.
So I have run into a problem where I have an ArrayList where the List is comprised of one letter strings. In this case (A,B,C,D,F,J,N) where the size of the list is 7.
现在我正在尝试编写代码，使所有字母组合可以在顺序无关紧要的情况下进行，即(我知道这将涉及n 选择 k")长达 5 个字母.
Now I am trying to write code making all combinations of lettering that can be made where the order does not matter i.e. (I know it will be involving "n choose k") up to 5 letters long.
所以对于 7 选择 1 将是 A、B、C、D、F、J、N... 7 选择 2 ... 等等.... 7 选择 3 ... 等等....等
So for 7 choose 1 will be A,B,C,D,F,J,N ... 7 choose 2 ... etc. ... 7 choose 3 ... etc. ... etc.
然后我希望将这些字符串组合存储到另一个列表/哈希图中(尚未决定).
I am then looking to store these string combinations into another list/hashmap (haven't decided on yet).
但我主要关注的是生成此类字符串的代码.如果有人可以提供帮助，将不胜感激.我还想让它模块化，以防万一我想最终形成 6,7 长度的其他组合.(这就是为什么我不只是使用 5 个循环并针对不同的索引递增).
But my main focus is on the code that would generate such strings. If anyone can help that would be greatly appreciated. I also want to make it modular just in case i want to eventually form other combinations of 6,7 length. (Which is why I am not just doing it with 5 loops and incrementing for different indices).
到目前为止我所拥有的......
What I have so far...
public class ReadFile {
public static void main(String[] args) throws IOException {
String file_name = "C:/Users/Shane/Documents/College/Classes/PurchaseTable.txt";
extract(file_name, 50);
}
private String path;
public ReadFile(String file_path) {
path= file_path;
}
public String[] OpenFile() throws IOException {
FileReader fr = new FileReader(path);
BufferedReader textReader = new BufferedReader(fr);
int numberOfLines = readLines();
String[] textData = new String[numberOfLines];
int i;
for(i=0; i < numberOfLines; i++) {
textData[i] = textReader.readLine();
}
textReader.close();
return textData;
}
int readLines() throws IOException {
FileReader file_to_read = new FileReader(path);
BufferedReader bf = new BufferedReader(file_to_read);
String aLine;
int numberOfLines = 0;
while(( aLine = bf.readLine()) != null) {
numberOfLines++;
}
bf.close();
return numberOfLines;
}
public static void extract(String filename, int threshold) {
String file_name = filename;
ArrayList<String> temp = new ArrayList<String>();
ArrayList<String> products = new ArrayList<String>();
HashMap<Integer, String> productsPerDate = new HashMap<Integer, String>();
//HashMap<Integer, String> allCombinations = new HashMap<Integer, String>();
try {
ReadFile file = new ReadFile(file_name);
String[] aryLines = file.OpenFile();
int i;
for (i=1; i < aryLines.length; i++) { //excludes header section of any table as shown in assignment
temp.add(aryLines[i]);
}
}
catch (IOException e) {
System.out.println( e.getMessage() );
}
System.out.println(temp);
System.out.println(temp.get(0));
System.out.println(temp.size());
int i; int j; int l;
for (i=0; i<temp.size(); i++) {
String str = temp.get(i);
StringBuilder sb = new StringBuilder(str);
int k =0;
for (j=0; j<=sb.length(); j++) {
if(sb.charAt(j) == '\"' && k==0) {
sb.delete(0, j+1);
k++;
}
if(sb.charAt(j) == '\"' && k!=0) {
sb.delete(j, sb.length());
String line = null;
System.out.println(sb);
for( l=0; l<sb.length(); l++) {
String string = Character.toString(sb.charAt(l));
if(string.equals(",")) {
}
else if (l ==0) {
products.add(string);
line = string;
}
else {
products.add(string);
line = line + string;
}
}
productsPerDate.put(i, line);
//System.out.println(products);
break;
}
}
}
System.out.println(products);
System.out.println(productsPerDate.entrySet()); //Hashmap set to string of 1 letter characters for products per date
Set<String> removeDup = new HashSet<>();
removeDup.addAll(products);
products.clear();
products.addAll(removeDup);
System.out.println(products);
int maxLength = productsPerDate.get(0).length();
for(int m = 0; m < productsPerDate.size(); m++) { //determine max length of string in hashmap
if(maxLength < productsPerDate.get(m).length()) {
maxLength = productsPerDate.get(m).length();
}
}
这可能不是执行此操作的最有效方法，但请耐心等待并以任何方式提供帮助.
This probably isn't the most efficient way to do this but please bear with me and help in any way you can.
输出显示在上面代码中创建的内容:
The output is shown below of what has been created in the above code:
1,"A,B,C,N",1/3/2013
4
A,B,C,N
B,C,D,A,F
A,C,V,N,J
A,C,J,D
[A, B, C, N, B, C, D, A, F, A, C, V, N, J, A, C, J, D]
[0=ABCN, 1=BCDAF, 2=ACVNJ, 3=ACJD]
[A, B, C, D, F, V, J, N]
所以本质上，我正在尝试编写代码，使用最后输出中显示的数组列表中包含的字母字符串来制作长度为 5 的字符串的所有可能组合.
So essentially I am trying to write the code to make all the possible combinations of length 5 string using the letter strings contained in the array list shown in last output.
推荐答案
这里有一个小方法，它返回长度为 k 的所有字母组合的列表(顺序无关紧要)，给定长度为 n 的输入字符串:
Here is a little method that returns a list of all letter combinations of length k (order doesn't matter), given an input String of length n:
public static ArrayList<String> combinations(String nChars, int k) {
int n = nChars.length();
ArrayList<String> combos = new ArrayList<String>();
if (k == 0) {
combos.add("");
return combos;
}
if (n < k || n == 0)
return combos;
String last = nChars.substring(n-1);
combos.addAll(combinations(nChars.substring(0, n-1), k));
for (String subCombo : combinations(nChars.substring(0, n-1), k-1))
combos.add(subCombo + last);
return combos;
}
public static void main(String[] args) {
String nChars = "ABCDE";
System.out.println(combinations(nChars, 2));
}
output: [AB, AC, BC, AD, BD, CD, AE, BE, CE, DE]
我使用字符串作为输入和输出，因为它们是不可变的，并且在切片方面比列表表现得更好.但如果您的列表只包含 1 个字母的字符串，则应该很容易转换.
I used Strings as input and output, since they are immutable and more well-behaved with regard to slicing than Lists. But if your List contains only 1-letter Strings, it should be easy to convert.
我不知道这个递归实现是否高效，但它很好地反映了帕斯卡三角形的数学特性:(n choose k) = (n-1 choose k-1) + (n-1选择k)
I don't know if this recursive implementation is performant, but it reflects nicely the mathematical property of the Pascal triangle: (n choose k) = (n-1 choose k-1) + (n-1 choose k)
这篇关于使用“N 选择 K"的字符串字母组合使用Java的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
