Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Create a random order of (x, y) pairs, without repeating/subsequent x's

Tags:

python

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.

like image 407
slhck Avatar asked Apr 06 '16 15:04

slhck


4 Answers

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
like image 154
B. M. Avatar answered Oct 20 '22 22:10

B. M.


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
like image 22
Vince Avatar answered Oct 20 '22 23:10

Vince


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.

like image 32
Allen Downey Avatar answered Oct 20 '22 23:10

Allen Downey


An interesting question! Here is my solution. It has the following properties:

  • If there is no valid solution it should detect this and let you know
  • The iteration is guaranteed to terminate so it should never get stuck in an infinite loop
  • Any possible solution is reachable with nonzero probability

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
like image 25
wim Avatar answered Oct 20 '22 23:10

wim