Re: Algorithm to generate different combinations based on N numbers

From: Alex Vinokur (alexvn_at_big.foot.com)
Date: 05/11/04 

Date: Tue, 11 May 2004 18:26:23 +0300

"Peter R" <peter_ross@canada.com> wrote in message news:f67ccf1.0405102043.3107ffbb@posting.google.com...
> 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[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[i] << " ";
  }
  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:alexvn@connect.to
     http://mathforum.org/library/view/10978.html

Relevant Pages