0

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

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

例子：

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

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

4 回答 4

4

生成组合或排列的常用方法是使用递归：枚举第一个元素的每种可能性，并将这些可能性添加到减少一个元素的同一集合的每个组合或排列中。因此，如果我们说您正在寻找一次取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) 的所有元素来生成元素。

于 2013-01-04T15:44:59.017 回答
3

如果我的问题正确，您需要生成所有 5 位数字，数字为 1、2、3、4 和 5。所以有一个简单的解决方案 - 生成所有以 5 为基数的数字44444，然后将 0 映射到 1、1到 2 以此类推。在需要的地方添加前导零 - 所以10变成00010or [1,1,1,2,1]。

注意：您实际上不必自己生成数字，您可以将数字迭代到 5**5（不包括），并通过获取以 5 为底的数字来为每个数字找到相应的序列。

于 2013-01-04T15:42:31.467 回答
2 
int increment(size_t *dst, size_t len, size_t base) {
    if (len == 0) return 0;
    if (dst[len-1] != base-1) {
        ++dst[len-1];
        return 1;
    } else {
        dst[len-1] = 0;
        return increment(dst, len-1, base);
    }
}

有了这个函数，你可以从 . 开始迭代 (0 ... 4) 的所有重复排列{0, 0, 0, 0, 0}。当重复排列用完时，该函数将返回 0。

然后对于每个重复排列，将内容用作数组的索引，以便获得数组的重复排列，而不是 (0 ... 4)。

于 2013-01-04T15:48:02.030 回答
2

在您给定的示例中，每个位置都可以被1, 2, 3, 4,占据5。由于有 5 个位置，所以可能性的总数 = 5 * 5 * 5 * 5 * 5 = 5 ^ 5 = 3125. 一般来说，它会是N ^ N。（其中 ^ 是幂运算符）。

为了产生这些可能性，在每个位置上，一个接一个地输入数字1, 2, 3, 4, 5, 并从最后一个位置开始递增，类似于 5 位计数器。

因此，从11111. 增加最后一个位置以获得11112...直到11115。然后回绕到1，并增加下一个数字11121继续11122...11125等。重复此操作直到到达第一个位置，您将在 结束55555。

于 2013-01-04T15:43:39.430 回答