c++ - 使用多个元素计算排列

Question

我正在尝试生成一组元素的所有可能排列。顺序无关紧要，元素可能会出现多次。每个排列的元素个数等于元素总数。

根据模式计算排列的基本递归算法(因为我是用 C++ 编写的，代码看起来与它类似):

elems = [0, 1, .., n-1];    // n unique elements. numbers only exemplary.
current = [];               // array of size n
perms(elems, current, 0);   // initial call

perms(array elems, array current, int depth) {
    if(depth == elems.size) print current;
    else {
        for(elem : elems) {
            current[depth] = elem;
            perms(elems, current, depth+1);
        }
    }
}

会产生大量的冗余序列，例如:

0, 0, .., 0, 0
0, 0, .., 0, 1    // this
0, 0, .., 0, 2
.  .  .   .  . 
.  .  .   .  .
0, 0, .., 0, n-1
0, 0, .., 1, 0    // is the same as this
.  .  .   .  .    // many more redundant ones to follow

我试图确定何时可以跳过确切的生成值，但到目前为止还没有发现任何有用的东西。我确信我可以找到一种方法来解决这个问题，但我也确信，这背后有一个我还没有设法看到的规则。

编辑:可能的解决方案+

elems = [0, 1, .., n-1];       // n unique elements. numbers only exemplary.
current = [];                  // array of size n
perms(elems, current, 0, 0);   // initial call

perms(array elems, array current, int depth, int minimum) {
    if(depth == elems.size) print current;
    else {
        for(int i=minimum; i<elems.size; i++) {
            current[depth] = elems[i];
            perms(elems, current, depth+1, i);
        }
    }
}

Answer 1

让你的第一个位置从 0 到 n 变化。然后让你的第二个位置为1。然后让你的第一个位置从1到n变化。然后将秒设置为 2 --> 首先从 2 到 n 等等。