順列生成

順列を生成．

再帰による辞書式順でない順列生成

view plainprint?

1. public void generate(int[] a){  
2.  recursive(a,0);  
3. }  
4.   
5. private void recursive(int[] a,int j){  
6.  if(j==a.length){  
7.   System.out.println(Arrays.toString(a));  
8.   return;  
9.  }  
10.  for(int i=j;i<a.length;i++){  
11.   // a[i]とa[j]を入れ替え  
12.   int t=a[j]; a[j]=a[i]; a[i]=t;  
13.   recursive(a,j+1);  
14.   // a[i]とa[j]を入れ替え  
15.   t=a[j]; a[j]=a[i]; a[i]=t;  
16.  }  
17. }  

public void generate(int[] a){
 recursive(a,0);
}

private void recursive(int[] a,int j){
 if(j==a.length){
  System.out.println(Arrays.toString(a));
  return;
 }
 for(int i=j;i<a.length;i++){
  // a[i]とa[j]を入れ替え
  int t=a[j]; a[j]=a[i]; a[i]=t;
  recursive(a,j+1);
  // a[i]とa[j]を入れ替え
  t=a[j]; a[j]=a[i]; a[i]=t;
 }
}

再帰による辞書式順順列生成

view plainprint?

1. public void generate(int[] a){  
2.  recursive(a,0);  
3. }  
4.   
5. private void recursive(int[] a,int j){  
6.  if(j==a.length){  
7.   System.out.println(Arrays.toString(a));  
8.   return;  
9.  }  
10.  for(int i=j;i<a.length;i++){  
11.   // j~iを循環右ローテート  
12.   int t=a[i];  
13.   for(int k=i;k>j;k--)  
14.    a[k]=a[k-1];  
15.   a[j]=t;  
16.   recursive(a,j+1);  
17.   // j~iを循環左ローテート  
18.   for(int k=j;k<i;k++)  
19.    a[k]=a[k+1];  
20.   a[i]=t;  
21.  }  
22. }  

public void generate(int[] a){
 recursive(a,0);
}

private void recursive(int[] a,int j){
 if(j==a.length){
  System.out.println(Arrays.toString(a));
  return;
 }
 for(int i=j;i<a.length;i++){
  // j~iを循環右ローテート
  int t=a[i];
  for(int k=i;k>j;k--)
   a[k]=a[k-1];
  a[j]=t;
  recursive(a,j+1);
  // j~iを循環左ローテート
  for(int k=j;k<i;k++)
   a[k]=a[k+1];
  a[i]=t;
 }
}

辞書式順でない順列生成では，単純に2つの要素を交換していますが，辞書式順の順列生成では，その操作を右ローテートに置き換えています．
右ローテートだと辞書式順になる理由は以下の通り．

a₁a₂…a_n
と要素が並んでいて，
a_i>a_i+1
とします．(色々説明が面倒なので要素a_iを数とします)
a_iを先頭に置いた時，辞書式順で初めに来る列(=最小値)は何かというと，
a₁…a_i-1a_ia_i+1…a_n
のa_iを先頭に持ってきた
a_i[a₁…a_i-1a_i+1…a_n]
になります．ちょうどこれは，元の列のa₁…a_iを右にローテートしたものです．
というわけで，i=1~nについてこの操作を実行すると，
a₁[a₂a₃…a_n-1a_n]
a₂[a₁a₃…a_n-1a_n]
…
a_n-1[a₁a₂…a_n-2a_n]
a_n[a₁a₂…a_n-2a_n-1]
とn個の列が出来ます．
それぞれの列について再帰させ，[]内でも同様の操作を行うと，1つの列あたりn-1個の列が出来ます．

a₁[a₂[a₃a₄…a_n-1a_n]]
a₁[a₃[a₂a₄…a_n-1a_n]]
…
a₁[a_n-1[a₂a₃…a_n-2a_n]]
a₁[a_n[a₂a₃…a_n-2a_n-1]]

[[]]の一番内側の列は，2項目までを決定した時の最小値です．
というわけで，n回再帰することで，辞書式順の順列が作れます．