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

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

  全排列的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));
}

 

 

 

 

转载于: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账号...

(0)


相关推荐

  • SVN 配置ip访问[通俗易懂]

    SVN 配置ip访问[通俗易懂]之前为了对visualsvnserver服务器进行IP访问控制配置,参考了http://blog.sina.com.cn/s/blog_6dc4dbed0100zass.html介绍的办法解决了这个问题最近svnserver准备升级到V3.7.1版本,发现之前的办法不好使了,启动就直接报错:invalidcommand’Order’,度娘了一把,原来是Apache版本变化导致的.最新…

  • IDEA汉化包汉化「建议收藏」

    IDEA汉化包汉化「建议收藏」IDEA汉化包,汉化教程

  • pycharm设置主题背景图片[通俗易懂]

    pycharm设置主题背景图片[通俗易懂]一、操作步骤1.双击shift出现搜索框,输入:setbackgroundimage;(或者通过设置路径:File|Settings|Appearance&Behavior|Appearance,选择BackgroundImage)2.选择你喜欢的背景图片上传;3.可通过opacity控件设置透明度image:输入背景图片路径opacity:设置透明度方框:选择图片样式…

  • vc中关于 directx的配置,和dxsdk_extras(directshow)

    vc中关于 directx的配置,和dxsdk_extras(directshow)

    2021年12月13日
  • oracle 表名拼接_oracle_根据表名拼装语句

    oracle 表名拼接_oracle_根据表名拼装语句1、—–批量删除用户下所有表数据——保留表结构eg:批量删除用户下的所有表数据SELECT’TRUNCATETALBE’||TABLE_NAME||’;’FROMUSER_TABLES;如果表中存在外键会报错,建议使用delete,然后再purgerecyclebin;(清空回收站操作)SELECT’DELETEFROM’||table_name||’…

  • Oracle 触发器写法

    Oracle 触发器写法createorreplacetriggert_after_user_copy–createorreplacetrigger触发器名称afterinsertorupdateordelete—时间after/before事件insertorupdateordeleteont_user—作用的表ontablenameFOREACHROW–指定是否对受影响的每行都执行触发器,即行级触发器,如果不使用此子句,则为语句级触发器.

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号