如何将列表中的项目重新排列为4个组，以便组中的项目之前没有与该组中的其他项目组合？

Question

因此，我的女朋友被要求将女孩的女生联谊会分成4组。她需要为4个不同的活动（每周1个活动）做这个。总共有168个女孩（方便的是它可以分成4组）。需要注意的是，没有一个女孩可以与一个女孩组成一团，而这些女孩之前已经和他们在一起。

当她告诉我这个问题我告诉她我可以给她编写一个可以做到这一点的小脚本，没问题。我认为这不具备挑战性......

最初我以为我会在python中编写一个小脚本，使用随机数生成器从女孩列表中随机选择女孩并将它们放入4个组中。每个组都有一个从1开始的递增ID，而不是重置为新事件（因此事件2的第一组ID为43）。每个女孩都会成为一个在她名字之上的对象，也会包含她已经在的群组的ID。对于将来的迭代/事件，我将再次从列表中随机选择女孩并将它们分成4组，但是会进行检查以确保其先前的组ID中没有重叠。如果一个女孩没有通过检查，重新播种数字生成器并继续生成一个随机数，直到它与通过检查的女孩的索引相匹配。

我仍然认为这会起作用（除非这个问题在数学上是不可能的），但它会很慢而且效率低下。我知道必须有比蛮力组合更优雅的解决方案。

我怎么能完成这个任务？

Answer 1

想象一下，四个戒指一个在另一个上面放在42个（可以用168个女孩创建的群组中，每组有4个女孩）连续站立的两极。那些与杆子一分为二的戒指的每一部分都是一个女孩。每次你想让一群没有在同一组的女孩。只需旋转每个环加一次。我不知道如果你可以想象我试图暗示与否，或者可能是我可能无法正确表达自己。你的问题很有趣所以我写了一个python函数试图在代码中表达它。我没有测试它是诚实的，但我希望这应该工作。这是代码。

def group_girls(girls, what_time=0):
    # Create four groups containing girls
    rings = {}
    for i in range(0, 4):
        rings[i] = []
    for girl_number in range(len(girls)):
        rings[girl_number % 4].append(girls[girl_number])
    # Create a group now
    groups = {}
    for group_number in range(42):
        groups[group_number] = []
        apparent_index = group_number
        for j in range(4):
            apparent_index += what_time
            groups[group_number].append(rings[j][apparent_index])
    return groups

'what_time'是您想要选择女孩的活动数量。我希望它有所帮助！

Answer 2

只有4个事件，您可以使用简单的算法。将所有女孩任意安排到一个有4列42行的矩阵中。每行都是第一个事件的组。然后，将列2向下移动一行，将列3向下移动2行，并将列4向下移动3行。您现在有第二个事件的新分组。重复两次以获得第3和第4个事件的分组。由于每列的移动量不同，并且没有任何列移动完整的42行，因此没有两个女孩会共享同一行两次。

（显然，这种策略不会产生最大数量的有效分组，但它肯定会给你4个。）

Answer 3

我测试了它，它的工作原理。粗暴的算法。每个活动42个小组。一个女孩在所有比赛中总是有不同的队友。

import itertools, random

def gen_groups(items, c):
    t = items[:]
    random.shuffle(t)
    size = len(t) / c
    for i in xrange(c):
        yield tuple(sorted(t[i*size:(i+1)*size]))

def has_collision(plan0, plan1):
    for g0 in plan0:
        for g1 in plan1:
            if len(set(g0) & set(g1)) > 1:
                return True

def main():
    items = range(168)
    events = set()
    for e in xrange(4):
        while True:
            groups = tuple([g for g in gen_groups(items, 42)])
            collision = False
            for pre_groups in events:
                if has_collision(pre_groups, groups):
                    collision = True
                    break
            if not collision:
                events.add(groups)
                print '-- event %s --' % (e + 1)
                print groups
                break
    print 'done'

if __name__ == '__main__':
    main()

Answer 4

你可以在桌子/团体的人中尝试一种“音乐椅”（即circular shifts）。

码

import collections as ct

import more_itertools as mit


def shift(iterable):
    """Return a list redistributed subsets."""
    # Prepare empty containers
    tables = [()] * len(iterable)

    assignments = ct.deque(tables)
    for k, sublst in enumerate(zip(*iterable)):
        # distrib list to each position
        for i, item in enumerate(sublst):
            assignments[i] += (item,)
        assignments.rotate(-(k+1))
    return list(assignments)

size = 2*2
lst = list(mit.windowed(range(1, 169), n=size, step=size))


# Arrangement for the first four weeks
week_0 = lst
week_1 = shift(lst)
week_2 = shift(shift(lst))
week_3 = shift(shift(shift(lst)))

演示

>>> week_3
[(121, 110, 87, 52),
 (125, 114, 91, 56),
 (129, 118, 95, 60),
 (133, 122, 99, 64),
 (137, 126, 103, 68),
 (141, 130, 107, 72),
 ...]

注意：我们使用第三方more_itertools.windowed快速构建四个组的子集。

---

细节

考虑一个人数较少的16人，坐在四人桌上。对于某些m轮换，您可以确保一个成员与群体中的任何其他成员没有冲突，具体如下：

对于每个轮换，每个成员都移动i表远离其最后一个表位置。

例如，在下图中取A旋转的第一个表。在下一次轮换中，B：

• 坐在索引0处的人从最后一个位置移开0桌。
• 坐在索引1处的人从最后一个位置移开一张桌子。
• 坐在索引2处的人移动距离最后一个位置2个桌子。
• ...

简而言之，此过程只是在所有可用表中重新分配人员。

请注意，在中途点之外，碰撞开始发生（如旋转C和D的红色和橙色位置所示）。事实上，如果充分旋转（E），可以实现原始布置。虽然该算法对人口规模敏感，但对于旋转较少的较大人群来说，碰撞越来越少。因此，您需要168个四周（轮换）才能正常工作，而不会有客人再次相遇的风险。现在，如果他们恰好是朋友，那就是一个完全独立的挑战。

请参阅后面插图的示例代码：

lst = list(mit.windowed(range(1, 17), n=size, step=size))

a = lst
b = shift(lst)
c = shift(shift(lst))
d = shift(shift(shift(lst)))
e = shift(shift(shift(shift(lst))))

Answer 5

假设你有一个.txt文件，其中包含每行一个名字的女孩名字：

girls = open('girls_names.txt').read().splitlines() #list of 168 girls

#pick 168 girls, rearrange list, pick again, repeat for 4 girls
first, second, third, fourth = girls[1:]+girls[:1], \
                               girls[3:]+girls[:3], \
                               girls[6:]+girls[:6], \
                               girls[10:]+girls[:10]

#zip first, second, third and fourth girl selections together into groups                               
groups = zip(first, second, third, fourth)

#split groups evenly into 4 weeks, etc...
week1, week2, week3, week4 = groups[:42],    \
                             groups[42:84],  \
                             groups[84:126], \
                             groups[126:169]
#week1
>[('Adrienne', 'Joslyn', 'Nyla', 'Jordin'), ('Donna', 'Kathy', 'Abbie', 'Makayla'), ('Joslyn', 'Dahlia', 'Amy', 'Johanna'), ('Kathy', 'Nyla', 'Ann', 'Brooklynn'),...]