Say I have a list of valid X = [1, 2, 3, 4, 5]
and a list of valid Y = [1, 2, 3, 4, 5]
.
I need to generate all combinations of every element in X
and every element in Y
(in this case, 25) and get those combinations in random order.
This in itself would be simple, but there is an additional requirement: In this random order, there cannot be a repetition of the same x
in succession. For example, this is okay:
[1, 3]
[2, 5]
[1, 2]
...
[1, 4]
This is not:
[1, 3]
[1, 2] <== the "1" cannot repeat, because there was already one before
[2, 5]
...
[1, 4]
Now, the least efficient idea would be to simply randomize the full set as long as there are no more repetitions. My approach was a bit different, repeatedly creating a shuffled variant of X
, and a list of all Y * X
, then picking a random next one from that. So far, I've come up with this:
import random
output = []
num_x = 5
num_y = 5
all_ys = list(xrange(1, num_y + 1)) * num_x
while True:
# end if no more are available
if len(output) == num_x * num_y:
break
xs = list(xrange(1, num_x + 1))
while len(xs):
next_x = random.choice(xs)
next_y = random.choice(all_ys)
if [next_x, next_y] not in output:
xs.remove(next_x)
all_ys.remove(next_y)
output.append([next_x, next_y])
print(sorted(output))
But I'm sure this can be done even more efficiently or in a more succinct way?
Also, my solution first goes through all X
values before continuing with the full set again, which is not perfectly random. I can live with that for my particular application case.
A simple solution to ensure an average O(N*M)
complexity:
def pseudorandom(M,N):
l=[(x+1,y+1) for x in range(N) for y in range(M)]
random.shuffle(l)
for i in range(M*N-1):
for j in range (i+1,M*N): # find a compatible ...
if l[i][0] != l[j][0]:
l[i+1],l[j] = l[j],l[i+1]
break
else: # or insert otherwise.
while True:
l[i],l[i-1] = l[i-1],l[i]
i-=1
if l[i][0] != l[i-1][0]: break
return l
Some tests:
In [354]: print(pseudorandom(5,5))
[(2, 2), (3, 1), (5, 1), (1, 1), (3, 2), (1, 2), (3, 5), (1, 5), (5, 4),\
(1, 3), (5, 2), (3, 4), (5, 3), (4, 5), (5, 5), (1, 4), (2, 5), (4, 4), (2, 4),\
(4, 2), (2, 1), (4, 3), (2, 3), (4, 1), (3, 3)]
In [355]: %timeit pseudorandom(100,100)
10 loops, best of 3: 41.3 ms per loop
Here is my solution. First the tuples are chosen among the ones who have a different x value from the previous selected tuple. But I ve noticed that you have to prepare the final trick for the case you have only bad value tuples to place at end.
import random
num_x = 5
num_y = 5
all_ys = range(1,num_y+1)*num_x
all_xs = sorted(range(1,num_x+1)*num_y)
output = []
last_x = -1
for i in range(0,num_x*num_y):
#get list of possible tuple to place
all_ind = range(0,len(all_xs))
all_ind_ok = [k for k in all_ind if all_xs[k]!=last_x]
ind = random.choice(all_ind_ok)
last_x = all_xs[ind]
output.append([all_xs.pop(ind),all_ys.pop(ind)])
if(all_xs.count(last_x)==len(all_xs)):#if only last_x tuples,
break
if len(all_xs)>0: # if there are still tuples they are randomly placed
nb_to_place = len(all_xs)
while(len(all_xs)>0):
place = random.randint(0,len(output)-1)
if output[place]==last_x:
continue
if place>0:
if output[place-1]==last_x:
continue
output.insert(place,[all_xs.pop(),all_ys.pop()])
print output
Here's a solution using NumPy
def generate_pairs(xs, ys):
n = len(xs)
m = len(ys)
indices = np.arange(n)
array = np.tile(ys, (n, 1))
[np.random.shuffle(array[i]) for i in range(n)]
counts = np.full_like(xs, m)
i = -1
for _ in range(n * m):
weights = np.array(counts, dtype=float)
if i != -1:
weights[i] = 0
weights /= np.sum(weights)
i = np.random.choice(indices, p=weights)
counts[i] -= 1
pair = xs[i], array[i, counts[i]]
yield pair
Here's a Jupyter notebook that explains how it works
Inside the loop, we have to copy the weights, add them up, and choose a random index using the weights. These are all linear in n
. So the overall complexity to generate all pairs is O(n^2 m)
But the runtime is deterministic and overhead is low. And I'm fairly sure it generates all legal sequences with equal probability.
An interesting question! Here is my solution. It has the following properties:
I do not know the distribution of the output over all possible solutions, but I think it should be uniform because there is no obvious asymmetry inherent in the algorithm. I would be surprised and pleased to be shown otherwise, though!
import random
def random_without_repeats(xs, ys):
pairs = [[x,y] for x in xs for y in ys]
output = [[object()], [object()]]
seen = set()
while pairs:
# choose a random pair from the ones left
indices = list(set(xrange(len(pairs))) - seen)
try:
index = random.choice(indices)
except IndexError:
raise Exception('No valid solution exists!')
# the first element of our randomly chosen pair
x = pairs[index][0]
# search for a valid place in output where we slot it in
for i in xrange(len(output) - 1):
left, right = output[i], output[i+1]
if x != left[0] and x != right[0]:
output.insert(i+1, pairs.pop(index))
seen = set()
break
else:
# make sure we don't randomly choose a bad pair like that again
seen |= {i for i in indices if pairs[i][0] == x}
# trim off the sentinels
output = output[1:-1]
assert len(output) == len(xs) * len(ys)
assert not any(L==R for L,R in zip(output[:-1], output[1:]))
return output
nx, ny = 5, 5 # OP example
# nx, ny = 2, 10 # output must alternate in 1st index
# nx, ny = 4, 13 # shuffle 'deck of cards' with no repeating suit
# nx, ny = 1, 5 # should raise 'No valid solution exists!' exception
xs = range(1, nx+1)
ys = range(1, ny+1)
for pair in random_without_repeats(xs, ys):
print pair
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With