すべての自尊心のあるプログラマーは、深いネストが悪いスタイルであることを知っています。 ただし、ネストされたループのカスケード（3つ以上）によって実装されるアルゴリズムがあります。 この記事では、お気に入りのDの組み合わせをソートするときに、ネストされたループの問題にどのように対処できるかについて説明します。
最も単純な状況を検討してください。
指定：N個のアイテム
必要：繰り返しなしでK要素のすべてのセットを反復処理する
組み合わせ論では、これはNからKへの割り当てと呼ばれます。
標準ライブラリは関数std.algorithm.permutationsを提供しますが、これは少し異なります-ロシア語の順列。
KによるNの単純な列挙を実装します。
import std.range; import std.algorithm; auto partialPermutation(R)( R r, size_t k ) if( isInputRange!R ) { static struct Result { R[] r, orig; // this( R[] r ) { this.r = r; orig = r.dup; } bool empty() @property { return r[0].empty; } void popFront() { foreach_reverse( ref x; r ) { x.popFront(); if( !x.empty ) break; } // foreach( i, ref x; r[1..$] ) { if( x.empty ) x = orig[i+1]; } } auto front() @property { return r.map!(a=>a.front); } } auto rr = new R[](k); rr[] = r; return Result( rr ); }
これで、この関数を使用して、可能なすべての組み合わせを反復処理できます。
foreach( v; partialPermutation( iota(6), 3 ) ) writefln( "%d %d %d", v[0], v[1], v[2] );
このような実装では、繰り返しが発生し、非常に単純に処理されます。
auto uniqPartialPermutation(R)( R r, size_t k ) if( isInputRange!R ) { bool noDups(T)( T v ) pure { foreach( i; 0 .. v.length ) if( v[i+1..$].canFind( v[i] ) ) return false; return true; } return partialPermutation(r,k).filter!(a=>noDups(a)); }
より複雑な例を考えてみましょう。
指定：異なるデータ型のNの異なる範囲
必要：これらの要素のすべての組み合わせのセットを反復処理します
D言語を使用すると、作業コードにわずかな変更を加えるだけで済みます。
望ましい結果を得るには：
auto combinations(R...)( R rngs ) if( allSatisfy!(isInputRange,R) ) { static struct Result { R r, orig; // this( R r ) { this.r = r; orig = r; } bool empty() @property { return r[0].empty; } void popFront() { foreach_reverse( ref x; r ) { x.popFront(); if( !x.empty ) break; } foreach( i, ref x; r[1..$] ) { if( x.empty ) x = orig[i+1]; } } auto front() @property { return getFronts( r ); } } return Result( rngs ); }
getFronts
ヘルパー関数は、最初の要素のタプルを返します。
auto getFronts(R...)( R r ) if( allSatisfy!(isInputRange,R) ) { static if( R.length == 1 ) return tuple( r[0].front ); else static if( R.length > 1 ) return tuple( getFronts(r[0]).expand, getFronts(r[1..$]).expand ); else static assert(0, "no ranges - no fronts" ); }
これで、次のように使用できます。
foreach( a,b,c; combinations(iota(3),["yes","no"],"xyz")) writeln( a,"[",b,"]",c );
図を完成させるために、機能を拡張して、機能の
combinations
範囲だけでなく、範囲のタプルも受け入れることができます。 これを行うには、名前を変更します
result
、同じ名前の関数内に入れますが、署名を制限せず、
ネストされたタプルの展開を追加します。
auto combinations(T...)( T tpls ) { auto result(R...)( R rrr ) if( allSatisfy!(isInputRange,R) ) { ... combinations ... } auto wrapTuples(X...)( X t ) pure { static if( X.length == 1 ) { static if( isTuple!(X[0]) ) return wrapTuples( t[0].expand ); else return tuple( t[0] ); } else static if( X.length > 1 ) return tuple( wrapTuples(t[0]).expand, wrapTuples(t[1..$]).expand ); } return result( wrapTuples(tpls).expand ); }
auto tt = tuple( hCube!3(iota(2)), iota(3) ); foreach( a, b, c, d, e, f; combinations( tt, ["yes", "no", "maybe"], "abc" ) ) writefln( "%s.%s.%s(%s) %s %s", a, b, c, d, e, f );
ここで、
hCube
関数は、指定された回数だけ範囲を複製します。
auto hCube(size_t N,R)( R r ) { static if( N == 0 ) return tuple(); static if( N == 1 ) return tuple(r); else return tuple( r, hCube!(N-1)(r).expand ); }
それだけです foreachの数を減らしても、この状況でのアルゴリズムの複雑さは変わらないことに注意してください。 もう少し砂糖。