c++ - 对应字符不在同一位置时字符串的所有排列

Question

我需要给定字符串的所有可能排列，以便没有字符应与输入字符串保持在同一位置。例如。：对于输入“询问”输出：所有可能的排列，如“ksa”，“kas”......这样'a'不在第一个位置，'s'不在第二个位置等等......在任何排列。

我只需要计算这种可能的排列

我可以通过生成所有排列并过滤它们来做到这一点，但我需要一种非常有效的方法来做到这一点。

字符串中的所有字符都是“唯一”

首选语言 C++。

Answer 1

您正在寻找的东西被称为错乱 -维基百科文章很好地解释了一种获取公式的方法，以及几个不同的结果方程。

您还可以使用包含原理来计算数字，从所有排列的数量 - n! 开始，然后减去固定在其位置上的一个数字的排列，加上固定两个数字的排列，依此类推。

Answer 2

对于一组可n区分的元素，您可以通过以下方式排列它们，而没有元素位于其原始位置dearangements(n)：

int derangements(int n) {
    assert(n >= 0);
    return n ? ((n - 1) * (derangements(n - 1) + derangements(n - 2)) : 1;
}

请注意，由于非线性递归，这具有指数运行时间。但是，您可以改进此公式。

int derangements(int n) {
    assert(n >= 0);
    if(n == 0) return 1;

    int a = 1;
    int b = 0;
    do {
       int x = (n-1)*(a+b);
       a = b;
       b = x;
    } while(--n > 1);
    return b;
}