使用 2 个值查找长度 N 的所有排列

Question

我有一组值，例如：{1,2}，{1,2,3} ...等。

如何找到所有排列，包括长度为 N 的重复值。

输入： 值={1,2}； N =3

输出： 111,112,121,122,211,212,221,222

N>不。价值观

所以如果我们取 {1,2,3} 那么 N > 3

无法为此找到适当的算法。

我想过实现回溯，但我认为对其进行任何修改都不能解决这个问题，如果我错了，请纠正我。

Answer 1

为什么回溯不起作用？这是一个简单的实现：

def generate(position, result, N, values):
    if position == N:
        print(''.join(result))
        return
    for val in values:
        result[position] = val
        generate(position+1, result, N, values)

这个运行与

values = ['1', '2', '3']
N = 3
result = [None]*N
generate(0, result, N, values)

Answer 2

N 应该大于值的数量的约束并不重要。

假设值的集合是{0,1,2,3,4,5,6,7,8,9}并且N=3。那么输出将是从 000 到 999 的所有整数，因此我们可以通过从 000 到 999 一一计数来生成它们。

概括这个想法，算法可以从第一个值的 N 个副本的序列开始，然后“计数”直到达到最后一个值的 N 个副本。

在每次迭代时，打印当前序列，然后像整数加 1 一样“加一”：从第一个位置开始，如果该值不是最后一个值，则将其更改为下一个值并停止此步骤。如果该值是最后一个值，则将其设置为第一个值并在下一个位置重复。

如果位置达到N，则所有组合都已打印完毕，算法完成。

对于 {1,2} 且 N = 3，序列将是：

111  <-- initial sequence
211  <-- first position advanced
121  <-- first position reset and second position advanced
221
112
212
122
222  <-- N'th position reached with all values at the last: DONE

注意：由于我认为这是家庭作业，所以我故意不发布完整的实现。