Re: generate random permutation
- To: mathgroup at smc.vnet.net
- Subject: [mg40355] Re: generate random permutation
- From: "AngleWyrm" <no_spam_anglewyrm at hotmail.com>
- Date: Wed, 2 Apr 2003 04:37:58 -0500 (EST)
- References: <b66c98$fqs$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
The number of possible permutations to a set of number S = { a1, a2, ...
an } is n!, which is ( 1 x 2 x ... x n ). This multiplication is O(n) in
terms of performance, because the function must perform an extra multiply
for every increase in the size of the set. One could express it in C++ like
so:
#include <cstdlib>
#include <iostream>
#include <set>
int main (void)
{
// A set of four integers
set<int> myNums;
myNums.insert(42);
myNums.insert(69);
myNums.insert(1);
myNums.insert(100);
cout << "\nSize: " << myNums.size() << endl;
/***** My Generic Permutation Algorithm ***/
long numPermutations = myNums.size();
int counter = myNums.size();
while( --counter ) {
numPermutations *= counter;
}
/************************************/
cout << "\nTotal number of permutations is: " << numPermutations <<
endl;
system("Pause");
return 0;
}
But you could do better, if you know in advance a ceiling on the size of the
set! Consider this: The number of permutations for ALL sizes of sets is a
series of numbers, which could simply be hard-coded into an array of the
appropriate size. If you know that the maximum size of your set is, say
1000, then pregenerate the first thousand permutations and hard-code them in
an array. Then at run time, all you would have to do is:
numPermutations = permutationLookupTable[ myNums.size() ];
An O(1) operation!