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

Question

假设我有一个有效列表 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 值，然后再继续整个集合，这不是完全随机的。对于我的特定应用案例，我可以接受。

Answer 1

确保平均 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