计算数组的重复排列

Question

假设我有一个包含 5 个元素的数组。我如何在 C 中计算此数组的所有可能重复排列。

编辑:我的意思是使用 5 创建所有可能的数组。所以位置很重要。

例子:

array = [1,2,3,4,5]

[1,1,1,1,1]
[1,1,1,1,2]
[1,1,1,2,3]
.
.

Answer 1

生成组合或排列的一种常见方法是使用递归:枚举第一个元素的每种可能性，并将这些可能性添加到减少一个元素的同一集合的每个组合或排列中。因此，如果我们说您正在寻找一次k n 事物的排列数，我们使用符号 perms(n, k), 你得到:

perms(5,5) = {
    [1, perms(5,4)]
    [2, perms(5,4)]
    [3, perms(5,4)]
    [4, perms(5,4)]
    [5, perms(5,4)]
}

同样，对于 perms(5,4) 你会得到:

perms(5,4) = {
    [1, perms(5,3)]
    [2, perms(5,3)]
    [3, perms(5,3)]
    [4, perms(5,3)]
    [5, perms(5,3)]
}

所以 perms(5,5) 的一部分看起来像:

[1, 1, perms(5,3)]
[1, 2, perms(5,3)]
[1, 3, perms(5,3)]
[1, 4, perms(5,3)]
[1, 5, perms(5,3)]
[2, 1, perms(5,3)]
[2, 2, perms(5,3)]
...

定义 perms(n, k) 很简单。对于任何递归定义，您需要两件事:基本情况和递归步骤。基本情况是 k = 0:perms(n, 0) 是一个空数组 []。对于递归步骤，您通过将集合中的每个可能值添加到 perms(n, k-1) 的所有元素来生成元素。