宝塔服务器面板，一键全能部署及管理，送你10850元礼包，点我领取

一、错排是什么

错排是组合数学中的一种常用问题，它指将n个元素排列在n个位置上，其中每个元素最多出现一次，有多少种不同排列情况。通俗的说，就是在所有的排列中，有多少种情况下，没有元素排在它原本的位置上。

/**
 * 阶乘
 */
int factorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

/**
 * 错排公式
 */
int deRange(int n) {
    if (n == 1) {
        return 0;
    } else if (n == 2) {
        return 1;
    } else {
        return (n - 1) * (deRange(n - 1) + deRange(n - 2));
    }
}

二、错排公式的推导

下面我们以n=4为例，来推导一下错排公式。

我们要求的是4个元素排列的错排数。

首先，第一个元素有3种可能，它可以排在除了第一个位置之外的任意一个位置上，那么第一个元素排完之后，问题就转化为了剩下的3个元素的错排，总数就是3*(3-1) = 6。

如果第一个元素排在第二个位置上，那么它就不能排在第一个位置和第二个位置，那么它就只能排在第三个位置或者第四个位置上。如果排在第三个位置上，剩下的元素需要错排，错排的总数就是2*(2-1) = 2；如果排在第四个位置上，剩下的元素也需要错排，错排的总数也是2*1 = 2。

所以，第一个元素排在第二个位置的总数就是4。

同理，如果第一个元素排在第三个位置和第四个位置，那么错排的总数也是4。

最终，我们得到的结果就是 3*(3-1)*2 + 4*(2-1)*2 + 4*(2-1)*2 = 18+8+8 = 34

三、程序实现

这里我们使用递归的方式来实现错排公式。注意，当n=1时，返回值为0；n=2时，返回值为1。

int deRange(int n) {
    if (n == 1) {
        return 0;
    } else if (n == 2) {
        return 1;
    } else {
        return (n - 1) * (deRange(n - 1) + deRange(n - 2));
    }
}

// 输出n个元素的错排数
int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", deRange(n));
    return 0;
}

四、使用错排公式的一些场景

错排公式可以用于多种场合，下面我们介绍几个常见的使用情况。

1、密码学

错排公式可以用于密码学，当我们需要把一个明文字符串加密成一个密文字符串时，可以使用错排公式来产生一个随机的排列方式，然后将所有的字符按照这种排列方式进行替换，从一个字符串变成另一个字符串。

// 将字符串s按照错排公式进行加密
string encode(string s) {
    int n = s.size();
    // 产生一个随机的排列方式
    vector p(n);
    for (int i = 0; i < n; i++) {
        p[i] = i;
    }
    random_shuffle(p.begin(), p.end());
    // 将所有字符按照排列方式进行替换
    string t(n, ' ');
    for (int i = 0; i < n; i++) {
        t[p[i]] = s[i];
    }
    return t;
}

// 将字符串s按照给定的排列方式进行解密
string decode(string s, vector p) {
    int n = s.size();
    string t(n, ' ');
    for (int i = 0; i < n; i++) {
        t[i] = s[p[i]];
    }
    return t;
}

2、贡献值排序

在有些场合下，我们需要对一组数据进行排序，但是需要考虑到每个元素的贡献值。例如，在一堆学生中，有些学生的成绩比较高，但是参与过的活动比较少，有些学生的成绩比较低，但是参与过的活动比较多，那么我们要按照这两项指标分别对学生进行评价，如何给出一个合理的排序呢？错排公式可以提供一种思路，即将高成绩的学生看作是排列在前面的元素，将参与活动多的学生看作排列在后面的元素，然后使用错排公式计算出所有满足要求的排列数量，根据排列数量的大小来进行排序。

// 对一组数据按照权值进行排序
template
vector<pair> sortByWeight(const vector &a, function getWeight) {
    int n = a.size();
    vector<pair> w(n);
    for (int i = 0; i < n; i++) {
        w[i] = make_pair(getWeight(a[i]), a[i]);
    }
    sort(w.rbegin(), w.rend()); // 按照权值从大到小排序
    double totalWeight = accumulate(w.begin(), w.end(), 0.0, [](double x, pair y) { return x + y.first; });
    vector<pair> result(n);
    for (int i = 0; i < n; i++) {
        double leftWeight = totalWeight - w[i].first; // 排列在后面的元素的贡献值之和
        double rightWeight = w[i].first; // 排列在前面的元素的贡献值
        int leftCount = n - 1 - i; // 排列在后面的元素的个数
        int rightCount = i; // 排列在前面的元素的个数
        int totalCount = leftCount + rightCount;
        result[i].first = (double) deRange(totalCount) / factorial(totalCount) * leftWeight + (double) deRange(leftCount) / factorial(leftCount) * rightWeight;
        result[i].second = w[i].second;
    }
    sort(result.rbegin(), result.rend()); // 按照错排数量从大到小排序
    return result;
}

3、图像隐写

图像隐写是将一张图片嵌入到另一张图片中，使得外观上看起来像一张图片。错排公式可以提供一种方式，根据错排公式的结果，将原始图片的像素点随机地替换成隐写图片的像素点。

// 将图片t嵌入到图片s中
Mat embed(Mat s, Mat t) {
    srand(time(NULL));
    int n = s.rows * s.cols;
    vector p(n);
    for (int i = 0; i < n; i++) {
        p[i] = i;
    }
    random_shuffle(p.begin(), p.end());
    Mat result = s.clone();
    for (int i = 0; i < n / 2; i++) {
        int x1 = p[2 * i] / s.cols;
        int y1 = p[2 * i] % s.cols;
        int x2 = p[2 * i + 1] / s.cols;
        int y2 = p[2 * i + 1] % s.cols;
        result.at(x1, y1) = t.at(x2 % t.rows, y2 % t.cols);
        result.at(x2, y2) = t.at(x1 % t.rows, y1 % t.cols);
    }
    return result;
}