Программист
0,0
рейтинг
7 января в 01:37

Разработка → Немного сахара в комбинаторике tutorial

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

Каждый уважающий себя программист знает, что глубокие вложенности — плохой стиль. Но есть алгоритмы, которые реализуются каскадом вложенных циклов (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 не меняет сложность алгоритма в этой ситуации. Просто ещё немного сахара.
Oleg Butko @deviator
карма
25,0
рейтинг 0,0
Программист
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (5)

  • 0
    Может оформите это модулем и выложите на code.dlang.org?
    • 0
      не думаю, что такую мелочь стоит выносить в отдельный модуль
      но я добавил это в desmath
      • 0
        Так даже лучше, спасибо.
  • +1
    Я случайно вашу первую задачу на Haskell:
    import Data.List
    import Control.Monad
    
    pPerm :: Eq a => Int -> [a] -> [[a]]
    pPerm c = mfilter (\r -> r == nub r) . replicateM c
    
    main :: IO ()
    main = putStr $ unlines $ map show $ pPerm 3 [1..5]
    

    (хотя nub неэффективен и квадратичен, можно вместо него использовать nubBy).

    А во второй задаче надо для множеств A1… An перебрать все элементы из их декартова произведения?
    • 0
      Да, видимо, так правильней будет сказать.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.