algorithm - 迭代查找字符数组大小为 k 的所有组合(N 选择 K)

Question

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

基本上:

• 给定一个元素数组，例如E = {1,2,a,b} 和
• 给定一个数字 K，例如K = 2
• 我想退回所有Combinations E 尺码 K(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));
        }
    }
}

其中pool为E，length为K。

所以我们会调用:buildStringRec(new char[2], 0, 2); 并获取

11
12
13
21
22
23
31
32
33

这可以迭代完成吗？我一直在努力思考如何使用可变长度来做到这一点。

任何帮助将不胜感激!如果需要，我可以按原样发布我的代码，但由于我的重试，它的更改如此频繁，以至于我一发布就几乎没用了。

此外，我不想使用 Apache 或 String Builder 来执行此操作，因为我想了解如何执行此操作的概念。我不是简单地要求代码。只要解释清楚，伪代码就可以。

谢谢!

编辑

我正在使用这个网站来测试呈现给我的所有选项:https://ideone.com/k1WIa6
随意 fork 并尝试一下!

Answer 1

递归求解

对我来说，递归解决方案似乎是最好的选择。
您可以用堆栈替换克隆路径数组以提高性能:

char[] pool = new char[]{'1', '2', '3'};
Stack<int> stack = new Stack<int>();

// Actually, resulting length should be the same length as pool array
int length = pool.length;

public void buildStringRec(int pos)
{
    if (length == pos + 1) 
    {
        System.out.println(String.valueOf(root));
        return;
    }

    for(char c : pool){
        stack.Push(c);
        buildStringRec(pos + 1);
        stack.Pop(c);
    }
}

迭代解决方案

假设，出于某种原因，您需要反复执行此操作。
我相信有更好的解决方案。不过，这是我能做的最好的了。

您可以将您的任务改写为另一个任务:

How to output ALL numbers in base N of length N.

假设您有一个长度为 3 的数组:{'a', 1, 'z'}。
您想要的答案是:

a-a-a    a-a-1    a-a-z
a-1-a    a-1-1    a-1-z
a-z-a    a-z-1    a-z-z
1-a-a    1-a-1    1-a-z

现在，让我们看看这些值的索引:

0-0-0    0-0-1    0-0-2
0-1-0    0-1-1    0-1-2
0-2-0    0-2-1    0-2-2 
2-0-0    2-0-1    2-0-2

实际上，这是一个以 3 为基数的连续数字:000, 001, 002, 010, 011, 012, 020, 021, 022, 200, 201, 202。

记住它们的计算公式:base ^ length。在我们的例子中，length == base。因此，它是 base ^ base。

现在，我们的任务变得更容易了:

int[] toBase(long bs, long value)
{ 
    int[] result = new int[bs];
    for (long i = bs - 1; i >= 0; i--)
    {
        result[i] = (int)(value % bs);
        value = value / bs;
    }
    return result;
}

long Pow(long a, long b)
{
    long result = 1;
    for (int i = 0; i < b; i++) result *= a;
    return result;
}

char[] pool = new char[] {'a', 'b', 'c'};

void outputAll()
{
    long n = pool.Length;
    for (long i = 0; i < Pow(n, n); i++)
    {
        int[] indices = toBase(n, i);
        for (int j = 0; j < n; j++)
            Console.Write("{0} ", pool[indices[j]]);
        Console.WriteLine();
    }
}

当然，可以有一些优化:

• 不需要每次都计算toBase。从 000 开始并且每次都计算下一个数字更容易且性能更高。
• 您可以更改 Pow 函数以使用快速平方求幂 算法等。

这只是为了解释一种方法而提供的示例。

请记住，长度为 3 的数组只有 27 种这样的组合。然而，长度为 7 的数组将有 823543。它呈指数增长。

工作示例

这是一个DotNetFiddle working Demo .

只需更改 pool 数组值即可获得结果。 在这里和上面的所有示例中，我都使用了 C#。它可以很容易地转换为 C++ :)

对于我来说，它适用于长达 7 的长度(大约 1 - 1.5 秒)。
当然，您需要删除控制台输出才能获得这样的结果。控制台输出工作真的很慢。