Search on the blog

2012年3月30日金曜日

順列と辞書順の相互変換

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

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

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

ソースコード
#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;
}

0 件のコメント:

コメントを投稿