有没有像next_permutation一样用于重复排列的函数？

Question

我希望做的是找出一个带有重复元素的一维数组的所有排列。

例如：

int array[]={1,2,3};
for(i=0;i<3;i++){
    next_permutation(array,array+3)
    for(int j=0;j<=3;j++){
        printf("%d ",array[j]);
    }
printf("\n");
}

将返回：

1 2 3
1 3 2
2 1 3
etc...

我想要函数返回的内容：

1 1 1
1 1 2
1 2 1
2 1 1
1 2 2
2 2 1
2 1 2
1 1 3
1 3 1
3 1 1
etc...

有没有一个能够做到这一点的函数？

提前感谢， Erik

- Erik Sophocleous

---

这是相关的：http://stackoverflow.com/questions/1944508/arbitrary-digit-counter - Aziz

以及这个链接：https://dev59.com/LUzSa4cB1Zd3GeqPl1zR - Aziz

Answer 1

你不是在进行排列，而只是在计数。

例如，如果你要枚举集合{0, 1}的3位数字，你将得到：

000
001
010
011
100
101
110
111

看，这只是二进制计数。

因此，将您的元素集映射到n位数字，然后进行n进制计数将给出正确的答案。

- Zang MingJie

Answer 2

我用Java写了这个程序。
虽然代码没有优化，但你可以理解我的意思：

String [] data = {"1","2","3"};
public void perm(int maxLength, StringBuffer crtComb){

    if (crtComb.length() == maxLength){
        System.out.println(crtComb.toString());
        return;
    }

    for (int i=0; i<data.length; i++){
        crtComb.append(data[i]);
        perm(maxLength, crtComb);
        crtComb.setLength(crtComb.length()-1);
    }

}

- Adrian

Answer 3

通常在计算从1到k（带重复）的整数排列时：

1. 最初将第一个排列设置为 1 1 1.... （k次）。

2. 找到最右边的索引（称为j），使该索引处的元素小于k。

3. 将索引j处的元素值增加一，并从位置j + 1至k重置所有元素为1。

4. 重复步骤2和3。

应用此逻辑，我们现在得到：

第1个排列-> 1 1 1。

然后在第2个位置（0索引计数）有1 < 3，因此将其增加并将此位置之后的所有元素重置为1。第2个排列-> 1 1 2。

然后在第1个位置（0索引计数）有1 < 3，因此将其增加并将此位置之后的所有元素重置为1。第3个排列-> 1 2 1。

依此类推。

- Darshan Dorai