`
128kj
  • 浏览: 612003 次
  • 来自: ...
社区版块
存档分类
最新评论

全排列的Hash函数(JAVA)

阅读更多
我们经常使用的数的进制为“常数进制”,即始终逢p进1。例如,p进制数K可表示为
    K = a0*p^0 + a1*p^1 + a2*p^2 + ... + an*p^n (其中0 <= ai <= p-1),
它可以表示任何一个自然数。

   对于这种常数进制表示法,以及各种进制之间的转换大家应该是很熟悉的了,但大家可能很少听说变进制数。

这里介绍一种特殊的变进制数,它能够被用来实现全排列的Hash函数,并且该Hash函数能够实现完美的防碰撞和空间利用(不会发生碰撞,且所有空间被完全使用)。这种全排列Hash函数也被称为全排列数化技术。


一、变进制数:

我们考查这样一种变进制数:第1位逢2进1,第2位逢3进1,……,第n位逢n+1进1。它的表示形式为
    K = a1*1! + a2*2! + a3*3! + ... + an*n! (其中0 <= ai <= i),
也可以扩展为如下形式(因为按定义a0始终为0),以与p进制表示相对应:
    K = a0*0! + a1*1! + a2*2! + a3*3! + ... + an*n! (其中0 <= ai <= i)。
(后面的变进制数均指这种变进制数,且采用前一种表示法)

例:十进数     变进制数     十进制
    0     =         0   =    0
    1     =         1   =   1*1!
    2     =        10   =   1*2!+0*1!
    3     =        11   =   1*2!+1*1!
    4     =        20   =   2*2!+0*1!
    5     =        21   =   2*2!+1*1!
    6     =       100   =   1*3!+0*2!+0*1!
    7     =       101   =   1*3!+0*2!+1*1!
    8     =       110   =   1*3!+1*2!+0*1!
    9     =       111   =   1*3!+1*2!+1*1!
   10     =       120   =   1*3!+2*2!+0*1!
   11     =       121   =   1*3!+2*2!+1*1!
   12     =       200   =   2*3!+0*2!+0*1!
  
先让我们来考查一下该变进制数的进位是否正确。假设变进制数K的第i位ai为i+1,需要进位,而ai*i!=(i+1)*i!=1*(i+1)!,
即正确的向高位进1。这说明该变进制数能够正确进位,从而是一种合法的计数方式。 


二、n位变进制数K的性质:
(1)当所有位ai均为i时,此时K有最大值
    MAX[K] = 1*1!+2*2!+3*3!+...+ n*n!
           = 1!+1*1!+2*2!+3*3!+...+n*n!-1
           = (1+1)*1!+2*2!+3*3!+...+n*n!-1
           = 2!+2*2!+3*3!+...+n*n!-1
           =(1+2)*2!+3*3!+...+n*n!-1
           = 3!+3*3!+...+n*n!-1
             ..................
           = (n+1)!-1
    因此,n位变进制数的最大值为(n+1)!-1。

(2)当所有位ai均为0时,此时K有最小值0。
因此,n位变进制数能够表示0到(n+1)!-1的范围内的所有自然数,共(n+1)!个。
如:8位变进制数能表示0到(9!-1)内的所有自然数,有9!个.


三、全排列的Hash函数:

  在一些状态空间搜索算法中,我们需要快速判断某个状态是否已经出现,此时常常使用Hash函数来实现。
其中,有一类特殊的状态空间,它们是由全排列产生的,比如N数码问题。对于n个元素的全排列,共产生n!个不同的排列或状态。
下面将讨论如何使用这里的变进制数来实现一个针对全排列的Hash函数。

   从数的角度来看,全排列和变进制数都用到了阶乘。如果我们能够用0到n!-1这n!个连续的变进制数来表示n个元素的所有排列,
那么就能够把全排列完全地数化,建立起全排列和自然数之间一一对应的关系,也就实现了一个完美的Hash函数。
那么,我们的想法能否实现呢?答案是肯定的,下面将进行讨论。

假设我们有b0,b1,b2...bn 共 n+1 个不同的元素,假设各元素之间有一种次序关系b0 < b1 < b2 ...< bn。对它们进行全排列,
共产生(n+1)!种不同的排列。对于产生的任一排列 c0,c1,c2,..,cn,其中第i个元素ci(1 <= i <= n)与
它前面的i个元素构成的逆序对的个数为di(0 <= di <= i),那么我们得到一个逆序数序列d1,d2,...,dn(0 <= di <= i)。
这不就是前面的n位变进制数的各个位么?于是,我们用n位变进制数M来表示该排列:
   M = d1*1! + d2*2! + ... + dn*n!
因此,每个排列都可以按这种方式表示成一个n位变进制数。下面,我们来考查n位变进制数能否与n+1个元素的全排列建立起一一对应的关系。

由于n位变进制数能表示(n+1)!个不同的数,而n+1个元素的全排列刚好有(n+1)!个不同的排列,
且每一个排列都已经能表示成一个n位变进制数。如果我们能够证明任意两个不同的排列产生两个不同的变进制数,那么我们就可以得出结论:

定理:
   n+1个元素的全排列的每一个排列对应着一个不同的n位变进制数。

证明:
   对于全排列的任意两个不同的排列p0,p1,p2,...,pn(排列P)和q0,q1,q2,...,qn(排列Q),
从后往前查找第一个不相同的元素,分别记为pi和qi(0 < i <= n)。
(1)如果qi > pi,那么,
     如果在排列Q中qi之前的元素x与qi构成逆序对,即有x > qi,则在排列P中pi之前也有相同元素x > pi(因为x > qi且qi > pi),
即在排列P中pi之前的元素x也与pi构成逆序对,所以pi的逆序数大于等于qi的逆序数。又qi与pi在排列P中构成pi的逆序对,
所以pi的逆序数大于qi的逆序数。
(2)同理,如果pi > qi,那么qi的逆序数大于pi的逆序数。
因此,由(1)和(2)知,排列P和排列Q对应的变进制数至少有第i位不相同,即全排列的任意两个不同的排列具有不同的变进制数。
至此,定理得证。


四、计算k个元素的一个全排列对应的变进制数的算法(hash函数)
public class Test{
  //1!=1;2!=2;3!=6;4!=24;5!=120;6!=720...
  static int fac[] = {1,2,6,24,120,720,5040,40320};

  static int hash(int num,int k){num是K个元素的一个全排列
    int  n[]=new int[k];
    for(int i = k-1; i >=0; i--){
        n[i] = num % 10;
        num /= 10;
    }
   
    int key = 0;
    int c;
    for(int i = 1; i <k; i++){
         c=0;
     for(int j = 0; j < i; j++)
         if(n[j] > n[i]) c++;
     key += c * fac[i-1];
    }
    return key;
}

static int hash(String s,int k){// s是k个不同元素(数字)的一个全排列。
    int  n[]=new int[k];
    for(int i = k-1; i >=0; i--){
        int num=s.charAt(i)-48;
        n[i] = num % 10;
        num /= 10;
    }
   
    int key = 0;
    int c;
    for(int i = 1; i <k; i++){
         c=0;
     for(int j = 0; j < i; j++)
         if(n[j] > n[i]) c++;
     key += c * fac[i-1];
    }
    return key;
}
  
  public static void main(String[] args){
    int a[]={123,132,213,231,312,321};
    for(int i=0;i<a.length;i++)
      System.out.println(hash(a[i],3));

      System.out.println(hash("012345678",9));
       System.out.println(hash("876543210",9));
         System.out.println(hash(876543210,9));
 }
    
   }



运行:
D:\java>java   Test
0
2
1
4
3
5
0
362879
362879
分享到:
评论

相关推荐

    Java程序员拼多多3轮面试.pdf,这是一份不错的文件

    5. 全排列算法:实现一个生成所有排列组合的函数,通常用回溯法或递归。 6. B树和B+树:数据库索引中的数据结构,B+树更适合范围查询。 7. Hash解决冲突:开放寻址法、链地址法等。 8. 进程间通信:了解共享内存、...

    程序员编程艺术--共二十七章-集锦与总结(教你如何编程)

    - **第十六~第二十章:全排列,跳台阶,奇偶排序,第一个只出现一次等问题** - 覆盖组合数学中的经典问题。 - 包括不同问题的求解策略和代码示例。 - **第二十一~二十二章:出现次数超过一半的数字,最短摘要的...

    基于Simulink的风火水储联合调频系统中储能SOC对ACE影响的技术分析

    内容概要:本文详细探讨了在Simulink环境中构建的风火水储联合调频系统中,储能系统的荷电状态(SOC)对区域控制偏差(ACE)的影响。文中通过具体案例和MATLAB代码展示了储能系统在不同SOC水平下的表现及其对系统稳定性的作用。同时,文章比较了储能单独调频与风火水储联合调频的效果,强调了储能系统在应对风电波动性和提高系统响应速度方面的重要作用。此外,作者提出了针对SOC变化率的参数整定方法以及多电源协同工作的优化策略,旨在减少ACE波动并确保系统稳定运行。 适合人群:从事电力系统调频研究的专业人士,尤其是熟悉Simulink仿真工具的研究人员和技术人员。 使用场景及目标:适用于希望深入了解储能系统在电力系统调频中作用的研究者和技术人员,目标是通过合理的SOC管理和多电源协同工作,优化调频效果,提高系统稳定性。 其他说明:文章提供了详细的MATLAB代码片段,帮助读者更好地理解和应用所讨论的概念。同时,文中提到的实际案例和仿真结果为理论分析提供了有力支持。

    欧姆龙PLC NJ中大型程序案例:结构化与面向对象编程的深度融合及应用

    内容概要:本文深入探讨了欧姆龙PLC NJ系列中大型程序中结构化编程与面向对象编程的结合及其应用。首先介绍了结构化编程作为程序框架的基础,通过功能块(FB)实现清晰的程序结构和流程控制。接着阐述了面向对象编程的理念,将现实世界的对象映射到程序中,利用类的概念实现模块化和可扩展性。两者结合提高了程序的容错率,增强了程序的稳定性和可维护性。文中通过多个实际案例展示了如何在工业自动化领域中应用这两种编程方法,如电机控制、设备类的创建、异常处理机制、接口实现多态性、配方管理和报警处理等。 适合人群:从事工业自动化领域的工程师和技术人员,尤其是那些希望提升PLC编程技能的人群。 使用场景及目标:适用于需要优化PLC程序结构、提高程序可靠性和可维护性的场合。目标是帮助工程师掌握结构化编程和面向对象编程的技巧,从而写出更加高效、稳定的PLC程序。 其他说明:文章强调了在实际项目中灵活运用两种编程方法的重要性,并提醒读者注意实时性要求高的动作控制应采用结构化编程,而工艺逻辑和HMI交互则更适合面向对象编程。

    matlab与聚类分析

    matlab与聚类分析。根据我国历年职工人数(单位:万人),使用有序样品的fisher法聚类。

    卡尔曼滤波生成航迹测量程序

    卡尔曼滤波生成航迹测量程序

    基于格子玻尔兹曼方法(LBM)的多孔电极浸润特性研究及其Python实现

    内容概要:本文详细介绍了利用格子玻尔兹曼方法(LBM)对多孔电极浸润特性的模拟研究。首先阐述了LBM的基本原理,包括碰撞和迁移两个关键步骤,并提供了相应的Python伪代码。接着讨论了如何处理多孔介质中的固体边界,特别是通过随机算法生成孔隙结构以及结合CT扫描数据进行三维重构的方法。文中还探讨了表面张力、接触角等因素对浸润过程的影响,并给出了具体的数学表达式。此外,文章提到了并行计算的应用,如使用CUDA加速大规模网格计算,以提高模拟效率。最后,作者分享了一些实用技巧,如通过调整松弛时间和润湿性参数来优化模拟效果,并强调了LBM在处理复杂几何结构方面的优势。 适合人群:从事电池研发、材料科学领域的研究人员和技术人员,尤其是关注多孔电极浸润性和电解液扩散机制的人群。 使用场景及目标:适用于希望深入了解多孔电极内部流体动力学行为的研究者,旨在帮助他们更好地理解和预测电极材料的浸润特性,从而改进电池设计和性能。 其他说明:尽管LBM在处理多孔介质方面表现出色,但在某些极端条件下仍需引入额外的修正项。同时,参数的选择和边界条件的设定对最终结果有着重要影响,因此需要谨慎对待。

    基于FPGA和W5500的TCP网络通信:Zynq扩展口开发测试平台(使用Vivado 2019.2纯Verilog实现)

    内容概要:本文详细介绍了在Zynq扩展口上使用FPGA和W5500实现TCP网络通信的过程。作者通过一系列实验和技术手段,解决了多个实际问题,最终实现了稳定的数据传输。主要内容包括:硬件搭建(SPI接口配置)、数据回环处理、压力测试及优化、多路复用扩展以及上位机测试脚本的编写。文中提供了大量Verilog代码片段,展示了如何通过状态机控制SPI通信、优化数据缓存管理、处理中断等问题。 适合人群:对FPGA开发和网络通信感兴趣的工程师,尤其是有一定Verilog编程基础的研发人员。 使用场景及目标:适用于需要在嵌入式系统中实现高效、稳定的TCP通信的应用场景。目标是帮助读者掌握FPGA与W5500结合进行网络通信的具体实现方法和技术细节。 其他说明:文章不仅提供了详细的代码实现,还分享了许多实践经验,如硬件连接注意事项、信号完整性问题的解决方案等。此外,作者还提到了未来的工作方向,如UDP组播和QoS优先级控制的实现。

    python3.10以上 可安装pyside6(类似pyqt),具体安装操作步骤

    python3.10以上 可安装pyside6(类似pyqt),具体安装操作步骤

    基于FDTD仿真的可调谐石墨烯超材料吸收体设计与实现

    内容概要:本文详细介绍了利用有限差分时域法(FDTD)进行可调谐石墨烯超材料吸收体的设计与仿真。文中解释了石墨烯超材料的基本结构(三层“三明治”结构)、关键参数(如化学势、周期、厚度等)及其对吸收性能的影响。同时展示了如何通过调整石墨烯的化学势来实现吸收峰的位置和强度的变化,以及如何优化结构参数以获得最佳的吸收效果。此外,还提供了具体的代码示例,帮助读者理解和重现相关实验结果。 适合人群:从事纳米光子学、超材料研究的专业人士,尤其是对石墨烯基超材料感兴趣的科研工作者和技术开发者。 使用场景及目标:适用于希望深入了解石墨烯超材料的工作原理及其潜在应用场景的研究人员;旨在探索新型可调谐光学器件的设计思路和发展方向。 其他说明:文中不仅分享了理论知识,还包括了许多实践经验,如避免常见错误、提高仿真相关效率的小技巧等。对于想要将研究成果应用于实际产品的团队来说,这些细节非常有价值。

    随机生成2字到10字的中文词组

    随机生成2字,3字,4字,5字,6字,7字,8字,9字,10字的中文词组20个

    【汽车电子电气架构】智能座舱域控平台设计:基于双片龍鷹一号SoC芯片的高性能硬件架构与多模态交互系统构建

    内容概要:本文详细探讨了智能座舱域控设计的发展历程和技术趋势。首先介绍了智能座舱从被动式交互到主动式交互的技术演变,包括硬件和交互方式的进步。随后,文章重点讨论了智能座舱功能发展趋势,涵盖车载显示技术的多屏化、大屏化和高端化,以及SoC芯片的多核异构架构和算力融合,强调了其在智能座舱中的核心作用。此外,还阐述了电子电气架构从分布式向集成化的转型,分析了其面临的挑战和未来趋势。最后,基于当前智能座舱的发展需求,提出了一种基于双片龍鷹一号芯片的新域控平台设计方案,详细描述了其硬件设计实现方案,旨在提供高性能、高可靠性的智能座舱解决方案。 适合人群:汽车电子工程师、智能座舱研发人员及相关领域的技术人员。 使用场景及目标:①帮助读者理解智能座舱的技术发展历程及其未来发展方向;②为智能座舱域控平台的设计和开发提供参考和技术支持;③探讨电子电气架构的转型对汽车行业的影响及应对策略。 其他说明:文章结合实际案例和技术数据,深入浅出地解释了智能座舱的各项技术细节,不仅提供了理论指导,还具有较强的实践意义。通过对智能座舱域控平台的全面剖析,有助于推动智能座舱技术的创新发展,提升用户体验。

    多智能体协同编队控制:无人机编队背后的Python实现与关键技术解析

    内容概要:本文详细介绍了多智能体协同编队控制的技术原理及其应用实例。首先通过生动形象的例子解释了编队控制的核心概念,如一致性算法、虚拟结构法和Leader-Follower模式。接着深入探讨了如何用Python实现基础的一致性控制,以及如何通过调整参数(如Kp、Ka)来优化编队效果。文中还讨论了实际工程中常见的问题,如通信延迟、避障策略和动态拓扑变化,并给出了相应的解决方案。最后,强调了参数调试的重要性,并分享了一些实用技巧,如预测补偿、力场融合算法和分布式控制策略。 适合人群:对多智能体系统、无人机编队控制感兴趣的科研人员、工程师和技术爱好者。 使用场景及目标:适用于希望深入了解多智能体协同编队控制理论并能够将其应用于实际项目的研究人员和开发者。目标是帮助读者掌握编队控制的关键技术和实现方法,提高系统的稳定性和可靠性。 其他说明:文章不仅提供了详细的理论讲解,还附有具体的代码示例,便于读者理解和实践。同时,作者结合自身经验分享了许多宝贵的调试技巧和注意事项,有助于读者在实际应用中少走弯路。

    评估管线钢环焊缝质量及其对氢脆的敏感性.pptx

    评估管线钢环焊缝质量及其对氢脆的敏感性.pptx

    C盘清理bat脚本自动清理C盘垃圾文件

    C盘清理bat脚本自动清理C盘垃圾文件

    GBT21266-2007 辣椒及辣椒制品中辣椒素类物质测定及辣度表示方法

    GBT21266-2007 辣椒及辣椒制品中辣椒素类物质测定及辣度表示方法

    弹跳球 XNA 游戏项目 演示如何使用 C# 在 Visual Studio XNA 中构建类似 arkanoiddx-ball 的游戏

    弹跳球 XNA 游戏项目。演示如何使用 C# 在 Visual Studio XNA 中构建类似 arkanoiddx-ball 的游戏。

    【人形机器人领域】宇树科技人形机器人:技术实力、市场炒作与应用前景分析

    内容概要:文章全面解析了宇树科技人形机器人的发展现状、技术实力、市场炒作现象及其应用前景和面临的挑战。宇树科技成立于2016年,凭借春晚舞台的惊艳亮相和社交媒体的热议迅速走红,其人形机器人具备先进的运动控制算法、传感器技术和仿生结构设计。然而,市场炒作现象如高价租赁、二手市场炒作和虚假宣传等影响了市场秩序。尽管存在炒作,人形机器人在工业、服务和家庭领域仍具广阔前景,但也面临技术升级、成本控制、安全性和政策监管等挑战。 适合人群:对机器人技术、人工智能以及科技发展趋势感兴趣的读者,包括科技爱好者、投资者和相关行业的从业者。 使用场景及目标:①帮助读者了解宇树科技人形机器人的技术特点和发展历程;②揭示市场炒作现象及其影响;③探讨人形机器人的应用前景和面临的挑战。 其他说明:文章强调了宇树科技人形机器人在技术上的突破和市场上的表现,同时也提醒读者关注市场炒作现象带来的风险,呼吁各方共同努力推动人形机器人产业健康发展。

    msvcp140.dll

    msvcp140.dll丢失怎样修复

Global site tag (gtag.js) - Google Analytics