具有一些固定数字的排列

Question

如果我在指定的地方需要一些字母/数字,如何有效地生成一个数字的排列(或单词中的字符)？

例如,从头开始在第二位生成数字3的所有数字,从数字末尾开始在第二位生成数字1.数字中的每个数字必须是唯一的,您只能从数字1-5中选择.

4 3 2 1 5
4 3 5 1 2
2 3 4 1 5
2 3 5 1 4
5 3 2 1 4
5 3 4 1 2

我知道有一个next_permutation函数,所以我可以准备一个数字为{4,2,5}的数组并将其循环发布到这个函数,但是如何处理固定位置？

Answer 1

生成所有排列2 4 5并在输出例程中插入3和1.只要记住他们必须的立场:

int perm[3] = {2, 4, 5};
const int N = sizeof(perm) / sizeof(int);

std::map<int,int> fixed;  // note: zero-indexed
fixed[1] = 3;
fixed[3] = 1;

do {
    for (int i=0, j=0; i<5; i++)
        if (fixed.find(i) != fixed.end())
            std::cout << " " << fixed[i];
        else
            std::cout << " " << perm[j++];
    std::cout << std::endl;
} while (std::next_permutation(perm, perm + N));

输出

 2 3 4 1 5
 2 3 5 1 4
 4 3 2 1 5
 4 3 5 1 2
 5 3 2 1 4
 5 3 4 1 2