Optimized Algorithm to Find All 720 Random Permutations of [0, 6)

[intervoxel]

TL;DR 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).

 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:

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

Thanks for any answer.

 

[mathman]

Should move to computer forum.

 

[jedishrfu]

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

 

[pbuk]

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).

 

[mfb]

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).

 

[intervoxel]

Thank you for the kind answers, guys.

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

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.

 

[Vanadium 50]

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

Can you point me at one of those?

 

[pbuk]

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.

 

[Vanadium 50]

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]

Just to clarify, do you mean to determine all possible permutations and put them in a random order? If so, I would do it in exactly those two steps.
1) Make a methodical non-random list of all possible permutations.
2) Put that list into a random order.

On the other hand, suppose you want to generate a sequence of random permutations, with all permutations equally likely, and allowing repeats. The is an entirely different problem. But you can still make the list of step 1) above and repeatedly select one at random as long as you like.