Shuffle list with 2-back repetition limit python
I have the following list:
a=['airplane','track','car','train']
I would like to create a list that represents each item of this list twice, but prevents the items from being repeated for the next two lines. This means that the plane can only spawn after the plane, as long as there are two different objects between them, so b would be a good candidate:
b=['airplane','track','car','airplane','train','track','car' etc.]
but c won't:
c=['airplane,'track','airplane', etc.]
I was thinking of some kind of brute-force operation where: 1.a is duplicated 2.random.shuffle (a) 3.check for repetition (maybe something like below:
curWord[n]==curWord[n+1]
- Re-shuffle if
TRUE
u start over. (I don't really know that the command was supposed to instruct python to read the true value. I suppose the statementif
would work, but in caseFALSE
I don't know how I would instruct python to proceed
Anyway, while getting answers to the questions defined above would be helpful to my own knowledge, I can see that the implementation I have looked at will probably take a very long time as the list grows.
Any suggestions?
Thanks in advance for your help!
source to share
If you only want one list with two instances of each item, is there a reason this won't work when the original list is longer than two items?
In [138]: a=['airplane','track','car','train']
In [139]: a + a
Out[139]: ['airplane', 'track', 'car', 'train', 'airplane', 'track', 'car', 'train']
If you are asking a more abstract question: "How to choose from the permutation space of list items so that they do not appear in two items of the same item" then the following should work.
Note that getting some structure in which the items appear twice is as easy as getting a + a
, and then you might worry about limiting the permutations a + a
— you don't have to overdo the "how to get two out of each" part of the problem.
import random
def valid_duplicate_spacing(x):
for i, elem in enumerate(x):
if elem in x[i+1:i+3]:
return False
return True
def sample_permutations_with_duplicate_spacing(seq):
sample_seq = seq + seq
random.shuffle(sample_seq)
while not valid_duplicate_spacing(sample_seq):
random.shuffle(sample_seq)
return sample_seq
Then it can be used like this:
In [165]: sample_permutations_with_duplicate_spacing(a)
Out[165]: ['airplane', 'train', 'track', 'car', 'train', 'track', 'car', 'airplane']
In [166]: sample_permutations_with_duplicate_spacing(a)
Out[166]: ['train', 'airplane', 'car', 'track', 'train', 'airplane', 'track', 'car']
If you are only talking about random sampling from the list so that the sample is not swapped for the next two draws, you can use a generator:
import random
def draw_with_delayed_replacement(seq):
drawn = random.choice(seq)
rejectables = [drawn]
yield drawn
drawn = random.choice(seq)
while drawn in rejectables:
drawn = random.choice(seq)
rejectables.append(drawn)
yield drawn
while True:
drawn = random.choice(seq)
if drawn in rejectables:
continue
else:
rejectables.pop(0)
rejectables.append(drawn)
yield drawn
Then you can do the following:
In [146]: foo = draw_with_delayed_replacement(a)
In [147]: foo.next()
Out[147]: 'car'
In [148]: foo.next()
Out[148]: 'train'
In [149]: foo.next()
Out[149]: 'track'
In [150]: foo.next()
Out[150]: 'car'
In [151]: foo.next()
Out[151]: 'train'
In [152]: foo.next()
Out[152]: 'track'
In [153]: foo.next()
Out[153]: 'car'
In [154]: foo.next()
Out[154]: 'airplane'
In [155]: foo.next()
Out[155]: 'track'
In [156]: foo.next()
Out[156]: 'train'
However, in this case, you cannot guarantee that you will get a sample where each item appears exactly twice, and this may be ineffective for small lists.
source to share
Here is my solution, which does not guarantee that each token appears exactly n times.
It is easy to extend my solution to guarantee this, but this would lead to a possible deadlock scenario that would need to be checked for this.
>>> def magicsequence(tokens, length):
... sequence = []
... while len(sequence) < length:
... candidate = random.choice(tokens)
... if candidate not in sequence[-2:]:
... sequence.append(candidate)
... return sequence
source to share
Here is a solution that satisfies the constraints and always returns a list with each element twice. It runs in O (n ^ 2) time, where n is the length of the list.
from collections import Counter
from itertools import permutations
from random import choice, shuffle
def shuffle_with_constraints(x):
if len(x) < 3:
raise ValueError("Lists with length less than 3 have no valid shuffles")
output = []
#a counter representing how many times we still need to insert an element
available = Counter(x*2)
while available:
if len(output) == len(x)*2-6: #we just need to insert six elements
distinct = len(available) #how many distinct elements we need to insert
if distinct == 6:
pass #there is no problem
elif distinct == 3: #only six possibilities
end = list(available)
shuffle(end)
return output + end*2
else:
#enumerate all 720 permutations and select a valid one
possibles = [possible for possible in permutations(available.elements())
if valid_6_shuffle(possible)]
return output+list(choice(possibles))
#choose a valid element and append it to the output
next = choice(list(set(available)-set(output[-2:])))
output.append(next)
#remove it from the availables
if available[next] == 2:
available[next] -= 1
else:
del available[next]
return output
def valid_6_shuffle(x):
for a,b,c in zip(x,x[1:],x[2:]):
if a==b or b==c or a==c:
return False
return True
source to share