# Random permutations

Summary:
Algorithm do find all random permutations of n=[0,6)
Summary: Algorithm do find all random permutations of n=[0,6)

Hi,

The following algorithm gives 6 out of the 720 random permutations of integers in the range [0, 6).

Code:
 t=0..5                             // permutation
i=0..5                      // sequence index
n = (t + i) % 6;        // % is the mod operator
n = n*n % 11;           // 11 is prime
n += n>>3;              // >> is the bit shift right operator
n = n & 7;              // & is the bitwise AND operator

I need an optimized code that gives all the 720 random permutations:

Code:
    t=0..719                    // permutation
i=0..5                  // sequence index
n = f(t, i);

mathman
Should move to computer forum.

jedishrfu
Mentor
What language are you using? or is that pseudo code in your example?

pbuk
Gold Member
Optimised how, and why?
• Least number of statements?
• Lowest memory use?
• Fastest execution?
• Most random?
• Most maintanable?
And what do you mean by random?

The easiest way to answer these questions is to write the code yourself (hint: generate all the 720 permutations and then sort the numbers 0..719 into a random order).

jedishrfu
mfb
Mentor
There are existing libraries that can do it, you can check how they do it.
There are recursive algorithms (given a permutation, find the next one e.g. when sorted like a lexicon) and direct algorithms (give me the nth permutation in this order).

Thank you for the kind answers, guys.

I found out exactly what I needed (c language):

Random permutations:
int idx = 6;
unsigned char permutation[] = { 0, 1, 2, 3, 4, 5 };
unsigned char temp[6];

void swap(unsigned char *a, unsigned char *b)
{
int t = *a;
*a = *b;
*b = t;
}

/*
* Prints a different permutation.
*/
void next()
{
while(true)
{
if(idx == 6)
{
int i;
for(i = 0; i < 6; i++)
temp[i] = 0;
idx = 0;
}
if(temp[idx] < idx)
{
if(idx % 2 == 0)
swap(&permutation[0], &permutation[idx]);
else
swap(&permutation[temp[idx]], &permutation[idx]);
permutation[idx]++;
idx = 0;
//
printArray(permutation);
return;
}
else
{
temp[idx] = 0;
idx++;
}
}
}

Every time function next() is called, it prints a different permutation.

Staff Emeritus
direct algorithms (give me the nth permutation in this order).

Can you point me at one of those?

pbuk
Gold Member
Can you point me at one of those?
Do you have Knuth vol 3? Or search for 'factoradic' or 'Lehmer code'. For only 6 elements this is not worth it of course.

It turns out that the OP's requirement was actually much simpler than it seemed from his OP.

mfb
Staff Emeritus
Do you have Knuth vol 3?

I don't, and that was my first thought. :) But thanks, Lehmer code is exactly what I need.

FactChecker