順列
PermutationTest.lzh
数独を始めとする論理パズルを解くプログラムでは、順列・組合せを多く用います。
順列・組合せは、ネット上のライブラリーなどが見つかると思いますが、ひとつ重要な機能が必要です。
例えば、6個から5つを選ぶ順列で(6P5) を生成したとします（”1,2,3,4,5”）。
これを用いてある事象群を評価しているとき、2番目の事象で誤りと分かったら3番目以降の評価は意味がないので中止します。
すなわち次の順列(”1,2,3,4,6”)、さらに次の順列(”1,2,3,5,4”)、…も意味がなく、
これらは飛ばして順列(”1,3,2,4,5”)に進むのが合理的です。
このように、次々に順列を生成するとき順列の位置を指定してスキップする機能が必要です。
GNPxでは、順列を扱うのは次のクラスです。実際に順列を生成するコードは、以下で示します。
public class Permutation{
private int N=0;
private int R=0;
private int[] Pwrk=null;
public int[] Pnum=null;
private bool First;
public Permutation( int N, int R=-1 ){
this.N=N;
this.R=R;
if( R<=0 || R>N ) this.R=N;
if( N>0 ){
Pwrk = Enumerable.Range(0,N).ToArray();
Pnum = Enumerable.Range(0,this.R).ToArray();
}
First=true;//(The first permutation has already been created in the constructor)
}
public bool Successor( int skip=-1 ){
if( First || Pwrk==null ){ First=false; return (Pwrk!=null); }
int r = (skip>=0)? skip: R-1;
if( r>N-1 ) r=N-1;
do{
if( r<0 ) break;
int A=Pwrk[r];
L_1:
if( A>=N-1 ){ r--; continue; }
A++;
for( int k=0; k<r; k++ ){ if( Pwrk[k]==A ) goto L_1; }
Pwrk[r]=A; //The next update position (r) and the number (A)
if( r<N-1 ){
int[] wx = Enumerable.Range(0,N).ToArray();
for( int k=0; k<=r; k++ ) wx[Pwrk[k]]=-1;//Exclude used digits
int n=0;
for( int k=r+1; k<N; k++ ){ // Fill the number after the change position
for( ; n<N; n++ ){
if( wx[n]<0 ) continue;
Pwrk[k]=wx[n++];
break;
}
}
}
for( int k=0; k<R; ++k ) Pnum[k]=Pwrk[k];//(Copy to external reference array)
return true;
}while(true);
return false;
}
public override string ToString(){
string st=""; Array.ForEach( Pnum, p=> st+=(" "+p) );
st += " "; Array.ForEach( Pwrk, p=> st+=(" "+p) );
return st;
}
}
Permutationの使い方
Permutationを次のように使います。
Successorをcallするたびに次の順列を生成し、生成している間は戻り値はtrueで、最後に達するとfalseになります。
次の順列生成の変更位置を指定して、無駄な生成をスキップします。変更位置はダイナミックに変更できます。位置指定は0から(順列サイズ-1)で、これ以外の場合または指定を省略したときは、スキップ機能は働きません。
var perm = new Permutation(6,5);
int skip=4;
while(perm.Successor(skip) ){
(Evaluation process) (Set change position skip for next permutation generation)
}*テストプログラム
class Program{
static void Main( string[ ] args ) {
Console.WriteLine( "* Permutation(4) *\n Successor()" );
Permutation perm = new Permutation(4);
while(perm.Successor()) Console.WriteLine( perm );
Console.WriteLine( "\n* Permutation(4,2) *\n Successor()" );
perm = new Permutation(4,2);
while(perm.Successor()) Console.WriteLine( perm );
Console.WriteLine( "\n* Permutation(4,3) *\n Successor(1)" );
perm = new Permutation(4,3);
while(perm.Successor(1)) Console.WriteLine( perm );
Console.Write( "\nExit with key input;" );
Console.ReadKey();
}
}実行結果（左:順列生成結果 右:関数内部の作業データ）
* Permutation(4) *
0 1 2 3 0 1 2 3
0 1 3 2 0 1 3 2
0 2 1 3 0 2 1 3
0 2 3 1 0 2 3 1
0 3 1 2 0 3 1 2
0 3 2 1 0 3 2 1
1 0 2 3 1 0 2 3
1 0 3 2 1 0 3 2
1 2 0 3 1 2 0 3
1 2 3 0 1 2 3 0
1 3 0 2 1 3 0 2
1 3 2 0 1 3 2 0
2 0 1 3 2 0 1 3
2 0 3 1 2 0 3 1
2 1 0 3 2 1 0 3
2 1 3 0 2 1 3 0
2 3 0 1 2 3 0 1
2 3 1 0 2 3 1 0
3 0 1 2 3 0 1 2
3 0 2 1 3 0 2 1
3 1 0 2 3 1 0 2
3 1 2 0 3 1 2 0
3 2 0 1 3 2 0 1
3 2 1 0 3 2 1 0
* Permutation(4,2) *
0 1 0 1 2 3
0 2 0 2 1 3
0 3 0 3 1 2
1 0 1 0 2 3
1 2 1 2 0 3
1 3 1 3 0 2
2 0 2 0 1 3
2 1 2 1 0 3
2 3 2 3 0 1
3 0 3 0 1 2
3 1 3 1 0 2
3 2 3 2 0 1
* Permutation(4,3) *
0 1 2 0 1 2 3
0 2 1 0 2 1 3
0 3 1 0 3 1 2
1 0 2 1 0 2 3
1 2 0 1 2 0 3
1 3 0 1 3 0 2
2 0 1 2 0 1 3
2 1 0 2 1 0 3
2 3 0 2 3 0 1
3 0 1 3 0 1 2
3 1 0 3 1 0 2
3 2 0 3 2 0 1