問題設定
どこかで見たことのあるような問題ですが、ふと以下のような問題を考えてみたくなりました。
"ABCDE....XYZ"のpermutationを考える。7777777777番目(0-based)のpermutationを求めよ。
例えば、 ABCDEFGHIJKLMNOPQRSTUVWXYZは0番目のpermutation。 ABCDEFGHIJKLMNOPQRSTUVWXZYは1番目のpermutation。 ..... と続きます。
例えば、 ABCDEFGHIJKLMNOPQRSTUVWXYZは0番目のpermutation。 ABCDEFGHIJKLMNOPQRSTUVWXZYは1番目のpermutation。 ..... と続きます。
以前TopCoderで似たような問題を解いたことがあったので、スムーズに書けました。悩ましいのは23行目のifのところに等号をつけるかどうかですが、「index番目をくれ」と言われたらindex+1以上持っている必要があり(0-basedだから)index個では足りないので次の文字まで行きます。
ついでに、逆変換する関数(permutationが与えられるので、辞書順で何番目かを返す関数)も書きました。
ついでに、逆変換する関数(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 件のコメント:
コメントを投稿