I have an assignment to show a brute force algorithm on combination and permutations. All I am given is the function headers, and I cannot see the main. I'm having trouble understanding how sets work...

Here is my header function for combination

``set< set<char> > powerSet(set<char S>)``

now, I'm not really sure where to start here. I kind of know how to do the algorithm for combination (essentially if the input was 1,2,3,4,5 it would print out every combination of that), but how do I iterate through sets?

how do I define the first and last parts of the set? Like this?

``(type?) i = S.begin()``

sorry if this post seems confusing.. I'm not really sure of it myself :D

3
Contributors
8
Replies
9
Views
7 Years
Discussion Span
Last Post by pseudorandom21

If your compiler has C++0x TR1 support, you can use the auto keyword for the type, otherwise you can use the iterator type.

I'm not exactly sure what you want, but here is an example of iterating over a set with iterators.

If iterators are new to you, you may wish to read about them before jumping in to using the STL.

``````set< int > myset;
myset.insert(100);
myset.insert(200);
myset.insert(300);
for( set<int>::iterator it = myset.begin(); it != myset.end(); ++it)
{
//Use iterator.
cout << (*it) << endl;
}``````

Okay thanks for the input so far.
This is helping me understand how to manipulate sets on the driver side. Now I need to figure out how to manipulate them in the functions. Also, if my set is full of chars instead of ints, how do I use the iterator to navigate the set?

Okay I've got most of it figured out now thanks!

Now to figure out the combination algorithm with sets!

Okay so I've worked on the permutation function and here is what I've got so far

``````set<string> permutation(set<char>S)
{
set<string> fun;
sort(S.begin(), S.end());
do{
fun.insert(S.begin(), S.end());
}while(next_permutation(S.begin(), S.end()));
return fun;
}``````

I'm receiving errors in the algorithms file... but it's mostly low level gibberish to me. Any thoughts?

Okay so I've worked on the permutation function and here is what I've got so far

``````set<string> permutation(set<char>S)
{
set<string> fun;
sort(S.begin(), S.end());
do{
fun.insert(S.begin(), S.end());
}while(next_permutation(S.begin(), S.end()));
return fun;
}``````

I'm receiving errors in the algorithms file... but it's mostly low level gibberish to me. Any thoughts?

scratch the sort function, that was causing most of the problems. How do I correctly 'insert' the different permutations into my set<string>?

Std::set is ordered, you can't change order of numbers. You could just use presorted normal array (vector) for next_permutation.

That's a good idea with the std::next_permutation(), I should have caught on to that myself. I thought that function was absolutely awesome when I went to do some permutation stuff.

Also, you may consider deciding upon the best container for your code, I would probably use a vector like Zjarek said. But the std::list<> can probably swap some stuff around faster.

Also, depending on how much data you have to permute, it may take a LOT of processing power or a LOT of time. It is my guess you will be considering performance improvements, so I'll add that to take advantage of multi-core processors you will need to use multiple threads of execution.

Edited by pseudorandom21: n/a