Использование рекурсии и обратного отслеживания для создания всех возможных комбинаций

Ответ 1

Хороший способ подумать о формировании N комбинаций - это посмотреть на структуру, как на дерево комбинаций. Прохождение этого дерева становится естественным способом думать о рекурсивном характере алгоритма, который вы хотите реализовать, и о том, как будет работать рекурсивный процесс.

Скажем, например, что у нас есть последовательность {1, 2, 3, 4}, и мы хотим найти все 3-комбинации в этом множестве. "Дерево" комбинаций будет выглядеть следующим образом:

                              root
                        ________|___
                       |            | 
                     __1_____       2
                    |        |      |
                  __2__      3      3
                 |     |     |      |
                 3     4     4      4

Переходя от корня, используя обход предварительного порядка и идентифицируя комбинацию при достижении листа node, мы получаем комбинации:

{1, 2, 3}
{1, 2, 4}
{1, 3, 4}
{2, 3, 4}

Таким образом, в основном идея заключалась бы в последовательности через массив с использованием значения индекса, что для каждого этапа нашей рекурсии (которая в этом случае была бы "уровнями" дерева), увеличивается в массив, чтобы получить значение которые будут включены в набор комбинаций. Также обратите внимание, что нам нужно только перезаписывать N раз. Поэтому у вас будет некоторая рекурсивная функция, подпись которой будет выглядеть примерно так:

void recursive_comb(int step_val, int array_index, std::vector<int> tuple);

где step_val указывает, как далеко мы должны возвращаться, значение array_index указывает нам, где мы находимся в наборе, чтобы начать добавлять значения в tuple и tuple re complete, будет экземпляром комбинации в наборе.

Затем вам нужно вызвать recursive_comb из другой нерекурсивной функции, которая в основном "запускает" рекурсивный процесс путем инициализации вектора tuple и ввода максимальных рекурсивных шагов (т.е. количества значений, которые мы хотим в кортеж):

void init_combinations()
{
    std::vector<int> tuple;
    tuple.reserve(tuple_size); //avoids needless allocations
    recursive_comb(tuple_size, 0, tuple);
}

Наконец, ваша функция recusive_comb будет выглядеть примерно так:

void recursive_comb(int step_val, int array_index, std::vector<int> tuple)
{
    if (step_val == 0)
    {
        all_combinations.push_back(tuple); //<==We have the final combination
        return;
    }

    for (int i = array_index; i < set.size(); i++)
    {
        tuple.push_back(set[i]);
        recursive_comb(step_val - 1, i + 1, tuple); //<== Recursive step
        tuple.pop_back(); //<== The "backtrack" step
    }

    return;
}

Здесь вы можете увидеть рабочий пример этого кода: http://ideone.com/78jkV

Обратите внимание, что это не самая быстрая версия алгоритма, поскольку мы берем некоторые дополнительные ветки, которые нам не нужно брать, которые создают ненужные вызовы копирования и вызова и т.д.... но, надеюсь, он общее представление о рекурсии и обратном слежении, а также о том, как они работают вместе.

Ответ 2

Лично я бы пошел с простым итерационным решением.

Представьте набор узлов как набор бит. Если вам нужно 5 узлов, то есть 5 бит, каждый бит представляет конкретный node. Если вам нужно 3 из них в вашем тапочке, вам просто нужно установить 3 бита и отслеживать их местоположение.

В основном это простая вариация в отношении всех разных подмножеств узлов. Если классическая реализация представляет собой набор узлов как целое число. Каждый бит в целочисленном выражении представляет node. Пустое множество равно 0. Затем вы просто увеличиваете целое число, каждое новое значение представляет собой новый набор узлов (битовый шаблон, представляющий набор узлов). Только в этом варианте вы убедитесь, что на нем всегда есть 3 узла.

Просто, чтобы помочь мне подумать, я начинаю с активных 3-х верхних узлов {4, 3, 2}. Затем я пересчитываю. Но было бы тривиально изменить это, чтобы считать в другом направлении.

#include <boost/dynamic_bitset.hpp>
#include <iostream>


class TuppleSet
{
    friend std::ostream& operator<<(std::ostream& stream, TuppleSet const& data);

    boost::dynamic_bitset<> data;    // represents all the different nodes
    std::vector<int>        bitpos;  // tracks the 'n' active nodes in the tupple

    public:
        TuppleSet(int nodes, int activeNodes)
            : data(nodes)
            , bitpos(activeNodes)
        {
            // Set up the active nodes as the top 'activeNodes' node positions.
            for(int loop = 0;loop < activeNodes;++loop)
            {
                bitpos[loop]        = nodes-1-loop;
                data[bitpos[loop]]  = 1;
            }
        }
        bool next()
        {
            // Move to the next combination
            int bottom  = shiftBits(bitpos.size()-1, 0);
            // If it worked return true (otherwise false)
            return bottom >= 0;
        }
    private:
        // index is the bit we are moving. (index into bitpos)
        // clearance is the number of bits below it we need to compensate for.
        //
        //  [ 0, 1, 1, 1, 0 ]   =>    { 3, 2, 1 }
        //             ^
        //             The bottom bit is move down 1 (index => 2, clearance => 0)
        //  [ 0, 1, 1, 0, 1]    =>    { 3, 2, 0 }
        //                ^
        //             The bottom bit is moved down 1 (index => 2, clearance => 0)
        //             This falls of the end
        //          ^
        //             So we move the next bit down one (index => 1, clearance => 1)
        //  [ 0, 1, 0, 1, 1]
        //                ^
        //             The bottom bit is moved down 1 (index => 2, clearance => 0)
        //             This falls of the end
        //             ^
        //             So we move the next bit down one (index =>1, clearance => 1)
        //             This does not have enough clearance to move down (as the bottom bit would fall off)
        //      ^      So we move the next bit down one (index => 0, clearance => 2)
        // [ 0, 0, 1, 1, 1] 
        int shiftBits(int index, int clerance)
        {
            if (index == -1)
            {   return -1;
            }
            if (bitpos[index] > clerance)
            {
                --bitpos[index];
            }
            else
            {
                int nextBit = shiftBits(index-1, clerance+1);
                bitpos[index] = nextBit-1;
            }
            return bitpos[index];
        }
};

std::ostream& operator<<(std::ostream& stream, TuppleSet const& data)
{
    stream << "{ ";
    std::vector<int>::const_iterator loop = data.bitpos.begin();
    if (loop != data.bitpos.end())
    {
        stream << *loop;
        ++loop;
        for(; loop != data.bitpos.end(); ++loop)
        {
            stream << ", " << *loop;
        }
    }
    stream << " }";
    return stream;
}

Главное тривиально:

int main()
{
    TuppleSet   s(5,3);

    do
    {
        std::cout << s << "\n";
    }
    while(s.next());
}

Выход:

{ 4, 3, 2 }
{ 4, 3, 1 }
{ 4, 3, 0 }
{ 4, 2, 1 }
{ 4, 2, 0 }
{ 4, 1, 0 }
{ 3, 2, 1 }
{ 3, 2, 0 }
{ 3, 1, 0 }
{ 2, 1, 0 }

Версия shiftBits() с использованием цикла

    int shiftBits()
    {
        int bottom   = -1;
        for(int loop = 0;loop < bitpos.size();++loop)
        {
            int index   = bitpos.size() - 1 - loop;
            if (bitpos[index] > loop)
            {
                bottom = --bitpos[index];
                for(int shuffle = loop-1; shuffle >= 0; --shuffle)
                {
                    int index   = bitpos.size() - 1 - shuffle;
                    bottom = bitpos[index] = bitpos[index-1]  - 1;
                }
                break;
            }
        }
        return bottom;
    }

Ответ 3

В MATLAB:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% combinations.m

function combinations(n, k, func)
assert(n >= k);
n_set = [1:n];
k_set = zeros(k, 1);
recursive_comb(k, 1, n_set, k_set, func)
return

function recursive_comb(k_set_index, n_set_index, n_set, k_set, func)
if k_set_index == 0,
  func(k_set);
  return;
end;
for i = n_set_index:length(n_set)-k_set_index+1,
  k_set(k_set_index) = n_set(i);
  recursive_comb(k_set_index - 1, i + 1, n_set, k_set, func); 
end;
return;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Test:
>> combinations(5, 3, @(x) printf('%s\n', sprintf('%d ', x)));
3 2 1 
4 2 1 
5 2 1 
4 3 1 
5 3 1 
5 4 1 
4 3 2 
5 3 2 
5 4 2 
5 4 3