permutations and combinations

[Jeff Kish]

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

 

[Victor Bazarov]

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

 

[Howard Hinnant]

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
read
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".

In this article he defines a generic algorithm:

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

 

[Alex Vinokur]

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

In this article he defines a generic algorithm:

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

Could one see your algorithm?

[snip]

 

[Howard Hinnant]

[snip]

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

In this article he defines a generic algorithm:

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
direct link to their downloads page will just redirect you back to their
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

 

[Jeff Kish]

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:

-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

 

[DHOLLINGSWORTH2]

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.

 

[Victor Bazarov]

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?

 

[Micha]

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

 

[DHOLLINGSWORTH2]

re: aspell, ispell

Cool, Thanks.

Dan