# Algorithm to generate different combinations based on N numbers

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

1. ### Peter RGuest

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

2. ### Alf P. SteinbachGuest

* (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.

[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

3. ### Alex VinokurGuest

"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