generating list of every combination without duplicates

Question

I would like to generate a list of combinations. I will try to simplify my problem to make it understandable.

We have 3 variables :

• x : number of letters
• k : number of groups
• n : number of letters per group

I would like to generate using python a list of every possible combinations, without any duplicate knowing that : i don't care about the order of the groups and the order of the letters within a group.

As an example, with x = 4, k = 2, n = 2 :

# we start with 4 letters, we want to make 2 groups of 2 letters
letters = ['A','B','C','D']

# here would be a code that generate the list

# Here is the result that is very simple, only 3 combinations exist.
combos = [ ['AB', 'CD'], ['AC', 'BD'], ['AD', 'BC'] ]

Since I don't care about the order of or within the groups, and letters within a group, ['AB', 'CD'] and ['DC', 'BA'] is a duplicate.

This is a simplification of my real problem, which has those values : x = 12, k = 4, n = 3. I tried to use some functions from itertools, but with that many letters my computer freezes because it's too many combinations.

Another way of seeing the problem : you have 12 players, you want to make 4 teams of 3 players. What are all the possibilities ?

Could anyone help me to find an optimized solution to generate this list?

Answer 1

There will certainly be more sophisticated/efficient ways of doing this, but here's an approach that works in a reasonable amount of time for your example and should be easy enough to adapt for other cases.

It generates unique teams and unique combinations thereof, as per your specifications.

from itertools import combinations

# this assumes that team_size * team_num == len(players) is a given
team_size = 3
team_num = 4
players = list('ABCDEFGHIJKL')
unique_teams = [set(c) for c in combinations(players, team_size)]

def duplicate_player(combo):
    """Returns True if a player occurs in more than one team"""
    return len(set.union(*combo)) < len(players)
    
result = (combo for combo in combinations(unique_teams, team_num) if not duplicate_player(combo))

result is a generator that can be iterated or turned into a list with list(result). On kaggle.com, it takes a minute or so to generate the whole list of all possible combinations (a total of 15400, in line with the computations by @beaker and @John Coleman in the comments). The teams are tuples of sets that look like this:

[({'A', 'B', 'C'}, {'D', 'E', 'F'}, {'G', 'H', 'I'}, {'J', 'K', 'L'}),
 ({'A', 'B', 'C'}, {'D', 'E', 'F'}, {'G', 'H', 'J'}, {'I', 'K', 'L'}),
 ({'A', 'B', 'C'}, {'D', 'E', 'F'}, {'G', 'H', 'K'}, {'I', 'J', 'L'}),
 ...
]

If you want, you can cast them into strings by calling ''.join() on each of them.

Answer 2

Another solution (players are numbered 0, 1, ...):

import itertools

def equipartitions(base_count: int, group_size: int):
    if base_count % group_size != 0:
        raise ValueError("group_count must divide base_count")

    return set(_equipartitions(frozenset(range(base_count)), group_size))


def _equipartitions(base_set: frozenset, group_size: int):
    if not base_set:
        yield frozenset()

    for combo in itertools.combinations(base_set, group_size):
        for rest in _equipartitions(base_set.difference(frozenset(combo)), group_size):
            yield frozenset({frozenset(combo), *rest})


all_combinations = [
    [tuple(team) for team in combo]
        for combo in equipartitions(12, 3)
]

print(all_combinations)
print(len(all_combinations))

And another:

import itertools
from typing import Iterable

def equipartitions(players: Iterable, team_size: int):
    if len(players) % team_size != 0:
        raise ValueError("group_count must divide base_count")

    return _equipartitions(set(players), team_size)


def _equipartitions(players: set, team_size: int):
    if not players:
        yield []
        return

    first_player, *other_players = players
    for other_team_members in itertools.combinations(other_players, team_size-1):
        first_team = {first_player, *other_team_members}
        for other_teams in _equipartitions(set(other_players) - set(first_team), team_size):
            yield [first_team, *other_teams]


all_combinations = [
    {''.join(sorted(team)) for team in combo} for combo in equipartitions(players='ABCDEFGHIJKL', team_size=3)
]


print(all_combinations)
print(len(all_combinations))

Answer 3

Firstly, you can use a list comprehension to give you all of the possible combinations (regardless of the duplicates):

comb = [(a,b) for a in letters for b in letters if a != b]

And, afterwards, you can use the sorted function to sort the tuples. After that, to remove the duplicates, you can convert all of the items to a set and then back to a list.

var = [tuple(sorted(sub)) for sub in comb]
var = list(set(var))

Answer 4

You could use the list comprehension approach, which has a time complexity of O(n*n-1), or you could use a more verbose way, but with a slightly better time complexity of O(n^2-n)/2:

comb = []

for first_letter_idx, _ in enumerate(letters):
    for sec_letter_idx in range(first_letter_idx + 1, len(letters)):
        comb.append(letters[first_letter_idx] + letters[sec_letter_idx])

print(comb)

comb2 = []

for first_letter_idx, _ in enumerate(comb):
    for sec_letter_idx in range(first_letter_idx + 1, len(comb)):
        if (comb[first_letter_idx][0] not in comb[sec_letter_idx]
        and comb[first_letter_idx][1] not in comb[sec_letter_idx]):
            comb2.append([comb[first_letter_idx], comb[sec_letter_idx]])

print(comb2)

This algorithm needs more work to handle dynamic inputs. Maybe with recursion.

Answer 5

Use combination from itertools

from itertools import combinations 

x = list(combinations(['A','B','C','D'],2))

t = []
for i in (x):
    t.append(i[0]+i[1]) # concatenating the strings and adding in a list

g = []
for i in range(0,len(t),2):
    for j in range(i+1,len(t)):
        g.append([t[i],t[j]])
        break
print(g)