CODEWITHSUNDEEP
pythonalgorithmcombinationspermutation
user9853395
user9853395

Reputation: 39

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

Problem:

Example:

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} }

Purpose: I need to list all possible ways a variable number of players can be divided into two equal (or almost equal) teams.

What I tried so far: I was able to code this in python using the itertools.combinations function. However, the way I did it seems inefficient. I got all combination for one subset and got the second subset by subtracting the original set from the first subset. But, because I need to take consideration of the fact that which team the player gets into does not matter, I have to basically divide that combination in half.

This is what I had.

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

Upvotes: 0

Views: 455

Answers (2)

MBo
MBo

Reputation: 80197

You are almost here.

Remove the first element from the players and remember it as leader

Form commands from players as you do now.

Add leader to the first command just before output

Simple example (without sets)

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

Upvotes: 1

Victor Martin
Victor Martin

Reputation: 89

You should try with a backtracking. It's quick and uses very few lines!

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

Upvotes: 1

Related Questions