Random permutations

  • Thread starter intervoxel
  • Start date
  • #1
195
1
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);

Thanks for any answer.
 

Answers and Replies

  • #2
mathman
Science Advisor
7,986
513
Should move to computer forum.
 
  • #3
13,114
6,995
What language are you using? or is that pseudo code in your example?
 
  • #4
pbuk
Science Advisor
Gold Member
2,524
1,256
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).
 
  • #5
35,667
12,228
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).
 
  • #6
195
1
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.
 
  • #7
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
27,633
11,838
direct algorithms (give me the nth permutation in this order).

Can you point me at one of those?
 
  • #8
pbuk
Science Advisor
Gold Member
2,524
1,256
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.
 
  • #9
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
27,633
11,838
Do you have Knuth vol 3?

I don't, and that was my first thought. :) But thanks, Lehmer code is exactly what I need.
 
  • #10
FactChecker
Science Advisor
Gold Member
6,572
2,644
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.
 

Related Threads on Random permutations

  • Last Post
Replies
3
Views
9K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
2
Views
6K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
13
Views
3K
  • Last Post
Replies
7
Views
4K
  • Last Post
Replies
11
Views
941
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
5
Views
795
  • Last Post
Replies
4
Views
540
Top