全排列的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));
}
<
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
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/110617.html原文链接：https://javaforall.net
![phpstorm2021.5.1激活码[在线序列号]「建议收藏」](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450-480x300.jpg)
