[UVA][math] 10460 - Find the Permuted String
Problem H
Find the Permuted String
Input: standard input
Output: standard output
Time Limit: 1 seconds
Permutation of a given string can be done in different ways. In order to get different permutations of a string, when all characters in the string are different, Donald E. Knuth gave the following process. To get all the permutations of a n character string (a1a2…an), using each permutation a1, a2… an-1, we can form n others by inserting ‘an’ (nth character) in all possible places. Thus we get n! permutations of that string. For example, to generate all permutations of “ACB”, we first start with ‘A’, then insert ’C’ and then insert ‘B’.
|
Col1 |
Col2 |
Col3 |
Permutation Index |
|
A |
CA
AC |
BCA CBA CAB BAC ABC ACB |
1 2 3 4 5 6 |
So we see that using above technique, the permutations of “ACB” are generated in a particular order. Here 2nd permutation of “ACB” is the string “CBA” or permutation index of “CBA” is 2. In this problem you will be given a string and a permutation index, I. You have to find the I'th permutation of the given string.
Input
First line of the input file will contain an integer denoting the number of test cases to follow. For each test case there will be two lines. First line of each test case will contain a string of length less than or equal to 26. The characters of the string will be all upper case letters and different. Next line will contain a permutation index, I. Range of I is from 1 to min(n!,2^31-1), where n is the length of the string.
Output
For each test case, print the I'th permuted string of the given string in a line. Look at Sample input and output for details.
Sample Input
4 ACB 2 ABC 1 ABC 6 ABCD 12Sample Output
CBA CBA ABC BACDAuthor : S. M. Shahed Nejhum
The Real Programmers' Contest-2題目描述：
按照這種插入順序，詢問第 I 個排列是什麼？
題目解法：
說實在，生成排列不是問題，但要快速找到第 I 個就比較困難，
中間使用計算得到窮舉第幾位時，後面會有多少的排列。
藉此剪枝忽略，但題目測資範圍很糟糕。
tricky case：
50
ABCDEFGHIJKLMNOPQRSTUVWXYZ
2147483647
my output：
SVRQXWPONMLKJIHTGFEDCBZAUY
很容易在計算上爆炸，估算的時候甚至會出現 26!/2! 就算 long long 也不夠。
估算有時候會比較大，不是計算過程中會溢位，本身答案就 overflow 了。
這裡借助 log 運算，雖然很不準，但是多少夠用了。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
char s[105], p[105];
int n, flag = 0;
long long f[50], rank, fff[50][50];
double ff[50];
void dfs(int idx) {
if(flag) return;
if(idx == n) {
p[idx] = '\0';
puts(p);
flag = 1;
return;
}
int i;
for(i = idx-1; i >= 0; i--)
p[i+1] = p[i];
p[0] = s[idx];
for(i = 0; i <= idx; i++) {
//printf("%lld %lld %lf %lf\n", rank, f[n]/f[idx+1], ff[n]-ff[idx+1], log(rank));
if(ff[n]-ff[idx+1] < log(rank)-(1e-9))
rank -= fff[idx+2][n];
else
dfs(idx+1);
swap(p[i], p[i+1]);
}
}
int main() {
int i, j, k;
for(i = 1; i < 30; i++)
ff[i] += ff[i-1] + log(i);
f[1] = f[0] = 1;
for(i = 2; i < 30; i++) {
f[i] = f[i-1]*i;
}
for(i = 0; i < 30; i++) {
for(j = i; j < 30; j++) {
fff[i][j] = 1;
for(k = max(i, 1); k <= j; k++)
fff[i][j] *= k;
}
fff[i+1][i] = 1;
}
int testcase;
scanf("%d", &testcase);
while(testcase--) {
scanf("%s %lld", s, &rank);
n = strlen(s);
flag = 0;
dfs(0);
}
return 0;
}
/*
4
ACB 2
ABC 1
ABC 6
ABCD 12
ABCDEFGHIJKLMNOPQRSTUVWXYZ
2147483647
*/