Algorithm to generate different combinations based on N numbers

Discussion in 'C++' started by Peter R, May 11, 2004.

  1. Peter R

    Peter R Guest

    Hi,

    Probably this question was asked before, but what is the algorithm to
    generate all combinations based on N numbers?

    For example, for 3 elements = {1,2,3}, I'd like to generate a list of
    (2^n - NULL):
    1, 2, 3
    1, 2
    2, 3
    1, 3
    1,
    2,
    3,

    For 4 elements = {1,2,3,4}, it'll be
    1,2,3,4
    1,2,3
    1,2,4
    1,3,4
    2,3,4
    1,2
    1,3
    1,4
    2,3
    2,4
    3,4
    1
    2
    3
    4

    Thanks,
    P Ross
    Peter R, May 11, 2004
    #1
    1. Advertising

  2. * (Peter R) schriebt:
    >
    > Probably this question was asked before, but what is the algorithm to
    > generate all combinations based on N numbers?


    In C++ you can use std::bitset to access the bits of value. You can
    alternatively use the shift operator << and bit-level and, &. The first
    can be more clear, the latter more efficient.

    The above assumes you use the straightforward algorithm of counting from
    1 to 2^N-1, inclusive.

    For details about this and other _algorithms_, please do ask in e.g.
    [comp.programming], since that question is off-topic in this group.

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is top-posting such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
    Alf P. Steinbach, May 11, 2004
    #2
    1. Advertising

  3. Peter R

    Alex Vinokur Guest

    "Peter R" <> wrote in message news:...
    > Hi,
    >
    > Probably this question was asked before, but what is the algorithm to
    > generate all combinations based on N numbers?
    >
    > For example, for 3 elements = {1,2,3}, I'd like to generate a list of
    > (2^n - NULL):
    > 1, 2, 3
    > 1, 2
    > 2, 3
    > 1, 3
    > 1,
    > 2,
    > 3,
    >
    > For 4 elements = {1,2,3,4}, it'll be
    > 1,2,3,4
    > 1,2,3
    > 1,2,4
    > 1,3,4
    > 2,3,4
    > 1,2
    > 1,3
    > 1,4
    > 2,3
    > 2,4
    > 3,4
    > 1
    > 2
    > 3
    > 4
    >
    > Thanks,
    > P Ross



    For instance,

    ------ C++ code : BEGIN ------

    #include <cassert>
    #include <vector>
    #include <set>
    #include <iostream>
    #include <sstream>
    #include <iterator>
    using namespace std;

    typedef unsigned long ulong;

    // ------------------------
    struct less_functor
    {
    bool operator()(
    const vector<int>& left_i,
    const vector<int>& right_i
    )
    {
    if (left_i.size() < right_i.size()) return true;
    if (left_i.size() > right_i.size()) return false;

    return (left_i < right_i);
    }
    };


    // ------------------------
    set<vector<int>, less_functor> get_permut (ulong);
    set<vector<int>, less_functor> get_permut (const vector<int>&);


    // ------------------------
    set<vector<int>, less_functor> get_permut (ulong size_i)
    {
    vector<int> abt;
    for (ulong i = 0; i < size_i; i++) abt.push_back (i + 1);
    return get_permut (abt);
    }


    // ------------------------
    set<vector<int>, less_functor > get_permut (const vector<int>& abt_i)
    {
    set<vector<int>, less_functor > ret_sv;
    if (abt_i.size() == 0) return ret_sv;

    if (abt_i.size() == 1)
    {
    ret_sv.insert (vector<int> (1, abt_i[0]));
    return ret_sv;
    }


    for (ulong i = 0; i < abt_i.size(); i++)
    {
    vector<int> abt (abt_i);
    abt.erase(remove(abt.begin(), abt.end(), abt_i), abt.end());
    const set<vector<int>, less_functor> tmp_sv (get_permut(abt));

    for (set<vector<int>, less_functor>::const_iterator pos_iter = tmp_sv.begin();
    pos_iter != tmp_sv.end();
    pos_iter++
    )
    {
    ret_sv.insert (*pos_iter);
    }

    }
    ret_sv.insert (abt_i);

    return ret_sv;

    }


    int main (int argc, char** argv)
    {
    const bool condition_argc (argc == 2);

    cout << endl;
    cout << " YOUR COMMAND LINE : ";
    for (long i = 0; i < argc; i++)
    {
    cout << argv << " ";
    }
    cout << endl;
    cout << endl;

    if (!condition_argc)
    {
    cout << ""
    << " USAGE : "
    << argv[0]
    << " <size of alphabet>"
    << endl;
    return 1;
    }

    assert (condition_argc);

    const long abt_size (atoi(argv[1]));
    if (abt_size < 0)
    {
    cout << "ERROR : <size of alphabet> must be non-negative"
    << endl
    << "Actual value = "
    << abt_size
    << endl;
    return 1;
    }


    const set<vector<int>, less_functor> out (get_permut (ulong (abt_size)));
    for (set<vector<int>, less_functor>::const_iterator pos_iter = out.begin();
    pos_iter != out.end();
    pos_iter++
    )
    {
    ostringstream oss;
    copy (pos_iter->begin(), pos_iter->end(), ostream_iterator<int>(oss, ", "));
    cout << oss.str().substr (0, oss.str().size() - 2) << endl;
    }

    return 0;
    }


    ------ C++ code : END --------


    --
    Alex Vinokur
    mailto:
    http://mathforum.org/library/view/10978.html
    Alex Vinokur, May 11, 2004
    #3
    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,110
    Leor Zolman
    Apr 13, 2004
  2. Replies:
    0
    Views:
    3,116
  3. deancoo
    Replies:
    2
    Views:
    428
    deancoo
    Feb 25, 2005
  4. cayblood
    Replies:
    8
    Views:
    515
    Victor Bazarov
    Nov 2, 2005
  5. Alexander Antonakakis

    Help on algorithm to calculate combinations

    Alexander Antonakakis, Feb 25, 2010, in forum: Ruby
    Replies:
    8
    Views:
    144
    Josh Cheek
    Feb 25, 2010
Loading...

Share This Page