若干固定数的置换

Question

如果我需要指定位置的字符/数字，如何有效地生成一个数字(或word中的字符)的排列？

例如，用数字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

Answer 2

我读过其他的答案，我相信在你的具体问题上，它们比我的好。不过，如果有人需要一个通用的解决方案来解决你的问题，我会回答。

我最近需要生成三个独立的连续范围[first1，last1) + [first2，last2) + [first3，last3)的所有排列。这对应于您的情况，所有三个范围都是长度为1，并且只有一个元素分隔。在我的例子中，唯一的限制是距离(first3，last3) >=距离(first1，last1) +距离(first2，last2) (我相信可以用更多的计算费用来放松这个限制)。

我的应用程序是生成每个唯一的排列，而不是它的反向排列。守则如下：

http://howardhinnant.github.io/combinations.html

具体适用的函数是combine_discontinuous3 (创建组合)，它在创建排列的reversible_permutation::operator()中使用。

这不是一个现成的打包解决方案，您的问题。但是它是一个工具集，可以用来解决问题的泛化。同样，对于您的简单问题，我推荐其他人已经提供的更简单的解决方案。

Answer 3

记住你想要固定号码的地方。从数组中删除它们。像往常一样产生排列。在每次排列之后，将固定的数字插入到它们应该出现的位置，然后输出。