算法题：如何将排列映射到编码？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

算法题：如何将排列映射到编码？

算法题：如何将排列映射到编码？# JobHunting - 待字闺中

q*x2011-12-21 08:12

1 楼

比如123的排列有6个，按次序可以映射到0到5。那么函数f("321") = 5，f("132") = 1
，等等。
假设P是k个不同数字/字母的某个排列，求f(P)。
另外求f的逆函数。
应该是个经典题吧？

r*t2011-12-21 08:12

2 楼

做 bubble sort count 交换次数？

c*m2011-12-21 08:12

3 楼

把阶乘当base。
这个是经典，搜索时候用于储存状态空间。但是感觉面试问这个算难的了。

q*x2011-12-21 08:12

4 楼

太慢。

【在 r****t 的大作中提到】

: 做 bubble sort count 交换次数？

q*x2011-12-21 08:12

5 楼

有参考链接吗？

【在 c****m 的大作中提到】

: 把阶乘当base。
: 这个是经典，搜索时候用于储存状态空间。但是感觉面试问这个算难的了。

H*e2011-12-21 08:12

6 楼

就是算阶乘那个
假设要求第index=8的string（0 based, not 1)
abcd (4个) ,以a开头的有(4-1)!=6个，同理b/c/d/也是6个
8/6 = 1(所选的字母的位置) 8%6 = 2 (下一个index) 所以第一个字母是 b
然后recursion, 剩下 acd, (3-1)!=2 index=2, index/2= 1. index%2=0
所以第二个字母为c
剩下ad, (2-1)!=1, index=0, index/1=0, index%2 =0;
所以第三个字母为a
第四个字母为d
总体为bcad
同理，逆函数类似的idea.

【在 q****x 的大作中提到】

: 有参考链接吗？

c*e2011-12-21 08:12

7 楼

Suppose 排列 1, 2, ..., n is expressed as a[n].
long index(int a[], int n) {
long idx=0;
for(int i=0;iidx+=(a[i]-1)*factorial(n-1-i);
return idx;
}

c*e2011-12-21 08:12

8 楼

index()的逆函数
void reverseIndex(long index, int a[], int n) {
long idx = index;
for(int i=0;iint j=idx/factorial(n-i-1);
a[i]=j;
idx = idx % factorial(n-i-1);
}
}

s*n2011-12-21 08:12

9 楼

这个对吗？假设1,2,3,4，n=4

【在 c**********e 的大作中提到】

: Suppose 排列 1, 2, ..., n is expressed as a[n].
: long index(int a[], int n) {
: long idx=0;
: for(int i=0;i: idx+=(a[i]-1)*factorial(n-1-i);
: return idx;
: }

s*n2011-12-21 08:12

10 楼

long index(int a[], int n) {
long idx=0;
long factorial = 1;
for(int i=n-2;i>=0;i--) {
int rank = 0;
for (int j=i+1; iif (a[j]factorial = factorial* (n-i-1);
idx+=rank*factorial;
}
return idx;
}

h*a2011-12-21 08:12

11 楼

What if the numbers in the array are not unique?

【在 s******n 的大作中提到】

: long index(int a[], int n) {
: long idx=0;
: long factorial = 1;
: for(int i=n-2;i>=0;i--) {
: int rank = 0;
: for (int j=i+1; i: if (a[j]: factorial = factorial* (n-i-1);
: idx+=rank*factorial;
: }