使用Java使用“n choose k”的字符串字母组合

Question

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();
            }
        }

以下是在上面的代码中创建的内容的输出：

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的所有可能组合的字符串使用包含在上一个输出中显示的数组列表中的字母字符串。

Answer 1

这里有一个小方法，它返回长度为k的所有字母组合的列表（顺序不重要），给定长度为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个字母的字符串，那么转换应该很容易。

我不知道这个递归实现是否有效，但它很好地反映了帕斯卡三角形的数学性质:(n choose k)=(n-1 choose k-1)+(n-1 choose k)