permutations and combinations

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

  1. Jeff Kish

    Jeff Kish Guest

    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
    Jeff Kish, Mar 7, 2005
    #1
    1. Advertising

  2. 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
    > 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
    Victor Bazarov, Mar 7, 2005
    #2
    1. Advertising

  3. 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
    > 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::eek: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
    #3
  4. Jeff Kish

    Alex Vinokur Guest

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



    --
    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
    #4
  5. 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".
    > >
    > > 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
    Howard Hinnant, Mar 7, 2005
    #5
  6. Jeff Kish

    Jeff Kish Guest

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

    <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
    #6
  7. 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
    #7
  8. 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
    #8
  9. Jeff Kish

    Micha Guest

    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
    #9
  10. re: aspell, ispell

    Cool, Thanks.

    Dan
    DHOLLINGSWORTH2, Mar 11, 2005
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. jose luis fernandez diaz

    Combinations/permutations algorithm in C++

    jose luis fernandez diaz, Apr 13, 2004, in forum: C++
    Replies:
    6
    Views:
    14,109
    Leor Zolman
    Apr 13, 2004
  2. Alex Vinokur
    Replies:
    2
    Views:
    2,792
    Alex Vinokur
    May 13, 2004
  3. Replies:
    6
    Views:
    462
  4. Seth Leija

    Combinations or Permutations

    Seth Leija, Sep 20, 2010, in forum: Python
    Replies:
    4
    Views:
    271
    Raymond Hettinger
    Sep 21, 2010
  5. Peter Ensch
    Replies:
    5
    Views:
    207
Loading...

Share This Page