使用 "N choose K" 使用 Java 的字符串字母组合

Question

所以我运行遇到了一个问题，我有一个 ArrayList，其中 List 由一个字母字符串组成。在这种情况下 (A,B,C,D,F,J,N)，列表的大小为 7。

现在我正在尝试编写代码，使所有字母组合都可以在顺序无关紧要的情况下进行，即（我知道它将涉及 "n choose k"）最多 5 个字母。

所以对于 7，选择 1 将是 A、B、C、D、F、J、N ... 7 选择 2 ... 等等。 ... 7 选择 3 ... 等等。 ...等等

然后我想将这些字符串组合存储到另一个 list/hashmap（尚未决定）。

但我主要关注的是生成此类字符串的代码。如果有人可以提供帮助，将不胜感激。我还想让它模块化，以防万一我想最终形成 6,7 长度的其他组合。（这就是为什么我不只是用 5 个循环并为不同的索引递增）。

到目前为止我有什么...

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

这里有一个小方法，给定一个长度为 n 的输入字符串，returns 一个长度为 k 的所有字母组合的列表（顺序无关紧要）：

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]

我使用字符串作为输入和输出，因为它们是不可变的，并且在切片方面比列表表现得更好。但是如果你的List只包含1个字母的字符串，应该很容易转换。

我不知道这个递归实现是否高效，但它很好地反映了 Pascal 三角形的数学属性：(n choose k) = (n-1 choose k-1) + (n-1 choose k)

Answer 2

蛮力，无递归，泛型，未优化，说教。

如果你想要安排而不是组合，只需评论一行。

// COMBINAISONS
/**
 * Return combinaisons of input
 * @param _input 
 * @param _n how many to pick
 * @return
 */
public static <T> Vector<Vector<T>> combinaisons (Vector<T> _input, int _n)
{
Vector<Vector<T>> output=new Vector<Vector<T>> ();

int size=_input.size();

// Current result
Object current[]=new Object[_n];
Arrays.fill(current,"");

// which element we take at each box  (between 0 and size-1)
int current_indices[]=new int[_n];
Arrays.fill(current_indices,-1);

// inputs used
boolean used[]=new boolean [size];
Arrays.fill(used, false);

// Which box are we processing
int current_box=0;

// Next value for next position
int next_pos_value=0;

// ALGORITHM

while (true)
{
// Finished ?
if (current_box<0)
    break;

// Last element ? 
if (current_box>=_n)
    {
    // => save group
    output.add(new Vector<T>((List<T>) Arrays.asList(current)));

    current_box--;
    continue;
    }

// filling Current box > 0 && < _n

// next value available
int last_value=current_indices[current_box];
int next_value=-1;

// Where do we begin
int begin_test=0;
if (last_value>=0)
    begin_test=last_value+1;

// bigger
// comment this for arrangement rather than combinaisons
if (begin_test<next_pos_value) begin_test=next_pos_value;

for (int test_value=begin_test; test_value < size; test_value++)
        if (!used[test_value])
            {
            next_value=test_value;
            break;
            }

// VALUE AVAILABLE
if (next_value!=-1)
    // valid value ?
    {
    // release
    if (last_value!=-1)
        used[last_value]=false;

        used[next_value]=true;
        current_indices[current_box]=next_value;
        current[current_box]=_input.get(next_value);

        // next position
        current_box++;

        // like arrangements, but next value always more
        next_pos_value=next_value+1;

        continue;
    }       

else
    // invalid value (too big) ?
    {
    // release
    if (last_value!=-1)
    used[last_value]=false;
    current_indices[current_box]=-1;

    // back position
    current_box--;

    // like arrangements, but reset this
    next_pos_value=-1;

    continue;
    }       
}

return output;
}
//  public static Vector<Vector<T>> combinaisons (Vector<T> _input)

使用 "N choose K" 使用 Java 的字符串字母组合

String Letter Combinations Using "N choose K" using Java

java

math

probability

arraylist

discrete-mathematics