q****x
发帖数: 7404 | 1 比如123的排列有6个，按次序可以映射到0到5。那么函数f("321") = 5，f("132") = 1
，等等。
假设P是k个不同数字/字母的某个排列，求f(P)。
另外求f的逆函数。
应该是个经典题吧？ |
r****t
发帖数: 10904 | 2 做 bubble sort count 交换次数？ |
c****m
发帖数: 179 | 3 把阶乘当base。
这个是经典，搜索时候用于储存状态空间。但是感觉面试问这个算难的了。 |
q****x
发帖数: 7404 | 4 太慢。
【在 r****t 的大作中提到】
: 做 bubble sort count 交换次数？
|
q****x
发帖数: 7404 | 5 有参考链接吗？
【在 c****m 的大作中提到】
: 把阶乘当base。
: 这个是经典，搜索时候用于储存状态空间。但是感觉面试问这个算难的了。
|
H***e
发帖数: 476 | 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**********e
发帖数: 2007 | 7 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;
} |
c**********e
发帖数: 2007 | 8 index()的逆函数
void reverseIndex(long index, int a[], int n) {
long idx = index;
for(int i=0;i
int j=idx/factorial(n-i-1);
a[i]=j;
idx = idx % factorial(n-i-1);
}
} |
s******n
发帖数: 3946 | 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******n
发帖数: 3946 | 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; i
if (a[j]
factorial = factorial* (n-i-1);
idx+=rank*factorial;
}
return idx;
} |
h*****a
发帖数: 1718 | 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;
: }
|
