1到n全排列的hash函数（o(n)）

全栈程序员-站长 • 2021年8月11日下午4:00 • 未分类 • 阅读 64

全排列的hash函数，可以利用N位变进制，一般做法是用逆序数，但时间复杂度比较大。

设n位变进制数M，+i位逢i+1进一，显然M可表示的数的范围为[0, n!)共n!个

要生成n个数的排列，可以先从n个数挑一个，再从剩下的n-1个数挑一下，如此反复n次。

若最初的n个数是 0,1,2 … n-1，第一次挑选的数是t，则可以将t放入到M的n-1位，
若第二次挑选的数是m，则 0 <= r <= n-1 且 r != t，当r等于n-1时，
不能将r放入到M的n-2位（可以放的最大数为n-2），但是注意到r值不可能为t，
该情况下将它的值改为t，得到的新r值肯定小等于n-2，因而可放入到M的n-2位。

重复上面的处理，最终得到的M值与排列是一一对应的。

#include
<
algorithm
>

#include
<
cstdio
>

#include
<
cassert
>

//
template<int n>

//
struct Factorial { enum { v = Factorial<n – 1>::v * n}; };

//

//
template<> struct Factorial<0> { enum { v = 1}; };

//

//
static const int Max_n = 12;

//
static const int factorial[Max_n] = {
//
0! 1! 2! .. 11!   12!= 4.8e8

//
  Factorial<0>::v, Factorial<1>::v, Factorial<2>::v,

//
  Factorial<3>::v, Factorial<4>::v, Factorial<5>::v,

//
  Factorial<6>::v, Factorial<7>::v, Factorial<8>::v,

//
  Factorial<9>::v, Factorial<10>::v, Factorial<11>::v,

//
};

static
inline
bool
init_factorial(
int
arr[],
int
len)
{


for
(
int
i
=

0
, k
=

1
; i
<
len; k
*=

++
i) arr[i]
=
k;
//
arr[i]为i!


return

true
;
}

int
hash_permutation(
int
arr[],
const

int
len)
{


static

const

int
Max_n
=

12
;
//
12!= 4.8e8


static

int
factorial[Max_n];

static

bool
tmp
=
init_factorial(factorial, Max_n);
  (
void
)tmp;
  assert(len
>=

1

&&
len
<=
Max_n);

//
mapped[i]记录数i最终被映射到哪个数字，index[i]记录数i在mapped数组中的位置


int
mapped[Max_n], index[Max_n];

for
(
int
i
=

0
; i
<
len;
++
i) mapped[i]
=
index[i]
=
i;


int
ret
=

0
;

//
设变进制数M的+i位为（i+1）进制。从高位到低位放入数字


for
(
int
i
=
len
–

1
; i
>

0
;
—
i) {
    assert(arr[i]
>=

0

&&
arr[i]
<
len);

int
k
=
mapped[arr[i]];
//
mapped数组中所有的数是0,1, 2, … i的一个排列，

    ret
+=
k
*
factorial[i];
//
因而可以将数字k放到变进制数M的+i位



int
idx
=
index[i];
//
将k从mapped数组中删除，删除k前

    mapped[idx]
=
k;
//
先将mapped数组中最大的数（也就是i）映射到k，

    index[k]
=
idx;
//
保证删除k后剩下的数恰好是0,1,2 … i-1的一个排列

  }

return
ret;
}

int
main()
{


const

int
N
=

4
;

int
arr[N];

for
(
int
i
=

0
; i
<
N;
++
i) arr[i]
=
i;

int
count
=

0
;

do
{

    printf(
“
%3d:
“
,
++
count);

for
(
int
i
=

0
; i
<
N;
++
i) printf(
“
%2d
“
, arr[i]);
    printf(
“
  %6d\n
“
, hash_permutation(arr, N));
  }
while
(std::next_permutation(arr, arr
+
N));
}