全排列生成算法

✍ dations ◷ 2025-07-19 07:02:53 #算法

全排列的生成算法方法是将给定的序列中所有可能的全排列无重复无遗漏地枚举出来。此处全排列的定义是:从n个元素中取出m个元素进行排列,当n=m时这个排列被称为全排列。

字典序、邻位对换法、循环左移法、循环右移法、递增进位制法、递减进位制法都是常见的全排列生成算法。

字典序,就是将元素按照字典的顺序(a-z, 1-9)进行排列。以字典的顺序作为比较的依据,可以比较出两个串的大小。比如 "1" < "13"<"14"<"153", 就是按每个数字位逐个比较的结果。对于一个串“123456789”, 可以知道最小的串是“123456789”,而最大的串“987654321”。这样针对这个串以字典序法生成全排列生成全排列,就是依次生成“123456789”->“123456798”->......->"987654312"->"987654321"这样的串。字典序法要求这一个与下一个有尽可能长的共同前缀,也即变化限制在尽可能短的后缀上。

设P是集合{1,2,……n-1,n}的一个全排列:P=P1P2……Pj-1PjPj+1……Pn(1≤P1,P2,……,Pn≤n-1)

证明它可以生成所有的排列只需要证明生成的下一个排序恰好比当前排列大的一个序列即可。对于任意j,作为从右端开始第一个小于右边数字的数,可以得到序列Pj+1,...Pn是降序排列,选择其中大于Pj的最小的数字Pk,与其交换,然后再对后面排序得到序列P1,...Pj-1Pk...Pn,恰好比P1...Pj-1Pj...Pn大一点的下一个排列,因此算法可以生成全排列。

对于元素集合{1,2,3}按字典序生成的全排列是:123,132,213,231,312,321。

   // array必须是从小到大排好序的   boolean dictSeq(int array) {       // 从最右端开始第一个比右边小的位置       int j = -1;       for (int i=array.length-2; i>=0; i--) {           if (array < array) {               j = i;               break;           }       }       // 此时已经是最大序了       if (j == -1) {           System.out.println("end");           return false;       }       // j后边比j位置大的最小的一个位置       int k = -1;       int min = Integer.MAX_VALUE;       for (int i=j; i<array.length; i++) {           if (array > array && array <= min) { // 这里要找到最后一个,否则对于存在相同元素的集合会出现错误。如:0122               min = array;               k = i;           }       }       // 交换j和k的值       int tmp = array;       array = array;       array = tmp;       // 对j后边的序列进行反转       int left = j+1;       int right = array.length - 1;       while (left < right) {           int t = array;           array = array;           array = t;           left ++;           right --;       }       for (int i : array) {           System.out.print(i + ", ");       }       System.out.println();       return true;   }

插入法

如果已知n-1个元素的排列,将n插入到排列的不同位置,就得到了n个元素的排列。用这种方法可以产生出任意n个元素的排列。这个方法有一个缺点:为了产生n个元素的排列,我们必须知道并存储所有n-1个元素的排列,然后才能产生出所有n阶排列。

该算法由Johnson-Trotter首先提出,是一个能快速生成全排列的算法。它的下一个全排列总是上一个全排列对换某相邻两位得到的。

假设其对n个元素能生成全排列,只需要证明其对n+1个元素,也能生成全排列,对于新进来的元素,将其认为值最大,插入最右方,每次从右移到左,或者改变方向后从左移到右就可以认为对于一个排列从不同位置插入生成一个新的排列,而对于n个元素是全排列的,因此对于n+1个元素也是全排列的,因此邻位对换法能生成全排列。

这个算法是基于序列的递增进位制数。递增进位制数是指数字的进制随着位数的递增而递增。一般情况下,数字最右边的进制是2,次右边的进制是3,以此类推。n位递增进位制数一共包含n!个数字,所以它可以与全排列生成算法结合在一起。

由于在字典序法中由中介数求排列比较繁琐,可以通过另外定义递增进位制数加以改进。定义: i的右边比i小的数字的个数, 则()↑为递增进位制法中定义的中介数,这里的中介数是递增进位制数字。例如,839647521对应的中介数为(67342221) ↑。由中介数求排列时,从大到小根据求出n,n-1,…,2,1的位置——从右向左将第+1个空填上i,剩下的最后一个空位填上1。因此根据“原排列”→“原中介数”→“新中介数”→”新排列“,在这样的定义下,可以求出下一个排列。所以根据递增进位制法生成全排列步骤如下:

如果已经输出所有的排列——结束

对于一个给定的中介数,对应于一个唯一的排列,这里排列和中介数的一一对应性的证明我们不做讨论。m位(m为正整数)递增递减进位制数字有(m+1)!个,因此对于一个m位的中介数可能的取值有(m+1)!。又因为中介数与排列一一对应,所以由m位的中介数可以求出(m+1)!个排列。一个m位的中介数对应m+1个数字,m+1个不同元素的全排列有(m+1)!个。因此递增进位制法可以生成全排列。

该方法与递增进位制法的原理相似,不同的是它定义的“递减进位制数”是数字的进制随着位数的递增而递减。这种进制一般最左边的进制是2,次左边的进制是3。其余原理与递增进位制法基本相同。

在递增进位制数法中,中介数的最低位是逢2进1,进位频繁,这是一个缺点。把递增进位制数翻转,就得到递减进位制数。递减进位制数字是指数字的进制随着数字位置的不同递减。

定义: i的右边比i小的数字的个数, 则() ↓为递减进位制法中定义的中介数,这里的中介数是递减进位制数字,递减进位制数(a2 a3 a4 a5 a6 a7 a8 a9)为:最低位逢9进1,次低位逢8进1……。例如,839647521对应的中介数为(12224376)↓。由中介数求排列时,从大到小根据从大到小求出n,n-1,…,2,1的位置——从右向左将第+1个空填上i,剩下的最后一个空位填上1。因此根据“原排列”→“原中介数”→“新中介数”→”新排列“,在这样的定义下,可以求出下一个排列。所以根据递减进位制法生成全排列步骤如下:

对于一个给定的中介数,对应于一个唯一的排列,这里排列和中介数的一一对应性的证明我们不做讨论。m位(m为正整数)递减递减进位制数字有(m+1)!个,因此对于一个m位的中介数可能的取值有(m+1)!。又因为中介数与排列一一对应,所以由m位的中介数可以求出(m+1)!个排列。一个m位的中介数对应m+1个数字,m+1个不同元素的全排列有(m+1)!个。因此递减进位制法可以生成全排列。

由“原排列”→“原中介数”→“新中介数”→“新排列”的方式求解:

按照以上字典序法、递增进位制数、递减进位制数法和邻位对换法四种算法,分别求出 83674521 之前第 2015 个排列。

相关

  • 腔静脉腔静脉(拉丁语:Venae cavae)俗称的大静脉,分为上腔静脉与下腔静脉。腔静脉连结右心房。是体循环系统的一部分。左心室→主动脉→小动脉→组织微血管→小静脉→腔静脉(上、下腔静
  • 莱斯大学莱斯大学(英语:Rice University;威廉·马歇尔·莱斯大学于1912年开办,开办之初名为威廉·马歇尔·莱斯文学、科学与艺术发展学院)是座落于美国德克萨斯州休斯顿市的一所私立的研
  • 奥利-约翰·达尔奥利-约翰·达尔(挪威语:Ole-Johan Dahl,1931年10月12日-2002年1月29日),生于挪威曼达尔,著名计算机科学家,与克利斯登·奈加特共同创造了Simula,被认为是面向对象之父。因此贡献,他与
  • 合成钢肥粒铁(α-Fe) 针状肥粒铁(acicular α-Fe) 奥氏体(γ-Fe) 马氏体 波来铁(88%肥粒铁,12%碳化三铁) 变韧铁 粒滴斑铁(波来铁及渗碳体的共晶    混合物,含碳量4.3%) 碳化三铁(Fe3C) β铁
  • 毛里塔尼亚乌吉亚毛里塔尼亚乌吉亚(货币代码:MRU),简称乌吉亚,是毛里塔尼亚的法定货币。乌吉亚是世界上少数以五分之一而非十分之一作为辅币单位的货币种类。毛里塔尼亚乌吉亚于1973年开始流通,以
  • 唐灰蝶属Cramer, 有10种,详见正文。唐灰蝶属(Green-banded Blue,学名:)是灰蝶科眼灰蝶亚科中的一个属。分布在新几内亚和周围的岛屿至澳大利亚北部。物种会拟态灵灰蝶属的品种或其他出没
  • 奥伯特·弗里德里希·卑尔讷 (刑法学者)奥伯特·弗里德里希·卑尔讷(德语:Albert Friedrich Berner,1818年11月30日-1907年1月13日),是德国 19 世纪最重要的刑法学家之一,曾任柏林大学(今日的柏林洪堡大学)法学教授。他的学
  • 恩斯特·荣格恩斯特·荣格(德语:Ernst Jünger,1895年3月29日-1998年2月17日),德国军人、小说家、昆虫学家,以他的第一次世界大战回忆录《钢铁风暴》而广为人知。1895年3月29日生于德国海德堡,1
  • 阿列克谢·库德林阿列克谢·列昂尼多维奇·库德林(俄语:Алексей Леонидович Кудрин,1960年10月12日-),出生于拉脱维亚,俄罗斯政治人物。曾担任俄罗斯政府副总理、财政部长。
  • 锺相锺相(11世纪?-1130年),南宋初期洞庭湖地区民变领袖。原是荆湖北路鼎州(今湖南常德市)的一个小商人。北宋末年,锺相在洞庭湖一代传播一种巫教(可能是摩尼教),仿照王小波、李顺、提出“