迭代地找到字符数组k的所有组合(N选择K)

Question

我目前正在将这个问题作为一个个人项目来处理.

基本上:

• 给定一系列元素,例如E = {1,2,a,b}和
• 给定数字K,例如K = 2
• 我想要返回大小为K的E的所有组合(E选择K)
• 例如{{1,1},{1,2},{1,a},{1,b},{2,1},...,{b,1},{b,2},{b ,a},{b,b}}

我已经使用以下函数递归地实现了这个:

char[] pool = new char[]{'1', '2', '3'};

public void buildStringRec(char[] root, int pos, int length){
    for(char c : pool){
        char[] newRoot = root.clone();
        newRoot[pos] = c;
        if(pos+1 < length){
            buildStringRec(newRoot, pos+1, length);
        } else{
            System.out.println(String.valueOf(root));
        }
    }
}

poolE和lengthK 在哪里？

所以我们打电话给:buildStringRec(new char[2], 0, 2);得到

11
12
13
21
22
23
31
32
33

这可以迭代完成吗？我一直试图围绕如何使用可变长度来做这件事.

任何帮助,将不胜感激!如果需要,我可以按照原样发布我的代码,但由于我的重试,它发生频率变化,我发布它几乎没用.

另外,我不想使用Apache或String Builder这样做,因为我想了解如何做到这一点的概念.我不是简单地要求代码.只要清楚地解释,伪代码就可以了.

谢谢!

编辑

我正在使用这个网站测试提供给我的所有选项:https:
//ideone.com/k1WIa6随意分叉并尝试一下!

Answer 1

这是另一个迭代解决方案：

您可以创建一个大小为 K 的整数数组来充当计数器，记录您完成组合的程度，并创建一个 char 数组来存储当前组合。

打印完每个组合后，通过增加其中一个计数器值来继续进行下一个组合，如果它通过达到等于 E 中元素数量的值而“溢出”，则将其重置为零并通过增加计数器值来执行进位计数器在下一个位置，检查那里是否有溢出等等。有点像汽车中的里程表，只不过数字与 E 中的值相关联。一旦最后一个位置溢出，那么您就生成了所有可能的组合。

我从数组中的最后一个值开始递增计数器，然后向下移动以获得与示例中相同的输出，但这当然不是必需的。该算法不检查重复项。

您不必使用当前组合存储字符数组，您可以每次在基于计数器的 for 循环中重新生成它，但这可能效率较低。此方法仅更新更改的值。

public static void buildStrings(char[] root, int length)
{
    // allocate an int array to hold the counts:
    int[] pos = new int[length];
    // allocate a char array to hold the current combination:
    char[] combo = new char[length];
    // initialize to the first value:
    for(int i = 0; i < length; i++)
        combo[i] = root[0];

    while(true)
    {
        // output the current combination:
        System.out.println(String.valueOf(combo));

        // move on to the next combination:
        int place = length - 1;
        while(place >= 0)
        {
            if(++pos[place] == root.length)
            {
                // overflow, reset to zero
                pos[place] = 0;
                combo[place] = root[0];
                place--; // and carry across to the next value
            }
            else
            {
                // no overflow, just set the char value and we're done
                combo[place] = root[pos[place]];
                break;
            }
        }
        if(place < 0)
            break;  // overflowed the last position, no more combinations
    }
}

ideone.com 演示