计算数组的重复排列

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

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）。

Answer 2

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

注意：你实际上并不有生成数字本身，你可能只是重复数字0到5 ** 5（不含），并为他们每个人将得到它找到corresponing序列的数字基地5

Answer 3

。在你给出的例子中，每个位置既可以由0​​，2，3，4，5占用。由于有5个职位，总可能性= 5 * 5 * 5 * 5 * 5 = 5^5 = 3125。一般来说，这将是N^N。 （其中^是指数运算符）。

要产生这些可能性，在每个位置，把数字1，2，3，4，5，一个接一个，而增量从最后一个位置，类似于一个5位计数器开始。

因此，从​​开始。增加最后的位置以获得11112 ...直到11115。 然后换回1，然后递增下一个数字11121继续使用11122 ... 11125等。重复此操作直到您到达第一个位置，并且您将在55555处结束。

Answer 4

生成组合或排列的常用方法是使用递归：枚举第一个元素的每个可能性，并将其添加到每个组合或排列中，以减少同一个元素减少一个元素。所以，如果说你正在寻找一次取ķ的ň东西排列的数量和我们使用符号烫发（ñ，ķ），您可以：

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

同样，烫发（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)] 
} 

所以烫发（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)] 
... 

定义烫发（n，k）很容易。至于任何递归定义，您需要两件事情：一个基本案例和一个递归步骤。基座情况是ķ = 0：烫发（Ñ，0）为空数组，[]。对于递归步骤，您生成前面加上每个可能的值要在集中所有烫发的元素（ñ，ķ -1）的元素。