# Shuffling a list while keeping order relative to related elements

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$

• Questions about python are off-topic here. – Yuval Filmus Aug 15 '17 at 22:04
• 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? – D.W. Aug 15 '17 at 22:18
• Stable shuffling? Interesting. – Raphael Aug 16 '17 at 5:08

## 2 Answers

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

• This probably won't be uniform. – Yuval Filmus Aug 16 '17 at 6:17
• 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. – Seth Killian Aug 16 '17 at 7:36
• @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. – James Hollis Aug 16 '17 at 11:30
• @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 – James Hollis Aug 16 '17 at 11:33
• 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. – Seth Killian Aug 16 '17 at 14:06

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