全配列問題の概要

全配列問題の概要
1.5全配列の生成アルゴリズム全配列の生成アルゴリズムは、与えられた文字セットに対して、有効な方法で可能なすべての全配列を重複なく列挙することである.
ここでは全配列アルゴリズムの4つを紹介する:(A)辞書順法(B)増分進位制数法(C)漸減進位制数法(D)隣接位対換法
1.5.1辞書順序法は与えられた文字セットの文字に対して一つの前後関係を規定し、その上で二つの全配列の前後は左から右まで一つ一つ対応する文字の前後であることを規定する.
[例]文字セット{1,2,3}は、小さい数字が先であり、辞書順に生成される全配列は、1231,322,323,313,12321である.
[注意]全配列は文字列と見なすことができ、文字列には接頭辞、接尾辞があります.
1)所与の全配列を生成する次の配列所与の次の配列所与の次の配列所与の次の配列所与の次の配列所与の次の配列所与の次の配列所与の次の配列所与の列これは、次の可能な限り長い共通接頭辞、すなわち、変化が可能な限り短い接尾辞に制限されることを要求する.
[例]839647521は、1〜9の配列である.1-9の配列の一番前は123456789で、一番後ろは987654321で、右から左にスキャンしても増加すれば、987654321に着いて、次はありません.そうでなければ、初めて下降した位置を見つけます./
1.5.2逓増ビット制数法1)配列から仲介数を求める
辞書の順序法では、仲介数の各位は配列数のビットによって決まる.仲介数ビットの下付き文字は、配列されたビットの下付き文字と一致する.インクリメントビット制数法では,仲介数の各位は配列中の数字によって決定される.すなわち,仲介数における各位の下付き文字は配列中の数字(2−n)と一致する.n−1ビットのキャリーチェーンが見られる.右端位逢2進1,右から第2位逢3進1,...,右から第i位逢i+1進1,i=1,2,...,n-1.このような仲介数をインクリメントビット制数と呼ぶ.上は仲介数で並べ替えられています.
シーケンス番号(10進数)から仲介数(増分進数)を求めると、m=m 1,0≦m≦n!-1 m1=2m2+kn-1,0≤kn-1≤1 m2=3m3+kn-2,0≤kn-2≤2 …………… mn-2=(n-1)mn-1+k2,0≤k2≤n-2 mn-1=k1,0≤k1≤n-1 p1p2…pn←→(k1k2…kn-1)↑←→m
辞書シーケンス法では仲介数から配列を求めるのが面倒であり,増分ビット制数を別途定義することで改善できる.
便宜上、ai+1=kn-1,i=1,2,...,n-1(k 1 k 2...kn-1)↑=(anan-1...a 2)↑ai:iの右側がiより小さい数字の個数をこのような定義で839647521←→(67342221)↑(67342221)↑+1=(67342300)↑←→849617523 6×8+7)×7+3)×6+4)×5+2)×4+2)×3+2)×2+1 =279905
(anan-1...a 2)↑からp 1 p 2...pnを求める.
大きいから小さいまでn,n-1,...,2,1の位置を求める
_ ... _ n _ _ …_ (an個のスペース)nの右側にan個のスペースがあります.n-1の右側にはan-1個のスペースがあります.......2の右側にa 2個のスペースがあります.最後のスペースは1の位置です.
1.5.3漸減進位制数法増分進位制数法では、仲介数の最低位が2進1に当たり、進位が頻繁であることが欠点である.インクリメンタルキャリー数を反転すると、インクリメンタルキャリー数が得られる.
(anan-1…a2)↑→(a2a3…an-1an)↓ 839647521→ (12224376)↓
(12224376)↓=1×3+2)×4+2)×5+2)×6+4)×7+3)×8+7)×9+6=340989[注意]次の配列を求めるのはとても簡単です
1.5.4隣位対換法減衰進位制数法の仲介数進位は頻繁ではなく、次の配列が進位しない場合に容易であることを求める.これは,次の配列が常に隣接する2ビットの置換で得られるアルゴリズムを設計できるかどうかを示唆する.減算ビット数のシフトは一方向であり,右から左であり,隣接ビット対シフト法のシフトは双方向である.
このアルゴリズムは、1〜n−1の各偶数配列に対して、nが右から左にn個のニュートラル(両端を含む)を挿入し、1〜nのn個の配列を生成することを記述することができる.1−n−1の各奇数配列に対して、nは左から右にn個のニュートラルを挿入し、1−nのn個の配列を生成する.[2,n]の各数字はそうである.
839647521ディクショナリシーケンス法インクリメンタルシフト法インクリメンタルシフトシフトシフトシフトシフト法次839651247 849617523893647521 836947521仲介数72642321↑67342221↑12224376↓10121372↓番号297191 279905 340989 203393
/*以上転載*/以下に全配列問題の再帰と非再帰解法について述べる.1.再帰(分治法思想):R={r 1,r 2,..rn}は配列するn個の元素であり、Ri=R-{ri}とする.集合X中の元素の全配列をperm(X)と記す.(ri)perm(X)は、各全配列前にプレフィックスriを付ける得られた配列を表すものとする.
n=1の場合、perm(R)=(r)は、rが唯一の元素である、これが出口条件である.n>1の場合、perm(R)は(r 1)perm(R 1),(r 2)perm(R 2),...(rn)perm(Rn)の構成.void Perm(list[],int k,int m)/kはプレフィックスの位置を表し、mは配列する数である.{if(k==m-1)/接頭辞が最後の位置である場合、印刷配列数.{for(int i=0;iint b[N]; int is_train(int a[],int n) { int i,j,k=1 ; for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) if(a[j]<a[i])b[k++]=a[j]; /* */ if(k>1)is_train(b,k); else return(1); } } void train(int a[],int n) { int i,j,t,temp,count=1 ; t=1 ; printf("input the %3dth way:",count); for(i=1;i<=n;i++) printf("%3d",a[i]); printf("
"); while(t) { i=n ; j=i-1 ; /* , */ while(j&&a[j]>a[i]) { j--; i--; } if(j==0)t=0 ; else t=1 ; if(t) { i=n ; /* , front */ while(a[j]>a[i]) i--; temp=a[j],a[j]=a[i],a[i]=temp ; quicksort(a,j+1,N);/* */ /* */ if(is_train(a,N)==1) { count++; printf("input the %3dth way:",count); for(i=1;i<=n;i++) printf("%3d",a[i]); printf("
"); } } } }