递归解法
对我来说，递归解决方案似乎是最好的选择。
您可以用堆栈替换克隆路径数组以提高性能：
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);
}
}
迭代解决方案
假设由于某种原因，您需要迭代地执行此操作。
我确信有更好的解决方案。不过，这已经是我能做到的最好的了。
您可以将您的任务改写为另一项：
如何输出长度为 N 的以 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快速使用的功能exponentiation by squaring算法等
这只是为了解释一种方法而提供的示例。
请记住，长度为 3 的数组将只有 27 个这样的组合。然而，长度为 7 的数组将有 823543。它呈指数增长。
工作样本
这里有一个DotNetFiddle 工作演示 https://dotnetfiddle.net/7lyEaB.
只是改变pool数组值以获得结果。
在这里和上面的所有示例中我都使用了 C#。它可以轻松转换为 C++ :)
对于我来说，它的长度在 7 以内（大约 1 - 1.5 秒）效果很好。
当然，您需要删除控制台输出才能获得这样的结果。控制台输出有效真的很慢.
