Create a permutation list

[markredd]

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 obtain
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!)
thanks

 

[Steve Hicks]

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 obtain
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!)
thanks

It seems to me like you want a recursive function, for a number of
reasons: M being unspecified means you can't just hardcode for loops;
also, mathematically, you can write the task inductively - the N=4,M=3
task is just 1..4 prepending a task with reduced N (3, 2, 1, or 0) and
M=2. Note that in this case, the lower bound is different. Thus, you
want a function something like

vector<vector<int>> permutations(int n,int m,int start=1,vector<int>
prepend=vector<int>())

that would return all the permutations of m items from [start..n],
prepended with prepend (your base cases are m=1 and start>n, and
optionally m=0).

Obviously you could do some simple optimizations such as wrapping this
in another function and passing the vector<vector<int>> by reference
to avoid copying lots of stuff. If you wanted to think "functionally"
you could possibly pass a function<vector<int>(vector<int>)> instead
to keep track of the prepending, though I haven't yet played out how
all the memory management work out in that case.

Is that clear enough to get started? If not, I could write more.
HTH,
steve

 

[Jerry Coffin]

(e-mail address removed)>, (e-mail address removed)
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 obtain
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:rev_permutation).

 

[Kai-Uwe Bux]

(e-mail address removed)>, (e-mail address removed)
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 obtain
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:rev_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 that
the OP really wants to iterate through the list of M-element subsets of an
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). You
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

Also note that comp.programming is better suited for language independent
questions.


Best

Kai-Uwe Bux

 

[Jerry Coffin]

[ ... ]

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 that the OP really wants to iterate
through the list of M-element subsets of an N-element set. He even
points out that order does not matter.

You're right -- I should have read his post more carefully before I
responded. My apologies for a boneheaded post.

 

[Francesco S. Carta]

(e-mail address removed)>, (e-mail address removed)
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 obtain
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:rev_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 that
the OP really wants to iterate through the list of M-element subsets of an
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). You
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) 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 << ", ";
}
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 << 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;
}

 

[Christopher Dearlove]

You're right -- I should have read his post more carefully before I
responded. My apologies for a boneheaded post.

There was a submission to the C++ standardisation process (sorry, I'm
not going to try to find it but it was either in 2008 or 2009) that proposed
adding std::next_combination, and other related functions, and gave some
example code. (It was too late for C++0X, maybe it will make a TC. If
so I suggested to the author a couple more functions that I found I needed
for related functionality when borrowing that code.) It'll be in the C++0X
archives as nxxxx for some xxxx.