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)


相关推荐

  • 指纹解锁特效怎么做?2022最简单的教程来咯「建议收藏」

    指纹解锁特效怎么做?2022最简单的教程来咯「建议收藏」在视频模板的制作过程中我们是有机会用到手机解锁的动效的,AE怎么制作手机解锁动效呢?今天就来跟大家分享一波BeardChicken大神制作的极具炫酷以及科技感的手机解AE制作手机解锁动效教程1.在绘图软件中画好背景、指纹图标以及指纹上方的圆圈,将其导入到AE中,指纹和圆圈生成合成,然后将指纹解锁的光效也导入到AE中,并调整其位置缩放后调整到指纹上层;2.打开[展开“转换控制”窗格]和[展开“入点”“出点”“持续时间”“伸缩”窗格],降低[持续时间],勾选[剪切蒙版];.

  • 智能家居急速扩容 企业标准各异

    智能家居急速扩容 企业标准各异

  • django 聚合函数_sql聚合函数的用法

    django 聚合函数_sql聚合函数的用法前言orm模型中的聚合函数跟MySQL中的聚合函数作用是一致的,也有像Sum、Avg、Count、Max、Min,接下来我们逐个介绍聚合函数所有的聚合函数都是放在django.db.models

  • latex中参考文献怎么弄进去_论文中的参考文献怎么标注右上角

    latex中参考文献怎么弄进去_论文中的参考文献怎么标注右上角参考文献常见问题集1.请问如何将参考文献的计算器置零,然后再计数,格式大致是这样:1文12文2…1文12文2我是这样实现的:beginthebibliography99endthebibliography……beginthebibliography9999endthebibliography我的文本实在ScienticWorkplace中编辑的,建议你也使用这个软件,很…

  • 商用技术的均衡架构:联想CEMS

    商用技术的均衡架构:联想CEMS

  • 提升效率的秘密,仅需这一篇吃透负载均衡

    提升效率的秘密,仅需这一篇吃透负载均衡写在前面写本文的目的: 对负载均衡的理解零零散散,不成体系。 阅读这篇文章需要的条件: 对OSI模型有些许了解 有耐心。本文涉及大量的知识点,且只能用文字才能讲清楚,所以文字比较多。 收获: 读完此篇文章,从宏观的角度理解了负载均衡的原理以及实现机制。加深对分布式架构的了解 主要内容: 本文首先从概念开始,讲解什么是负载均衡,以及负载均衡在分布式系统中所承担的角色以及提供的功能。 讲解负载均衡的分类。分别从软硬件角度、地域范围角度以及…

发表回复

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

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