Создание всех возможных комбинаций n элементов в C ++ ⇐ C++

[Anonymous]

Я работаю над созданием всех возможных комбинаций из списка n элементов, независимо от количества элементов в результирующих комбинациях. Это в основном набор мощности без пустого набора.
из набора {1 2 3} у вас будет 7 комбинаций.
(1) (1 2) (1 2 3) (1 3) (2) (2 3) (3)
Каждое решение, которое я мог бы найти, ограничивает результаты в списках указанного количества элементов. У меня есть одно решение, но я задаюсь вопросом, есть ли более эффективное решение. Я думаю, что это близко к O (n^2). < /P>
template
std::list PieceList::GetCombinations(std::list rightList)
{
std::list retVal;

if (rightList.size() == 1)
{
// Add a list with the last element.
// This element will appear at the end of the results.
retVal.push_back(rightList);
}
else
{
std::list leftList;
// Split off the first element from the right list.
leftList.splice(leftList.end(), rightList, rightList.begin());
// Add the list of one element to the results
retVal.push_back(leftList);
// Get results from the remaining elements.
std::list combinations = GetCombinations(rightList);
for (const std::list& valueList : combinations)
{
std::list temp(leftList);
// Append every result to the left list of one value.
temp.insert(temp.end(), valueList.begin(), valueList.end());
// Add this list to the results
retVal.push_back(temp);
}
// Add in the results from the last recursion.
retVal.splice(retVal.end(), combinations); // This preserves the order from the input list.
}

return retVal;
}



Подробнее здесь: https://stackoverflow.com/questions/796 ... items-in-c