Доброго времени суток, хабр!

Каждый уважающий себя программист знает, что глубокие вложенности — плохой стиль. Но есть алгоритмы, которые реализуются каскадом вложенных циклов (3 и более). В этой статье я хочу рассказать, как можно справиться с проблемой вложенных циклов при переборе комбинаций на любимом языке D.

Рассмотрим самую простую ситуацию.

Дано: N элементов
Нужно: перебрать все наборы по K элементов без повторений

В комбинаторике это называется размещением из N по K.

Стандартная библиотека предоставляет функцию std.algorithm.permutations, но это немного другое — перестановка по русски.

Реализуем простой перебор N по 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 ); } 

Теперь мы можем использовать эту функцию для перебора всех возможных комбинаций:

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 не меняет сложность алгоритма в этой ситуации. Просто ещё немного сахара.

ссылка на оригинал статьи http://habrahabr.ru/post/274619/