Re: permutations and combinations

From: Howard Hinnant (hinnant_at_metrowerks.com)
Date: 03/07/05 

Date: Mon, 07 Mar 2005 16:28:12 GMT

In article <tmno215fjqcmso48dbv69uubsu3b36s6d6@4ax.com>,
 Jeff Kish <jeff.kish@mro.com> 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
> 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::ostream_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

Relevant Pages

  • Re: permutations
    ... make a list of the permutation of the string you have left. ... The algorithm is recursive -- making a list of permutations is done from ... void swap(char *s, char *t) ...
    (comp.lang.c)
  • Re: permutations
    ... make a list of the permutation of the string you have left. ... The algorithm is recursive -- making a list of permutations is done from a ... void swap(char *s, char *t) ...
    (comp.lang.c)
  • This Weeks Finds in Mathematical Physics (Week 226)
    ... The first week they had lots of talks on "higher-dimensional rewriting", ... to find two files that give the same bit string. ... Now, if you're a mathematician, the whole idea of a cryptographic ... You can see the algorithm for this ...
    (sci.math.research)
  • This Weeks Finds in Mathematical Physics (Week 226)
    ... The first week they had lots of talks on "higher-dimensional rewriting", ... to find two files that give the same bit string. ... Now, if you're a mathematician, the whole idea of a cryptographic ... You can see the algorithm for this ...
    (sci.physics.research)
  • Re: Attention Sean - question about CSI
    ... the best compression algorithm you have. ... It should compress very ... which compresses that string to a single bit. ... from the binary code, and use it to decompress the data, then ...
    (talk.origins)