Create a random order of (x, y) pairs, without repeating/subsequent x's
<p>Say I have a list of valid <code>X = [1, 2, 3, 4, 5]</code> and a list of valid <code>Y = [1, 2, 3, 4, 5]</code>.</p>

<p>I need to generate all combinations of every element in <code>X</code> and every element in <code>Y</code> (in this case, 25) and get those combinations in random order.</p>

<p>This in itself would be simple, but there is an additional requirement: In this random order, there cannot be a repetition of the same <code>x</code> in succession. For example, this is okay:</p>

<pre><code>[1, 3]
[2, 5]
[1, 2]
...
[1, 4]
</code></pre>

<p>This is not:</p>

<pre><code>[1, 3]
[1, 2]  &lt;== the "1" cannot repeat, because there was already one before
[2, 5]
...
[1, 4]
</code></pre>

<p>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 <code>X</code>, and a list of all <code>Y * X</code>, then picking a random next one from that. So far, I've come up with this:</p>

<pre><code>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))
</code></pre>

<p>But I'm sure this can be done even more efficiently or in a more succinct way?</p>

<p>Also, my solution first goes through all <code>X</code> values before continuing with the full set again, which is not <em>perfectly</em> random. I can live with that for my particular application case.</p>