5
$\begingroup$

I'm looking to shuffle a list of the elements $a_1,\dots, a_6, \dots, e_1, \dots, e_6$

while keeping two rules:

if I loop though the list and filter out a specific letter or number it should be in order:

$a_1, a_2, a_3 \dots$ or $a_1, b_1, c_1 \dots$

How can I shuffle the list keeping these rules? I'm using python, so if there's a library that'd be great. Otherwise, just a generic way I could tackle this problem.

Here's an example of a shuffle that would fit the criteria:

$a_1, b_1, a_2, b_2, c_1, a_3, d_1, c_2, d_2, e_1, a_4, b_3,$ $c_3, d_3, b_4, d_4, c_4, a_5, e_2, d_5, e_3, c_5, a_6, b_5, e_4, a_7, $ $b_6, c_6, b_7, d_6, e_5, e_6, c_7, d_7, e_7$

Improve this question
$\endgroup$
3
  • $\begingroup$ Questions about python are off-topic here. $\endgroup$
    – Yuval Filmus
    Aug 15, 2017 at 22:04
  • $\begingroup$ I don't understand what you are asking. What is the input? What are the outputs, and how do they relate to the inputs? What do you mean by "shuffle"? I would have expected that "shuffle" means "re-order the elements", but then why do you mention filtering out items? What do you mean by in order? I don't understand your notation or what problem you are trying to solve. Can you edit it to clarify? $\endgroup$
    – D.W. ♦
    Aug 15, 2017 at 22:18
  • $\begingroup$ Stable shuffling? Interesting. $\endgroup$
    – Raphael ♦
    Aug 16, 2017 at 5:08

2 Answers 2

Reset to default
1
$\begingroup$

Something like this perhaps?

from random import randint
letter_count = [0] * 5

for _ in range(35):
    while True:
        letter = randint(0,4)
        if letter == 0 or letter_count[letter-1] > letter_count[letter]:
            if letter_count[letter] < 7:
                break

    letter_count[letter] += 1
    print(chr(97+letter),letter_count[letter])

It works, in a quick and dirty fashion, but it does not have a uniform distribution. You would calculate the probability of a sequence occurring by dividing by the number of possible elements at each step. At some point in the example you might have 5 possible elements and the probability of the sequence occurring would be 1/(some multiple of 5). For other sequences there would never be 5 possible elements and the probabilty of that sequence would be 1/(not a multiple of 5).

Improve this answer
$\endgroup$
6
  • $\begingroup$ This probably won't be uniform. $\endgroup$
    – Yuval Filmus
    Aug 16, 2017 at 6:17
  • $\begingroup$ This is good. I'm going to work on introducing a bit of bias to ensure there aren't there of the same number in a row or things like that like (c1, d1, e1). Thanks for getting me started. $\endgroup$
    – Seth Killian
    Aug 16, 2017 at 7:36
  • $\begingroup$ @SethKillian If you are doing Monte Carlo simulation or something like that and you need a uniform distribution, you can't just tweak this code a bit, you'll need a completely different algorithm (see Yuval's answer). I posted this because Yuval's answer (particularly Matthews' paper) is pretty heavy stuff and if you didn't say you needed uniform distribution. $\endgroup$
    – James Hollis
    Aug 16, 2017 at 11:30
  • $\begingroup$ @SethKillian Also, the sequences generated do seem rather nonrandom at the beginning and end (eg a1,a2,a3), but I suspect this is an illusion due to the limited number of possible elements that can appear. It may not be a good idea to try and 'fix' it $\endgroup$
    – James Hollis
    Aug 16, 2017 at 11:33
  • $\begingroup$ Basically what I'm trying to do is make a language quiz app where each letter is a word and each number is an associated type of question. 1 is the introduction, two is the multiple choice in english, three is a question where they type the word in, four is multiple choice in the language and five is another typing (6 and 7 same concept). That's why they need to be ordered a1, a2, a3, a4, a5, a6, a7. In order to make it interesting, I want to shuffle them while keeping a certain order (a3 never before a1 and c5 not before b5). The problem with this is I often run into a1, b1, c1. $\endgroup$
    – Seth Killian
    Aug 16, 2017 at 14:06
8
$\begingroup$

Your problem can be phrased as generating a random linear extension of a partial order. The partial order in your phrase is generated by your constraints. There is a classical algorithm of Matthews described in his paper Generating a random linear extension of a partial order. This might even be implemented in some library.

Your particular case is generating a random lattice word of certain content (for the reduction, delete all letters or all numbers). This is a concept occurring in representation theory of the symmetric groups, generalizing the classical ballot sequences. If you're lucky you might find an algorithm for generating a random lattice word (in Mupad, for example, somebody implemented an algorithm for generating all lattice words).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.