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

[Anonymous]

Я работаю над созданием всех возможных комбинаций из списка n элементов, независимо от количества элементов в результирующих комбинациях. Это в основном набор мощности без пустого набора.
Из набора {1 2 3} у вас будет 7 комбинаций.( 1 )
( 1 2 )
( 1 2 3 )
( 1 3 )
( 2 )
( 2 3 )
( 3 )
< /code>
Каждое решение, которое я мог найти, ограничивает результаты в списках указанного количества элементов. У меня есть одно решение, но мне интересно, есть ли более эффективное решение. Я думаю, что это близко к O (n 2 ).
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 ... -in-a-list