如何在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个元素，这样计算所有可能的排列需要很长时间。

有没有一种有效的方法来处理这个问题？

- user3447696

---

这里的目标是什么？你总是会有相同比例的1和0吗？它需要是随机的吗？ - jonrsharpe

如果1的数量比0多，会怎样？ - nsfyn55

如果您无法保留原始的零和一的数量，该怎么办？（例如，如果您的原始列表看起来像 [0, 1, 1, 1, 1, 1]？ - Savir

我始终会有20个总的1和0。其中将始终有六个1，其余将是0，就像上面的例子一样。我需要它是随机的。 - user3447696

Answer 1

我有一个基于分区的相对聪明的方法，但是既然你说总是有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]

- DSM

---

我现在也很好奇。分区方法会是什么样子呢？拜托了 :-) - Savir

Answer 2

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

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

- גלעד ברקן

---

这可能会产生两个相邻的1。 - DSM

@DSM 对不起，你说了什么？ - גלעד ברקן

现在它无法产生一个前导的 1。修复很容易；在 row 中再添加一个 0 并丢弃洗牌的第一个数字即可。 - David Eisenstat

@DavidEisenstat 谢谢你，David！已修复（我想）。 - גלעד ברקן

Answer 3

由于一行中1的数量是固定的，而且您不希望任何1相邻，因此让m为1的数量，k为该行中0的数量。然后，您想要将m个1随机放置在（k+1）个位置中，以便每个位置最多只有一个1。这相当于从集合（1,2,...,k+1）中选择大小为((k+1) choose m)的随机子集。这很容易做到。给定随机子集的选择，您可以构造您的0和1的随机排列，以使没有两个1相邻。随机选择算法需要O(m)时间。

- user2566092

Answer 4

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

- Terje D.