创建 (x, y) 对的随机顺序，不重复/后续的 x

假设我有一个有效的列表X = [1, 2, 3, 4, 5]以及有效的列表Y = [1, 2, 3, 4, 5].

我需要生成中每个元素的所有组合X以及中的每个元素Y（在本例中为 25）并按随机顺序获取这些组合。

这本身很简单，但有一个额外的要求：在这个随机顺序中，不能有相同的重复x陆续。例如，这样就可以了：

[1, 3]
[2, 5]
[1, 2]
...
[1, 4]

这不是：

[1, 3]
[1, 2]  <== the "1" cannot repeat, because there was already one before
[2, 5]
...
[1, 4]

现在，效率最低的想法是简单地随机化整个集合，只要不再有重复。我的方法有点不同，反复创建一个打乱的变体X，以及所有的列表Y * X，然后从中随机选择下一个。到目前为止，我已经想出了这个：

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

但我确信这可以更有效或更简洁地完成？

另外，我的解决方案首先遍历所有X再次继续全套操作之前的值，这不是完美随机的。对于我的特定应用案例，我可以接受这一点。

确保平均的简单解决方案O(N*M)复杂：

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

一些测试：

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