Velocity Reviews > C++ > combinations of substrings

# combinations of substrings

zgfareed@gmail.com
Guest
Posts: n/a

 09-23-2007
Can anyone suggest an algorithm or function to generate combinations/
permutations of a group of substrings stored in a vector. The
substrings consists of 3 letters and the resulting string combinations
should be of a size that is a multiple of 3.

sun1991
Guest
Posts: n/a

 09-24-2007
On 24 Sep, 06:53, (E-Mail Removed) wrote:
> Can anyone suggest an algorithm or function to generate combinations/
> permutations of a group of substrings stored in a vector. The
> substrings consists of 3 letters and the resulting string combinations
> should be of a size that is a multiple of 3.

check next_permutation() in STL.

Kai-Uwe Bux
Guest
Posts: n/a

 09-24-2007
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:

> Can anyone suggest an algorithm or function to generate combinations/
> permutations of a group of substrings stored in a vector. The
> substrings consists of 3 letters and the resulting string combinations
> should be of a size that is a multiple of 3.

First, the problem is obfuscated (I suspect, it is homework): the groups of
3 letters just hide the abstract problem of generating permutations and
combinations. So, first take the input data apart and create a

std::vector< std::string >

that stores those groups of three letters.

Now, for permutations, life is easy because STL has next_permutation built
in.

For combinations, note that the problem of enumerating all combinations of
length n from a set of k items is equivalent to listing all n-digit
counting numbers in base k (because if you have such a number, each digits
represents one of k items and you have made exactly n such choices). Thus,
you could use a

std::vector< unsigned int >

and implement "add 1" in base k.

Best

Kai-Uwe Bux