Some sugar in combinatorics

Good day, Habr!

Every self-respecting programmer knows that deep nesting is a bad style. But there are algorithms that are implemented by a cascade of nested loops (3 or more). In this article I want to tell you how to deal with the problem of nested loops when iterating through combinations in your favorite language D.

Consider the simplest situation.

Given: N items
Necessary: ​​go through all the sets of K elements without repetitions
')
In combinatorics, this is called a placement from N to K.

The standard library provides the function std.algorithm.permutations, but this is slightly different - a permutation in Russian.

We implement a simple search of N by K:

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 ); } 

Now we can use this function to iterate through all possible combinations:

 foreach( v; partialPermutation( iota(6), 3 ) ) writefln( "%d %d %d", v[0], v[1], v[2] ); 

With this implementation, there are repetitions, it is quite simply treated:

 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)); } 

Consider a more complex example.

Given: N different ranges of different data types.
Necessary: ​​enumerate sets from all combinations of these elements

The D language gives us the opportunity to make a couple of small changes to the working code.
to get the desired result:

 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 ); } 

The helper function getFronts returns a tuple of the first elements:

 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" ); } 

Now you can use this:

 foreach( a,b,c; combinations(iota(3),["yes","no"],"xyz")) writeln( a,"[",b,"]",c ); 

For completeness, we will extend the functionality to our function combinations
could take not only ranges, but also tuples of ranges. To do this, rename it
result and put it inside a function with the same name, but without limiting the signature and
add the deployment of nested tuples:

 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 ); 

where the hCube function simply duplicates a range a specified number of times:

 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 ); } 

That's all. One thing to keep in mind is: reducing the number of foreach does not change the complexity of the algorithm in this situation. Just some more sugar.