Сгенерировать все возможные упорядоченные подмножества из набора

Question

Я знаю, как сгенерировать все возможные подмножества из набора, включающего сверление бит. Например,

//Get if nth position's bit is set 
bool IsBitSet(int num, int bit) 
{ 
    return 1 == ((num >> bit) & 1); 
} 

int subsetMaxIterCount = pow(2, someList.size()); 
for (int i = 0; i < subsetMaxIterCount; i++) { 
    vector<A> subset; 
     for (size_t i = 0; i < jobList.size(); i++) 
     { 
      if (IsBitSet(jobSubsetIdx, i)) { 
       //Add to subset here 
      } 
     } 

     //Here we have a subset for some i 
    } 

Однако это не учитывает порядок.

Например, если бы я имел множество {1, 2, 3}, выше алгоритм генерирует подмножества:

{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1,2,3}

Что мне нужно в действительности это

{}, {1}, {2}, {3 }, {1, 2}, {1, 3}, {2, 3}, {1,2,3}, {2, 1}, {2, 1, 3}, {2, 3, 1}, {3, 1}, {3, 2}, {3, 1, 2}, {3, 2, 1}

Не уверен, что приведенный выше список является исчерпывающим. Каков эффективный алгоритм генерации чего-то подобного? (Это все возможные подмножества с перестановкой, кстати?)

Answer 1

Способ генерации подмножеств с использованием бит-скручивания, каждое подмножество сортируется внутри него e.g. {1, 2, 3}, {2, 3}, {1, 3}. Вы можете сгенерировать перестановку для каждого подмножества с помощью next_permutation

vector<vector<int>> mySubsetGenerator(vector<vector<int>>& subsets) { 
    vector<vector<int>> extendedSubset; 
    for(int i = 0; i < subsets.size(); ++i) { 
     do { 
      extendedSubset.push_back(subsets[i]); 
     } while(next_permutation(subsets[i].begin(), subsets[i].end())); 
    } 
    return extendedSubset; 
} 

Кроме того, вы можете использовать только возвраты для генерации всех возможных перестановок, взяв один или несколько элементов массива.