Xiagua - 1 year ago 106
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)) {
}
}

//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?)

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download