rsFalse's blog

help with random permutations problem
By rsFalse, history, 8 years ago, In English

Hello,
I had a problem: make sequence of random permutations which elements do not occur in same positions. E.g. I have list ('a', 'b', 'c', 'd'). I randomly generate permutation, say 'a d b c', then next permutation, say 'd c a b, then next permutation can not start with 'a' and 'd', because these elements occurs in first or second sequence on same position.
My algorithm is slow: I repeat to generate random (with Fisher-Yates shuffle) permutation and check each element if it not occur in previous sequences (I used 2D array). How to determine what is the complexity of my algorithm?
How to solve problem faster?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rsFalse (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

How many such permutations do you have to generate? Surely, not more than n, since that is not possible.

So, you can just do rotations.

For example, here are 4 permutations with n = 4:

a b c d

b c d a

c d a b

d a b c

And, here are 5 permutations with n = 5:

a b c d e

b c d e a

c d e a b

d e a b c

e a b c d

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Yes, I can rotate, but how could I obtain randomly distributed permutations?
    I need to generate m permutations, m <= n, where n is number of elements.

    → Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Try "Generating Uniformly Distributed Random Latin Squares" (on sci-hub for example). Looks complicated though.

It looks like this algorithm is implemented in SAGE, see http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/matrices/latin.html .

→ Reply