permutations and combinations

Discussion in 'C++' started by Jeff Kish, Mar 7, 2005.

1. Jeff KishGuest

Hi.

I realize this might be more of a "figure out the algorithm" thing than
strictly an std question.. sorry if it is off topic? It certainly was in the
other group!

Also, I'm pretty old, not in school.. just trying to figure this out., so it
isn't an assignment.

I see you can use next_permutation to find the permutations of a string of a
given length.

Right now I'm using a string, sorting it and passing it repeated into
next_permutation.

Is there any slick way to find all of them of any length, i.e. given a string
"dear" to get all of all lengths including:

a
ra
are
ear
dear
dare

I'm trying to figure out an algorithm to find all possible words from a set of
strings, without using any letters any more than they are in the string, i.e.
given lott you would not come up with "loot"

Thanks..
Jeff Kish
Jeff Kish, Mar 7, 2005

2. Victor BazarovGuest

Jeff Kish wrote:
> I realize this might be more of a "figure out the algorithm" thing than
> strictly an std question.. sorry if it is off topic? It certainly was in the
> other group!
>
> Also, I'm pretty old, not in school.. just trying to figure this out., so it
> isn't an assignment.
>
>
> I see you can use next_permutation to find the permutations of a string of a
> given length.
>
> Right now I'm using a string, sorting it and passing it repeated into
> next_permutation.

Does it work?

>
> Is there any slick way to find all of them of any length, i.e. given a string
> "dear" to get all of all lengths including:
>
> a
> ra
> are
> ear
> dear
> dare
>
> I'm trying to figure out an algorithm to find all possible words from a set of
> strings, without using any letters any more than they are in the string, i.e.
> given lott you would not come up with "loot"

There is no standard function for it, so you'd need to write a simple "get
me the next M from the set of N using the previous M" function. After you
have the subset, use std::next_permutation to enumerate all possibilities.
So, you'll have nested loops, one for lengths from 1 to strlen(yourstr),
and the other inside for the subsets, and inside that -- for permutations.

And, yes, it's not strictly a C++ question.

V
Victor Bazarov, Mar 7, 2005

3. Howard HinnantGuest

In article <>,
Jeff Kish <> wrote:

> Hi.
>
> I realize this might be more of a "figure out the algorithm" thing than
> strictly an std question.. sorry if it is off topic? It certainly was in the
> other group!
>
> Also, I'm pretty old, not in school.. just trying to figure this out., so it
> isn't an assignment.
>
>
> I see you can use next_permutation to find the permutations of a string of a
> given length.
>
> Right now I'm using a string, sorting it and passing it repeated into
> next_permutation.
>
> Is there any slick way to find all of them of any length, i.e. given a string
> "dear" to get all of all lengths including:
>
> a
> ra
> are
> ear
> dear
> dare
>
> I'm trying to figure out an algorithm to find all possible words from a set of
> strings, without using any letters any more than they are in the string, i.e.
> given lott you would not come up with "loot"

There's a closely related article in the Feb. '05 issue of C/C++ Users
Journal by John Dibling titled "Extending the STL".

template <class BidirectionalIterator, class Function, class Size>
Function
for_each_permutation(BidirectionalIterator first,
BidirectionalIterator last,
Size k,
Function fn);

The algorithm is documented to come from "The Art of Computer
Programming," Vol. 1, p. 45, Method 1.

for_each_permutation calls fn for each permutation of last-first items
taken k at a time:

fn(first, last)

I think this is a great algorithm, except that I think it would be
better if the Function were called with only the first k elements of the
permuted sequence, else you have to store k in fn:

fn(first, first+k)

Inspired by John's article, I wrote my own version of
for_each_permutation, which uses a slightly modified copy of
std::next_permutation to take into account that you sometimes only want
the items taken k at a time. However one could easily modify John's
publicly available listing to call fn(first, first+k) instead of
fn(first, last). Note, you might want to use std::advance where I've
used "+" to avoid requiring random access iterators.

At any rate, once you have this tool, your original problem can be
solved quite elegantly:

Create a printing functor:

class print
{
public:
print() : i_(0) {}

template <class It>
void operator()(It first, It last)
{
typedef typename std::iterator_traits<It>::value_type value_type;
std:stream_iterator<value_type> out(std::cout, " ");
std::cout << ++i_ << "\t: ";
std::copy(first, last, out);
std::cout << '\n';
}
private:
unsigned i_;
};

And then call for_each_permutation with this functor and for each
permutation length you're interested in (1 to 4):

print p;
for (unsigned k = 1; k <= size_array; ++k)
p = for_each_permutation(array, array + size_array, k, p);

The printing functor keeps a simple state which is just the line number.
Note that by passing the same functor back in, and catching it from the
return, the line number is kept up to date. My output looks like:

1 : a
2 : d
3 : e
4 : r
5 : a d
6 : a e
7 : a r
8 : d e
....

Kudos to John Dibling for suggesting the for_each_permutation algorithm.
I think for_each_combination would also be a valuable tool in the box:

template <class BidirectionalIterator, class Size,
class Functor>
Functor
for_each_combination(BidirectionalIterator first,
BidirectionalIterator last, Size k,
Functor f);

template <class BidirectionalIterator, class Size,
class Functor, class Compare>
Functor
for_each_combination(BidirectionalIterator first,
BidirectionalIterator last, Size k,
Functor f, Compare comp);

-Howard
Howard Hinnant, Mar 7, 2005
4. Alex VinokurGuest

"Howard Hinnant" <> wrote in message news:...
[snip]
> There's a closely related article in the Feb. '05 issue of C/C++ Users
> Journal by John Dibling titled "Extending the STL".
>
>
> template <class BidirectionalIterator, class Function, class Size>
> Function
> for_each_permutation(BidirectionalIterator first,
> BidirectionalIterator last,
> Size k,
> Function fn);
>
> The algorithm is documented to come from "The Art of Computer
> Programming," Vol. 1, p. 45, Method 1.

Is there any link to that?

[snip]

> Inspired by John's article, I wrote my own version of
> for_each_permutation

[snip]

--
Alex Vinokur
email: alex DOT vinokur AT gmail DOT com
http://mathforum.org/library/view/10978.html
http://sourceforge.net/users/alexvn
Alex Vinokur, Mar 7, 2005
5. Howard HinnantGuest

In article <d0i3sb\$fvl\$>,
"Alex Vinokur" <> wrote:

> "Howard Hinnant" <> wrote in message
> news:...
> [snip]
> > There's a closely related article in the Feb. '05 issue of C/C++ Users
> > Journal by John Dibling titled "Extending the STL".
> >
> >
> > template <class BidirectionalIterator, class Function, class Size>
> > Function
> > for_each_permutation(BidirectionalIterator first,
> > BidirectionalIterator last,
> > Size k,
> > Function fn);
> >
> > The algorithm is documented to come from "The Art of Computer
> > Programming," Vol. 1, p. 45, Method 1.

>
> Is there any link to that?

Yes: www.cuj.com

You'll have to navigate through their website to find code downloads. A
homepage.

> [snip]
>
> > Inspired by John's article, I wrote my own version of
> > for_each_permutation

>
> Could one see your algorithm?

Sorry, no. For now it must be considered my employer's IP. And
besides, I'm not at all sure the algorithm can't be improved over what I
did, and I'd hate to stifle such work.

The most I can say about it is what I already did: It was a minor
modification of the std::next_permutation that ships with Metrowerks.
And that algorithm is very close to the original HP algorithm which is:

rfind the first pair of adjacent elements in sorted order, and mark the
first of that pair with iterator i.

If no such adjacent elements are found, reverse the list and return
false (no more permutations).

rfind first element greater than *i, mark it with iterator j.

Exchange the elements referred to by i and j, and then reverse the
subrange [i+1, last). Return true.

-Howard
Howard Hinnant, Mar 7, 2005
6. Jeff KishGuest

On Mon, 07 Mar 2005 16:28:12 GMT, Howard Hinnant <>
wrote:

>In article <>,
> Jeff Kish <> wrote:
>
>> Hi.
>>
>> I realize this might be more of a "figure out the algorithm" thing than
>> strictly an std question.. sorry if it is off topic? It certainly was in the
>> other group!
>>
>> Also, I'm pretty old, not in school.. just trying to figure this out., so it
>> isn't an assignment.
>>
>>
>> I see you can use next_permutation to find the permutations of a string of a
>> given length.
>>
>> Right now I'm using a string, sorting it and passing it repeated into
>> next_permutation.
>>
>> Is there any slick way to find all of them of any length, i.e. given a string
>> "dear" to get all of all lengths including:
>>
>> a
>> ra
>> are
>> ear
>> dear
>> dare
>>
>> I'm trying to figure out an algorithm to find all possible words from a set of
>> strings, without using any letters any more than they are in the string, i.e.
>> given lott you would not come up with "loot"

<snip>
>Programming," Vol. 1, p. 45, Method 1.
>
>for_each_permutation calls fn for each permutation of last-first items
>taken k at a time:
>
>fn(first, last)
>
>I think this is a great algorithm, except that I think it would be
>better if the Function were called with only the first k elements of the
>permuted sequence, else you have to store k in fn:
>
>fn(first, first+k)
>
>Inspired by John's article, I wrote my own version of
>for_each_permutation, which uses a slightly modified copy of
>std::next_permutation to take into account that you sometimes only want
>the items taken k at a time. However one could easily modify John's
>publicly available listing to call fn(first, first+k) instead of
>fn(first, last). Note, you might want to use std::advance where I've
>used "+" to avoid requiring random access iterators.
>
>At any rate, once you have this tool, your original problem can be
>solved quite elegantly:
>

<snip>

>
>-Howard

Thanks.
I don't know if I'm up to extending the stl though. My skills are lacking a
bit in this area.
I appreciate the information, and I'll look it over.

Jeff Kish
Jeff Kish, Mar 8, 2005
7. DHOLLINGSWORTH2Guest

While we're on the subject;

Does anyone know where to find a spell checker complete with dictionary in
c/c++ source or LIB files?

Thanks a bunch.
DHOLLINGSWORTH2, Mar 9, 2005
8. Victor BazarovGuest

DHOLLINGSWORTH2 wrote:
> While we're on the subject;
>
> Does anyone know where to find a spell checker complete with dictionary in
> c/c++ source or LIB files?

The web?
Victor Bazarov, Mar 9, 2005
9. MichaGuest

DHOLLINGSWORTH2 wrote:

> Does anyone know where to find a spell checker complete with dictionary in
> c/c++ source or LIB files?

maybe those are useful:

aspell
ispell

Michael
Micha, Mar 10, 2005
10. DHOLLINGSWORTH2Guest

re: aspell, ispell

Cool, Thanks.

Dan
DHOLLINGSWORTH2, Mar 11, 2005