如何检查列表中的邻接关系并在Python中修复邻接关系

Question

我有这样一个列表：

row = [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

接下来我需要把这个列表打乱或者随机排列一下：

shuffle(row)

然后我需要检查一下，找出任何相邻的1，并把它们移动开，确保它们之间至少有一个0。比如，我希望结果看起来像这样：

row = [0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0]

我不太确定寻找相邻的1并把它们分开的最有效的方法是什么……而且我还需要反复进行这个操作，以便得到多个不同的组合。

最开始列表比较短的时候，我是这样做的：

row = [1, 1, 1, 0, 0, 0, 0, 0, 0, 0]
rowlist = set(list(permutations(row)))
rowschemes = [(0, 0) + x for x in rowlist if '1, 1' not in str(x)]

但是现在我的列表有20个元素，这样做就需要花费很长时间才能得到所有可能的排列。

有没有什么更有效的方法可以做到这一点呢？

Answer 1

因为每一行中1的数量是固定的，而且你不希望有两个1挨在一起，所以我们用m来表示1的数量，用k来表示0的数量。这样，你就想把m个1放在(k+1)个位置上，确保每个位置最多只能放一个1。这就相当于从(1,2,...,k+1)这个集合中随机选择一个大小为m的子集。这个过程其实很简单。选好这个随机的子集后，你就可以根据这个选择来构造你的0和1的随机排列，确保没有两个1是相邻的。这个随机选择的算法大约需要O(m)的时间。

Answer 2

把6个1和5个0放到一个列表里，形成如下：

row = [1,0,1,0,1,0,1,0,1,0,1]

然后把剩下的0一个一个地随机插入到这个（逐渐变大的）列表里。

for i in range(11,19):
    row.insert(random.randint(0,i), 0)

Answer 3

我之前想了一个还不错的分区方法，但因为你提到总是有20个数字和6个1，而6这个数字比较小，所以我们可以列出所有可能的位置（总共有38760种），然后把那些不合法的去掉。接着，你可以从剩下的有效位置中随机选择，最后构建出你想要的那一行：

import random
from itertools import combinations

def is_valid(locs):
    return all(y-x >= 2 for x,y in zip(locs, locs[1:]))

def fill_from(size, locs):
    locs = set(locs)
    return [int(i in locs) for i in range(size)]

然后

>>> size = 20
>>> num_on = 6
>>> on_locs = list(filter(is_valid, combinations(range(size), num_on)))
>>> len(on_locs)
5005
>>> fill_from(size, random.choice(on_locs))
[0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1]
>>> fill_from(size, random.choice(on_locs))
[0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
>>> fill_from(size, random.choice(on_locs))
[1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1]

Answer 4

为什么不直接去追求你想要的东西呢？比如说：

row = ["0","0","0","0","0","0","0","0","0","01","01","01","01","01","01"]
random.shuffle(row)
print (map(int, list("".join(row)[1:])))