Как написать C ++ версию функции powerset Python
Я хочу написать алгоритм максимальной клики для использования с матрицей смежности. Я следую за видео который объясняет, как кодировать и реализовать алгоритм с использованием 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 ++. Я не уверен, должен ли я использовать массивы или нет. До сих пор я кодировал ниже, но я не знаю, как вернуть пустой массив внутри пустого массива (когда elts list имеет размер 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 чтобы сделать выше.
Решение
Вот довольно буквальный перевод кода 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 ++ I иметь используется добавление одного вектора к другому, как в 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;
}
Другие решения
Других решений пока нет …