Algorithm to generate different combinations based on N numbers

[Peter R]

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

[Alf P. Steinbach]

* pe********@canada.com (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?

[Alex Vinokur]

"Peter R" <pe********@canada.com> wrote in message news:f6*************************@posting.google.co m...

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:al****@connect.to
http://mathforum.org/library/view/10978.html