Блог пользователя rsFalse

help with random permutations problem
Автор rsFalse, история, 8 лет назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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 .

→ Ответить