Может кто-нибудь объяснить, как работает рекурсия при поиске всех подмножеств?

Question

Я не могу, по жизни моей, рекурсии изображения и того, что он делает. Я много с этим борюсь. Из Руководства программиста-конкурента я обнаружил следующий фрагмент кода на C ++ в качестве решения следующей проблемы:

Рассмотрим проблему генерации всех подмножеств набора из n элементов. Например, подмножества {0,1,2}:;, {0}, {1}, {2}, {0,1}, {0,2}, {1,2} и {0,1,2}.

Элегантный способ просмотреть все подмножества набора - использовать рекурсию. Следующая функция поиска генерирует подмножества множества {0,1, ..., n - 1}. Функция поддерживает векторное подмножество, которое будет содержат элементы каждого подмножества. Поиск начинается, когда функция вызывается с параметром 0.

Когда функция поиска вызывается с параметром k, она решает следует ли включать элемент k в подмножество или нет, и в обоих случаев, затем вызывает себя с параметром k + 1 Однако, если k = n, функция замечает, что все элементы были обработаны и подмножество был сгенерирован.

void search(int k) {
    if (k == n) {
        // process subset
    } else {
        search(k+1);
        subset.push_back(k);
        search(k+1);
        subset.pop_back();
    }
}

Конечно, эта функция работает, и я сделал это около 3 раз вручную, чтобы убедиться, что она работает без нареканий. Но почему?

За исключением запоминания всех рекурсивных решений для всех проблем, я никогда не смогу найти такое решение. Какая абстракция здесь делается? Какое более общее понятие используется здесь?

Я всегда боролся с рекурсией, поэтому любая помощь приветствуется. Спасибо.

Answer 1

Для каждого k мы просто вызываем search(k+1) рекурсивно.один раз со значением k внутри вашего набора и один раз без него.

    search(k+1); // call search (k+1) with k NOT inside the set
    subset.push_back(k); // puts the value k inside the set
    search(k+1); // call search (k+1) with k inside the set
    subset.pop_back(); // removes the value k from the set

Как только мы достигнем n == k , рекурсия прекращается.

Представьте себе двоичное дерево глубины n, где каждый уровень представляет текущее значение, а две ветви - решение, входит ли значение в ваш окончательный набор или нет.Листья представляют все заключительные наборы.

Итак, учитывая n = 3 и начиная с k = 0 , вы получите:

search(0); 
-> search(1); // with 0 in
->-> search(2); // with 0 in AND 1 in
->->-> search (3); // with 0 in AND 1 in AND 2 in. terminates with (0,1,2)
->->-> search (3); // with 0 in AND 1 in AND 2 not in. terminates with (0,1)
->-> search(2); // with 0 in AND 1 not in
->->-> search (3); // with 0 in AND 1 not in AND 2 in. terminates with  (0,2)
->->-> search (3); // with 0 in AND 1 not in AND 2 not in. terminates with  (0)
-> search(1); // with 0 not in
->-> search(2); // with 0 not in AND 1 in
->->-> search (3); // with 0 not in AND 1 in AND 2 in. terminates with  (1,2)
->->-> search (3); // with 0 not in AND 1 in AND 2 not in. terminates with  (1)
->-> search(2); // with 0 not in AND 1 not in
->->-> search (3); // with 0 not in AND 1 not in AND 2 in. terminates with  (2)
->->-> search (3); // with 0 not in AND 1 not in AND 2 not in. terminates with  ()

As Джон , умно указав в своем комментарии, рекурсия использует тот факт, что:

all_subsets (a1, a2, ..., an) == all_subsets (a2, ..., an) U {a1, all_subsets (a2, ..., an)} , где U - оператор объединения множеств.

Многие другие математические определения преобразуются в рекурсивные вызовыестественно.

Answer 2

Это не только ваша проблема.Каждый, кто начинает изучать рекурсию впервые, сталкивается с этим.Главное - только визуализация.Хотя буквально это сложно.

Если вы попытаетесь визуализировать любой код рекурсии, сделав его удобным (используя ручку и бумагу), вы просто увидите: «О, это работает».Но вы должны знать, что большинство рекурсий имеют рекуррентное отношение.Исходя из этого, функция повторяется.Аналогично, для нахождения всех подмножеств определенного набора существует рекуррентное отношение. Это следующее ...

Взятие определенного элемента + Не взятие этого элемента

Здесьв вашем коде «Взятие определенного элемента» подразумевает «Push_back», а «Не взятие определенного элемента» подразумевает «Pop_back».Вот и все.

Одна из возможностей - не брать вещи.Мы называем это Нулевой набор .Другая возможность - взять все предметы.Здесь {0,1,2}.

Из теории комбинаций перестановок мы можем вычислить количество подмножеств.Это 2 ⁿ , где n - количество элементов.Здесь n = 3.Таким образом, число подмножеств будет 2 ³ = 8.

Для 0 возьмите или бросьте его, возможностей = 2
Для 1, возьмите или бросьте его, возможностей =2
Для 2, возьми или брось, возможности = 2

Итак, общее количество подмножеств равно 2 * 2 * 2 = 8 (включая Нулевой набор ).
Если вы отбросите Null Set , то общее число подмножеств будет 8-1 = 7.

Это теория вашего рекурсивного кода.

Answer 3

Я думаю, что вам не хватает визуализации. Поэтому я предлагаю вам посетить такие сайты, как attribute-visualizer.org , pythontutor.com .

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

#include <bits/stdc++.h>
using namespace std;

void subsetsUtil(vector<int>& A, vector<vector<int> >& res, vector<int>& subset, int index) {
    res.push_back(subset);
    for (int i = index; i < A.size(); i++) {
        subset.push_back(A[i]);
        subsetsUtil(A, res, subset, i + 1);
    }
    return;
}

vector<vector<int> > subsets(vector<int>& A) {
    vector<int> subset;
    vector<vector<int> > res;
    int index = 0;
    subsetsUtil(A, res, subset, index);
    return res;
}

int32_t main() {
    vector<int> array = { 1, 2, 3 };
    vector<vector<int> > res = subsets(array);
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++)
            cout << res[i][j] << " ";
        cout << endl;
    }
    return 0;
}

Хорошо, что ты действительно пытаешься учиться. Это очень поможет вам в соревновательном программировании. Надеюсь, это поможет вам