获取将一组对象划分为两个等长（或相差一个）子集的方法列表

Question

问题：

集合中有 n 个唯一对象 S
得到每一种方式的列表L S可以分为2个子集这样那：
- 如果n是偶数，则两个子集长度相同
- 如果n为奇数，则两个子集的长度仅相差1
- L是包含两个子集的list of set(list of set of set of two sets)
- L 不包含重复项

示例：

IF
S = {a, b, c, d, e, f, g, h, i, j}
L = func(S)

THEN
L == [
   { {a, b, c, d, e}, {f, g, h, i, j} },
   { {a, b, c, d, f}, {e, g, h, i, j} },
   { {a, b, c, d, g}, {f, e, h, i, j} },
   ... ]

SUCH THAT
{ {a, b, c, d, e}, {f, g, h, i, j} } 
== { {f, g, h, i, j}, {a, b, c, d, e} } 
== { {e, d, a, b, c}, {g, i, j, f, h} }

目的：我需要列出将可变数量的玩家分成两个相等（或几乎相等）的团队的所有可能方法。

到目前为止我尝试了什么：我能够使用 itertools.combinations 函数在 python 中编写代码。但是，我这样做的方式似乎效率低下。我得到了一个子集的所有组合，并通过从第一个子集中减去原始集得到了第二个子集。但是，因为我需要考虑到玩家进入哪个队伍并不重要，所以我基本上必须将那个组合分成两半。

这是我的。

import itertools as it
import math

def divide(players: set[int]):
    comb = it.combinations(players, math.floor(len(players) / 2))

    rtn = []
    for team in comb:
        a = frozenset(team)
        b = frozenset(players - a)
        element = {a, b}

        if element not in rtn:
            rtn.append(element)

    return rtn

Answer 1

你应该尝试回溯。速度很快，使用的代码很少！

n = int(input())

# List of solutions
# For each l in L, l[i] = True if player i is in team A, False if he is in team B
L = []

# Current solution
cur = [False]*n

# In each step, we decide the team of player i,
# Given that team A has already n_team_a players
def backtracking(i, n_team_a):
    n_team_b = i - n_team_a # Number of players on team B
    left = n - i            # Number of players left to choose

    # If we can't have a balanced team even if we put all the players
    # left in the same team, abort
    if n_team_a + left + 1 < n_team_b or n_team_b + left + 1 < n_team_a:
        return

    # If we found a solution, add it to L
    if i == n:
        L.append(cur.copy())
        return

    # Try putting player i on team A
    cur[i] = True
    backtracking(i + 1, n_team_a + 1)

    # Try putting player i on team B
    cur[i] = False
    backtracking(i + 1, n_team_a)
    
# Start
backtracking(0, 0)

# Print solutions
print(*L, sep='\n')

Answer 2

你快到了。

从球员中删除第一个元素并记住它作为leader

像现在一样从玩家那里形成命令。

将leader添加到输出前的第一个命令

简单示例（无集合）

import itertools as it
import math

def divide(players):
    first = players.pop(0)
    comb = it.combinations(players, len(players) // 2)

    rtn = []
    for team in comb:
        a = list(team)
        a.insert(0, first)
        b = [x for x in players if x not in team]
        element = (a, b)

        if element not in rtn:
            rtn.append(element)

    return rtn


print(divide([1,2,3,4,5]))

[([1, 2, 3], [4, 5]), ([1, 2, 4], [3, 5]), 
 ([1, 2, 5], [3, 4]), ([1, 3, 4], [2, 5]), 
 ([1, 3, 5], [2, 4]), ([1, 4, 5], [2, 3])]

获取将一组对象划分为两个等长（或相差一个）子集的方法列表

Obtaining list of ways to divide a set of object into two equal length (or off by one) subset

python

algorithm

combinations

permutation