Xiagua Xiagua - 26 days ago 12
C++ Question

Generate all possible ordered subset from a set

I'm aware how to generate all possible subsets from a set incorporating bit twiddling. For instance,

//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
}


However, this doesn't take into account of ordering.

For instance, if I had a set of {1, 2, 3}, the above algorithm generates subsets of:

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

What I need in reality is this

{}, {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}

Not sure if the above list is exhaustive. What's an effective algorithm in generating something like this? (Is this all possible subsets with permutation by the way?)

Answer

The way we generate the subsets using bit twiddling, every subset is sorted within it e.g. {1, 2, 3}, {2, 3}, {1, 3}. You can generate permutation for each subset using 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;
}

Moreover, you can use only backtracking to generate all possible permutations by taking one or more elements of array.

Comments