Xiagua - 1 year ago 106

C++ Question

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

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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**