全排列生成算法-展示頁(yè)
2024-08-19 14:16本頁(yè)面
【正文】 n 將這部分排列倒轉(zhuǎn)i = i + 1If i = j Then Exit ForSwap p(i), p(j)NextOutL p 39。 找出遞減子序列NextSwap p(i), p(j) 39。 839651247所以839647521的下一個(gè)排列是839651247。 839647521在該數(shù)字后的數(shù)字中找出比4大的數(shù)中最小的一個(gè)5 從它生成下一個(gè)排列的步驟如下： 自右至左找出排列中第一個(gè)比右邊數(shù)字小的數(shù)字4 =p1p2.....pj1pjpn.....pk+1pkpk1.....pj+1，這就是排列p的下一個(gè)下一個(gè)排列。按照這樣的規(guī)定，5個(gè)數(shù)字的所有的排列中最前面的是12345，最后面的是 54321。全排列的生成法通常有以下幾種：字典序法遞增進(jìn)位數(shù)制法遞減進(jìn)位數(shù)制法鄰位交換法n進(jìn)位制法遞歸類算法字典序法中，對(duì)于數(shù)字3......n的排列，不同排列的先后關(guān)系是從左到右逐個(gè)比較對(duì)應(yīng)的數(shù)字的先后來決定的。所有的排列中除最后一個(gè)排列外，都有一個(gè)后繼；除第一個(gè)排列外，都有一個(gè)前驅(qū)。任何n個(gè)字符集的排列都可以與1～n的n個(gè)數(shù)字的排列一一對(duì)應(yīng)，因此在此就以n個(gè)數(shù)字的排列為例說明排列的生成法。不過在說別人的同時(shí)我也知道，自己寫的也不夠好，不過這就是我的理解了，沒法子寫的再細(xì)了。求839647521的下一個(gè)排列1. 確定i，從左到右兩兩比較找出后一個(gè)數(shù)比前一個(gè)大的組合，在這里有39 47，然后i取這些組中最到的位置號(hào)（不是最大的數(shù)）在這兩組數(shù)中7的位置號(hào)最大為6，所以i=， 找出在i（包括i）后面的所有比i前面那一位大的數(shù)的最大的位置號(hào)，在此例中7，5 都滿足要求，則選5，5的位置號(hào)為7，所以算法: 由 P1P2…Pn 生成的下一個(gè)排列的算法如下:1. 求 i=max{j| Pj1Pj}2. 求 l=max{k| Pi1Pk }3.1—9的排列最前面的是123456789，最后面的是987654321，從右向左掃描若都是增的，就到了987654321，也就沒有下一個(gè)了。/*例*/生成給定全排列的下一個(gè)排列所謂一個(gè)全排列的下一個(gè)排列就是這一個(gè)排列與下一個(gè)排列之間沒有其他的排列。注意/*例全排列的生成算法對(duì)于給定的字符集，用有效的方法將所有可能的全排列無重復(fù)無遺漏地枚舉出來。字典序法按照字典序求下一個(gè)排列的算法字符集{1,2,3},較小的數(shù)字較先,這樣按字典序生成的全排列是:123,132,213,231,312,321。一個(gè)全排列可看做一個(gè)字符串，字符串可有前綴、后綴。這就要求這一個(gè)排列與下一個(gè)排列有盡可能長(zhǎng)的共同前綴，也即變化限制在盡可能短的后綴上。839647521是1—9的排列。否則找出第一次出現(xiàn)下降的位置。交換Pi1 與Pl得到P1P2…Pi1 (P i....Pn ) , 將紅色部分順序逆轉(zhuǎn),得到結(jié)果. 例l=73. 先將4和5交換，然后將5后的四位數(shù)倒轉(zhuǎn)得到結(jié)果 839657421224。839651247以上算法是在數(shù)論課上老師給出的關(guān)于字典序全排列的生成算法，以前也經(jīng)常要用到全排列生成算法來生成一個(gè)全排列對(duì)所有的情況進(jìn)行測(cè)試，每次都是現(xiàn)到網(wǎng)上找一個(gè)算法，然后直接copy代碼，修改一下和自己的程序兼容就行了，也不看是怎么來的，不是我不想看，實(shí)在是說的很抽象，那一大堆公式來嚇人，一個(gè)實(shí)例都不給，更有甚者連算法都沒有，只是在那里說，想看都看不懂，也沒那個(gè)耐心取理解那些人寫出來的那種讓人無法忍受的解釋。全排列的生成算法2008年04月25日 星期五 下午 03:23全排列的生成算法就是對(duì)于給定的字符集，用有效的方法將所有可能的全排列無重復(fù)無遺漏地枚舉出來。n個(gè)字符的全體排列之間存在一個(gè)確定的線性順序關(guān)系。每個(gè)排列的后繼都可以從 它 的前驅(qū)經(jīng)過最少的變化而得到，全排列的生成算法就是從第一個(gè)排列開始逐個(gè)生成所有的排列的方法。例如對(duì)于5個(gè)數(shù)字的排列 12354和12345，排列12345在前，排列12354在后。字典序算法如下：設(shè)P是1～n的一個(gè)全排列:p=p1p2......pn=p1p2......pj1pjpj+1
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1