順列と辞書順の相互変換

問題設定

　どこかで見たことのあるような問題ですが、ふと以下のような問題を考えてみたくなりました。

"ABCDE....XYZ"のpermutationを考える。7777777777番目（0-based）のpermutationを求めよ。
例えば、 ABCDEFGHIJKLMNOPQRSTUVWXYZは0番目のpermutation。 ABCDEFGHIJKLMNOPQRSTUVWXZYは1番目のpermutation。 ..... と続きます。

　以前TopCoderで似たような問題を解いたことがあったので、スムーズに書けました。悩ましいのは23行目のifのところに等号をつけるかどうかですが、「index番目をくれ」と言われたらindex+1以上持っている必要があり（0-basedだから）index個では足りないので次の文字まで行きます。
　ついでに、逆変換する関数（permutationが与えられるので、辞書順で何番目かを返す関数）も書きました。

ソースコード

view plainprint?

1. #include <iostream>  
2. #include <cstring>  
3. #include <algorithm>  
4. #include <cassert>  
5.   
6. using namespace std;  
7.   
8. const long long INF = 1LL << 50;  
9. long long f[26];  
10.   
11. // return the index-th(0-based) permutation of "ABCD...Z"  
12. string toPermutation (long long index) {  
13.     bool used[26];  
14.     char permutation[26+1];  
15.   
16.     memset(used, 0, sizeof(used));  
17.     memset(permutation, 0, sizeof(permutation));  
18.   
19.     for (int i = 0; i < 26; i++) {  
20.         for (int j = 0; j < 26; j++) {  
21.             if (used[j])  
22.                 continue;  
23.             if (f[25-i] <= index)  
24.                 index -= f[25-i];  
25.             else {  
26.                 permutation[i] = static_cast<char>('A'+j);  
27.                 used[j] = 1;  
28.                 break;  
29.             }  
30.         }  
31.     }  
32.   
33.     return permutation;  
34. }  
35.   
36. // return the lexicological order(0-based) of a permutation  
37. long long toIndex(string permutation) {  
38.     bool used[26];  
39.   
40.     memset(used, 0, sizeof(used));  
41.     long long ret = 0;  
42.     for (int i = 0; i < 26; i++) {  
43.         int c = permutation[i] - 'A';  
44.         for (int j = c-1; j > 0; j--) {  
45.             if (!used[j])  
46.                 ret += f[25-i];  
47.         }  
48.         used[c] = 1;  
49.     }  
50.   
51.     return ret;  
52. }  
53.   
54. int main(int argc, char **argv) {  
55.     // calculate factorials  
56.     f[0] = 1;  
57.     for (int i = 1; i < 26; i++)  
58.         f[i] = min(i*f[i-1], INF);  
59.   
60.     long long index;  
61.     cout << "input an integer:(up to 10 digits)" << endl;  
62.     cin >> index;  
63.     assert(index < 1e10);  
64.   
65.     cout << "The " << index << "-th permutation is " << toPermutation(index) << endl;  
66.   
67.     // for debug use  
68.     assert(toIndex(toPermutation(index)) == index);  
69.   
70.     return 0;  
71. }  

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cassert>

using namespace std;

const long long INF = 1LL << 50;
long long f[26];

// return the index-th(0-based) permutation of "ABCD...Z"
string toPermutation (long long index) {
    bool used[26];
    char permutation[26+1];

    memset(used, 0, sizeof(used));
    memset(permutation, 0, sizeof(permutation));

    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < 26; j++) {
            if (used[j])
                continue;
            if (f[25-i] <= index)
                index -= f[25-i];
            else {
                permutation[i] = static_cast<char>('A'+j);
                used[j] = 1;
                break;
            }
        }
    }

    return permutation;
}

// return the lexicological order(0-based) of a permutation
long long toIndex(string permutation) {
    bool used[26];

    memset(used, 0, sizeof(used));
    long long ret = 0;
    for (int i = 0; i < 26; i++) {
        int c = permutation[i] - 'A';
        for (int j = c-1; j > 0; j--) {
            if (!used[j])
                ret += f[25-i];
        }
        used[c] = 1;
    }

    return ret;
}

int main(int argc, char **argv) {
    // calculate factorials
    f[0] = 1;
    for (int i = 1; i < 26; i++)
        f[i] = min(i*f[i-1], INF);

    long long index;
    cout << "input an integer:(up to 10 digits)" << endl;
    cin >> index;
    assert(index < 1e10);

    cout << "The " << index << "-th permutation is " << toPermutation(index) << endl;

    // for debug use
    assert(toIndex(toPermutation(index)) == index);

    return 0;
}