Как написать C++ версию Python-функции powerset

Question

Я хочу написать алгоритм максимальной клики для использования с матрицей смежности. Я следую за видео, которое объясняет, как кодировать и реализовывать алгоритм с использованием Python. В настоящее время я пытаюсь закодировать функцию powerset через 2 минуты в видео.

def powerSet(elts):
    if len(elts) == 0:
        return [[]]
    else:
        smaller = powerSet(elts[1:])
        elt = [elts[0]]
        withElt = []
        for s in smaller:
            withElt.append(s + elt)
        allofthem = smaller + withElt
    return allofthem

print powerSet([1, 2, 3, 4, 5])

Я хочу переписать это на C++. Я не уверен, должен ли я использовать массивы или нет. До сих пор я кодировал ниже, но я не знаю, как вернуть пустой массив внутри пустого массива (когда eltslist имеет размер 0).

Я написал isEmpty функция для массива, так как я не могу использовать len(elts) как в Python. Мой подход, вероятно, не лучший подход, поэтому я открыт для любых советов.

ОБНОВИТЬ:

array powerSet(int elts[])
{
     if (isEmpty(elts)==1)
     {
          return {{}};
     }

}

В моем int main у меня есть:

list<int> elts;

list<int>::iterator i;

for (i=elts.begin(); i != elts.end(); ++i)
      cout << *i << " ";
      cout << endl;

powerSet(elts);    

Я не знаю, что делать отсюда.

Код должен использовать либо array/list/vector что мы называем "эльты" (сокращение от элементов). Затем, во-первых, следует добавить пустой список []затем остальная часть питания установлена ​​(все показано на видео).

Так, например, в случае, если elts = [1,2,3,4]мой код должен вернуться:

`[ [],[4],[3],[4,3],[2],[4,2],[3,2],[4,3,2],[1],[4,1],[3,1],[4,3,1],[2,1],[4,2,1],[‌​3,2,1],[4,3,2,1] ]  `  

Я не знаю как пользоваться array/list/vector чтобы сделать выше.

Answer 1

Вот довольно буквальный перевод кода Python

#include <vector>
using std::vector;
#include <iostream>
using std::cout;

//def powerSet(elts):
vector<vector<int>> powerSet(const vector<int>& elts)
{
//  if len(elts) == 0:
    if (elts.empty()) {
//      return [[]]
        return vector<vector<int>>(
            1, // vector contains 1 element which is...
            vector<int>()); // ...empty vector of ints
    }
//  else:
    else {
//      smaller = powerSet(elts[1:])
        vector<vector<int>> smaller = powerSet(
            vector<int>(elts.begin() +1, elts.end()));
//      elt = [elts[0]]
        int elt = elts[0]; // in Python elt is a list (of int)
//      withElt = []
        vector<vector<int>> withElt;
//      for s in smaller:
        for (const vector<int>& s: smaller) {
//          withElt.append(s + elt)
            withElt.push_back(s);
            withElt.back().push_back(elt);
        }
//      allofthem = smaller + withElt
        vector<vector<int>> allofthem(smaller);
        allofthem.insert(allofthem.end(), withElt.begin(), withElt.end());
//      return allofthem
        return allofthem;
    }
}

Это использует vector<int> для набора целых чисел. А потом vector этого, т.е. vector<vector<int>> список целых чисел Вы специально спросили об одной вещи

Я не знаю, как вернуть пустой массив внутри пустого массива (когда eltslist имеет размер 0).

Первый return оператор возвращает список с одним элементом, пустым набором, используя vector конструктор, чей первый аргумент n это количество элементов в vector и чей второй аргумент является элементом для повторения n раз. Эквивалентная, но более многословная альтернатива

    vector<vector<int>> powerSetOfEmptySet;
    vector<int> emptySet;
    powerSetOfEmptySet.push_back(emptySet);
    return powerSetOfEmptySet;

Я пытался сохранить код простым и избегать слишком многих эзотерических функций C++. Надеюсь, что вы можете пройти через это с помощью хорошей справки. Одна идиома C++, которую я использовал, добавляет один вектор к другому, как в allofthem.insert(allofthem.end(), withElt.begin(), withElt.end());,

Также в C++, который "ближе к металлу", чем Python, вы, вероятно, использовали бы только один vector вместо трех векторов smaller, withElt а также allofthem, Это приводит к более короткому и более оптимальному коду ниже.

//def powerSet(elts):
vector<vector<int>> powerSet(const vector<int>& elts)
{
//  if len(elts) == 0:
    if (elts.empty()) {
//      return [[]]
        return vector<vector<int>>(1, vector<int>());
    }
//  else:
    else {
//      smaller = powerSet(elts[1:])
        vector<vector<int>> allofthem = powerSet(
            vector<int>(elts.begin() +1, elts.end()));
//      elt = [elts[0]]
        int elt = elts[0]; // in Python elt is a list (of int)
//      withElt = []
//      for s in smaller:
//          withElt.append(s + elt)
//      allofthem = smaller + withElt
        const int n = allofthem.size();
        for (int i=0; i<n; ++i) {
            const vector<int>& s = allofthem[i];
            allofthem.push_back(s);
            allofthem.back().push_back(elt);
        }
//      return allofthem
        return allofthem;
    }
}

Тестовый код ниже

int main()
{
    const int N = 5;
    vector<int> input;
    for(int i=1; i<=N; ++i) {
        input.push_back(i);
    }
    vector<vector<int>> ps = powerSet(input);
    for(const vector<int>& set:ps) {
        cout << "[ ";
        for(int elt: set) {
            cout << elt << " ";
        }
        cout << "]\n";
    }
    return 0;
}

В качестве сноски я был приятно удивлен тем, насколько просто это было перевести с Python на C++. Я читал, что, возможно, имеет смысл использовать Python для написания (или создания прототипа) алгоритмов, а затем переписывать их по необходимости на языке, таком как C++, но, как гласит пословица, видеть - значит верить.

---

Вот версия программы, которая работает с C++98. Я отменил основные функции C++11, которые я использовал (>> в объявлениях шаблонов и на основе диапазона for).

#include <vector>
using std::vector;
#include <iostream>
using std::cout;

vector<vector<int> > powerSet(const vector<int>& elts)
{
    if (elts.empty()) {
        return vector<vector<int> >(1, vector<int>());
    }
    else {
        vector<vector<int> > allofthem = powerSet(
            vector<int>(elts.begin() +1, elts.end()));
        int elt = elts[0];
        const int n = allofthem.size();
        for (int i=0; i<n; ++i) {
            const vector<int>& s = allofthem[i];
            allofthem.push_back(s);
            allofthem.back().push_back(elt);
        }
        return allofthem;
    }
}

int main()
{
    const int N = 5;
    vector<int> input;
    for(int i=1; i<=N; ++i) {
        input.push_back(i);
    }
    vector<vector<int> > ps = powerSet(input);
    for(vector<vector<int> >::const_iterator i=ps.begin(); i!=ps.end(); ++i) {
        const vector<int>& set = *i;
        cout << "[ ";
        for(vector<int>::const_iterator j=set.begin(); j!=set.end(); ++j) {
            int elt = *j;
            cout << elt << " ";
        }
        cout << "]\n";
    }
    return 0;
}