Re: Create a permutation list
On 30 Set, 22:08, Kai-Uwe Bux <jkherci...@gmx.net> wrote:
Jerry Coffin wrote:
In article <6273cccb-0511-4cb5-acff-
f188e37b6...@l9g2000yqi.googlegroups.com>, markred...@gmail.com
says...
Hello world,
I'm looking for an algorithm in order to perform this operation: I
have a set of N possible values and I want to generate all the
possibile permutations composed by M slots without repetitions and not
considering the order.
Note: I don't know what are the values of N and M befor the software
starts, so i have to implement it at run-time.
For example, if N=4 with values {1 , 2 , 3 , 4} and M=3, I will ob=
tain
only 4 combinations, for example:
(1,2,3) [or (3,2,1), or (2,1,3), the order doesn't matter]
(1,3,4)
(1,2,4)
(2,3,4)
Can you describe an algorithm? (I don't need code, I hope I will able
to develop it!)
From a C++ viewpoint, the proper answer would probably be
std::next_permutation (and possibly std::prev_permutation).
I guess, there is a confusion caused by the OP's use of "permutation" in =
the
subject line. The example of the post, however, makes is pretty clear tha=
t
the OP really wants to iterate through the list of M-element subsets of a=
n
N-element set. He even points out that order does not matter.
Hint to the OP: think of the numbers 0, 1, 2, ..., 2^N - 1. These are
exactly the numbers that can be encoded by N bits, i.e., they correspond =
to
subsets of an N-element set (the 1-bits indicate the chosen elements). Yo=
u
could now create a next_M_subset() function by answering the following
question:
Given a number k in [0,2^N) that has M set bits, what is the
next number that has M bits set?
E.g.: N = 5, M = 3 would yield the following order:
00111
01011
01110
10011
10101
10110
11001
11010
11100
I suppose the OP wasn't after any homework, and even in such case,
that should be past due after a week (this sentence is about the fact
that I'm posting a working algorithm, nothing more).
Whatever, here is my implementation of the above suggestion:
-------
#include <iostream>
#include <sstream>
#include <vector>
#include <iomanip>
using namespace std;
typedef vector<unsigned> Combo;
typedef vector<Combo> Combos;
Combos combinations(unsigned slots, unsigned elements) {
Combos combos;
if (slots && slots <= elements) {
vector<bool> flags;
Combo combo;
for(unsigned i = 0; i < elements; ++i) {
flags.push_back(i < slots);
}
do {
for(unsigned i = 0, e = flags.size(); i < e; ++i) {
if(flags[i]) combo.push_back(i);
}
combos.push_back(combo);
combo.clear();
} while (prev_permutation(flags.begin(), flags.end()));
}
return combos;
}
string qty(unsigned number, const string& noun) {
ostringstream oss;
unsigned pos = noun.find("|");
oss << number;
oss << noun.substr(0, pos);
if(number != 1 && pos < noun.size()-1) {
oss << noun.substr(pos+1);
}
return oss.str();
}
ostream& operator<<(ostream& os, const Combo& combo) {
os << "{ ";
if(unsigned combo_size = combo.size()) {
for(unsigned i = 0; i < combo_size -1; ++i) {
os << combo[i] << ", ";
}
os << combo.back() << " ";
}
os << "}";
return os;
}
ostream& operator<<(ostream& os, const Combos& combos) {
os << qty(combos.size(), " combination|s") << endl;
for(unsigned i = 0, e = combos.size(); i < e; ++i) {
os << " " << setw(4) << (i+1) << ": " << combos[i] << endl;
}
return os;
}
void print_combinations(unsigned slots, unsigned elements) {
cout << " " << qty(elements, " element|s");
cout << ", arranged in\n " << qty(slots, " slot|s");
cout << ", generate" << ( elements == 1 ? "s\n " : "\n " );
cout << combinations(slots, elements) << endl;
}
int main() {
print_combinations(0, 0);
print_combinations(0, 1);
print_combinations(1, 0);
print_combinations(1, 1);
print_combinations(4, 5);
return 0;
}
-------
Like it?
--
Francesco S. Carta, http://fscode.altervista.org