全排列的hash函数,可以利用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值与排列是一一对应的。
<
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));
}
转载于:https://www.cnblogs.com/flyinghearts/archive/2011/05/08/2040612.html
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/110617.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...