全排列 - I



BB

对了也不要期盼接下来能更新快，毕竟中心转移了（由算法转思维，但是思维一般不会专门码文 QAQ）

Introduction

本文主要涉及全排列生成算法中的字典序法与递归方法


全排列 - 51NOD 1384

Link
https://www.51nod.com/Challenge/Problem.html#!#problemId=1384
Description
给出一个字符串S（可能有重复的字符），按照字典序从小到大，输出S包括的字符组成的所有排列
Sample Input

1312

Sample Output

1123  
1132  
1213  
1231
1312
1321
2113
2131  
2311
3112
3121
3211

Solution 1: 字典序法
C++ STL中的next_permutation()方法用此方法

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15;
const int inf = 0x3f3f3f3f;

char s[15];

bool next_permutation(char* s, int len) {
    int x = -1, y = len - 1;
    for(int i = len - 1; i - 1 >= 0; i--) {
        if(s[i - 1] < s[i]) {
            x = i - 1;
            break;
        }
    }

    if(x == -1) {
        return false;
    }

    for(int i = x + 1; i < len; i++) {
        if(s[x] >= s[i]) {
            y = i - 1;
            break;
        }
    }

    swap(s[x], s[y]);
    reverse(s + x + 1, s + len);
    return true;
}

int main() {
    while(~scanf("%s", s)) {
        int len = strlen(s);
        sort(s, s + len);

        do{
            puts(s);
        }while(next_permutation(s, len));
    }
}

Solution 2: 递归方法
缺点很明显，全部做完之后才能排序以及去重，效率低

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15;
const int inf = 0x3f3f3f3f;

vector<string> vec;

void getPermutation(int idx, int len, string& s) {
    if(idx == len) {
        vec.push_back(s);
        return;
    }
    for(int i = idx; i < len; i++) {
        swap(s[idx], s[i]);
        getPermutation(idx + 1, len, s);
        swap(s[idx], s[i]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    string s;
    while(cin >> s) {
        vec.clear();

        getPermutation(0, s.size(), s);

        sort(vec.begin(), vec.end());
        int n = unique(vec.begin(), vec.end()) - vec.begin();

        for(int i = 0; i < n; i++) {
            cout << vec[i] << endl;
        }
    }
}

Solution 3: 递归方法
在看POJ 1256在Discuss中看到的方法

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15;
const int inf = 0x3f3f3f3f;

bool flag[15];
char s[15], a[15];

void dfs(int idx, int len) {
    if(idx == len) {
        puts(s);
    }
    for(int i = 0; i < len; i++) {
        if(flag[i]) {
            continue;
        }

        flag[i] = true;
        s[idx] = a[i];
        dfs(idx + 1, len);
        flag[i] = false;
        while(i + 1 < len && a[i + 1] == a[i]) {
            i++;
        }
    }
}

int main() {
    while(~scanf("%s", a)) {
        memset(flag, false, sizeof(flag));
        int len = strlen(a);
        sort(a, a + len);
        dfs(0, len);
    }
}


New Year and the Permutation Concatenation - Codeforces 1091D

Link
http://codeforces.com/contest/1091/problem/D
Description
给定一个数n，求从1到n的所有按字典序排序的全排列组合组成的序列p中和为n(n+1)/2的连续子序列的个数，结果对998244353取模
e.g. n=3，p=[1,2,3,1,3,2,2,1,3,2,3,1,3,1,2,3,2,1]，seq={[1,2,3], [2,3,1], [3,1,3], [1,3,2], [3,2,2], [2,2,1], [2,1,3], [1,3,2], [3,2,3], [2,3,1], [3,1,3], [1,3,1], [3,1,2], [1,2,3], [2,3,2], [3,2,1]}，ans =9
Sample Input

3
4
10

Sample Output

9
56
30052700

Solution: 全排列字典序法生成算法思维
首先考虑到n(n+1)/2其中的一种情况是当前连续子序列对应于[1,n]中的每一个元素 接下来考虑全排列的字典序生成算法，可以知道如果从某个排列选择后缀k个元素，即前缀n-k个元素，若这k个元素不是降序的，那么下一个排列的前缀n-k个元素与此排列是相同的，那么这一子序列则能满足要求

因此考虑枚举k，用全部情况减去不满足条件的情况，即

\[\begin{aligned} ans &= n \cdot n! - \sum_{k=1}^{n} C_n^k A_{n-k}^{n-k} \\ &= n \cdot n! - \sum_{k=1}^{n}\frac{n!}{k! \cdot (n - k)!} \cdot (n - k)! \\ &= n \cdot n! - \sum_{k=1}^{n} \frac{n!}{k!} \end{aligned}\]

另外在分析过程中可以隐隐约约的发现，n(n+1)/2只有这一种情况 （证明？不会QAQ）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const int MOD = 998244353;
typedef pair<int, int> pii;
typedef long long ll;

ll arr[N];

inline void init() {
    arr[1] = 1;
    for(int i = 2; i < N; i++) {
        arr[i] = (arr[i - 1] * i) % MOD;
    }
}

ll quickPow(ll a, int b) {
    ll ans = 1, base = a;
    while(b) {
        if(b & 1)   ans = (ans * base) % MOD;
        base = (base * base) % MOD;
        b >>= 1;
    }
    return ans;
}

int main() {
    init();


    int n;
    while(~scanf("%d", &n)) {
        ll ans = (n * arr[n]) % MOD;
        for(int k = 1; k <= n - 1; k++) {
            ans = (ans - arr[n] * quickPow(arr[k], MOD - 2)) % MOD;
        }
        ans = (ans + MOD) % MOD;
        printf("%lld\n", ans);
    }
}