Create a permutation list
markredd
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
Victor Bazarov
> 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.
Not permutations, but combinations.
See http://en.wikipedia.org/wiki/Combinations .
> [..]
> Can you describe an algorithm? (I don't need code, I hope I will able
> to develop it!)
Wrong newsgroup. Consider 'comp.programming'. And GIYF.
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Steve Hicks
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
f188e3...@l9g2000yqi.googlegroups.com>, markr...@gmail.com
says...
From a C++ viewpoint, the proper answer would probably be
std::next_permutation (and possibly std::prev_permutation).
--
Later,
Jerry.
Kai-Uwe Bux
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
says...
[ ... ]
> 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.
--
Later,
Jerry.
Francesco S. Carta
> Jerry Coffin wrote:
> > In article <6273cccb-0511-4cb5-acff-
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
Christopher Dearlove
>> "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.
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.