3
votes

(Python) Recherche de toutes les partitions possibles d'une liste de listes soumises à une limite de taille pour une partition

Supposons que j'ai une liste k = [[1,1,1], [2,2], [3], [4]] , avec une limite de taille c = 4 .

Ensuite, j'aimerais trouver toutes les partitions possibles du sujet k ot c . Idéalement, le résultat devrait être:

[{[[1,1,1], [3]], [[2,2], [4]]}, {[[1 , 1,1], [4]], [[2,2], [3]]}, {[[1,1,1]], [[2,2], [3], [4]] }, ..., {[[1,1,1]], [[2,2]], [[3]], [[4]]}]

où J'ai utilisé la notation définie {} dans l'exemple ci-dessus (le cas réel est [] ) pour préciser ce qu'est une partition, où chaque partition contient des groupes de listes groupées ensemble.

J'ai implémenté l'algorithme suivant mais mes résultats ne correspondent pas:

def num_item(l):
    flat_l = [item for sublist in l for item in sublist]
    return len(flat_l)

def get_all_possible_partitions(lst, c):
    p_opt = []
    for l in lst:
        p_temp = [l]
        lst_copy = lst.copy()
        lst_copy.remove(l)
        iterations = 0
        while num_item(p_temp) <= c and iterations <= len(lst_copy):
            for l_ in lst_copy:
                iterations += 1
                if num_item(p_temp + [l_]) <= c:
                    p_temp += [l_]
        p_opt += [p_temp]
    return p_opt

Exécution de get_all_possible_partitions (k, 4) , J'obtiens:

[[[1, 1, 1], [3]], [[2, 2], [3], [4]], [[3], [1, 1, 1]], [[4], [1, 1, 1]]]

Je comprends que cela ne supprime pas les doublons et n'épuise pas les combinaisons possibles, ce que je Je suis coincé.

Certaines informations seront formidables! P.S. Je n'ai pas réussi à trouver des questions similaires: /

python-3.x algorithm list combinations partitioning

0 commentaires

3 Réponses :

2
votes

Si tous les éléments de la liste sont uniques, vous pouvez utiliser bit.

Supposons que k = [a, b, c], dont la longueur est 3, alors il y a 2 ^ 3 - 1 = 7 partions:

si vous utilisez bit pour représenter a, b, c, il y aura

001 -> [c]
010 -> [b]
011 -> [b, c]
100 -> [a]
101 -> [a,c]
110 -> [a,b]
111 -> [a,b,c]

donc, la clé pour résoudre cette question est maintenant évidente. p>

0 commentaires

2
votes

Je pense que cela fait ce que vous voulez (explications dans les commentaires):

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

Sortie:

# Main function
def get_all_possible_partitions(lst, c):
    yield from _get_all_possible_partitions_rec(lst, c, [False] * len(lst), [])

# Produces partitions recursively
def _get_all_possible_partitions_rec(lst, c, picked, partition):
    # If all elements have been picked it is a complete partition
    if all(picked):
        yield tuple(partition)
    else:
        # Get all possible subsets of unpicked elements
        for subset in _get_all_possible_subsets_rec(lst, c, picked, [], 0):
            # Add the subset to the partition
            partition.append(subset)
            # Generate all partitions that complete the current one
            yield from _get_all_possible_partitions_rec(lst, c, picked, partition)
            # Remove the subset from the partition
            partition.pop()

# Produces all possible subsets of unpicked elements
def _get_all_possible_subsets_rec(lst, c, picked, current, idx):
    # If we have gone over all elements finish
    if idx >= len(lst): return
    # If the current element is available and fits in the subset
    if not picked[idx] and len(lst[idx]) <= c:
        # Mark it as picked
        picked[idx] = True
        # Add it to the subset
        current.append(lst[idx])
        # Generate the subset
        yield tuple(current)
        # Generate all possible subsets extending this one
        yield from _get_all_possible_subsets_rec(lst, c - len(lst[idx]), picked, current, idx + 1)
        # Remove current element
        current.pop()
        # Unmark as picked
        picked[idx] = False
    # Only allow skip if it is not the first available element
    if len(current) > 0 or picked[idx]:
        # Get all subsets resulting from skipping current element
        yield from _get_all_possible_subsets_rec(lst, c, picked, current, idx + 1)

# Test
k = [[1, 1, 1], [2, 2], [3], [4]]
c = 4
partitions = list(get_all_possible_partitions(k, c))
print(*partitions, sep='\n')

1 commentaires

Oui c'est ce dont j'ai besoin! Merci beaucoup pour l'aide :)

0
votes

Remarque : Cette réponse est en fait pour un question liée fermée .

Si vous souhaitez uniquement renvoyer les bipartitions de la liste, vous pouvez utiliser more_iterools. set_partions :

>>> from more_itertools import set_partitions
>>>
>>> def get_bipartions(lst):
...     half_list_len = len(lst) // 2
...     if len(lst) % 2 == 0:
...         return list(
...             map(tuple, [
...                 p
...                 for p in set_partitions(lst, k=2)
...                 if half_list_len == len(p[0])
...             ]))
...     else:
...         return list(
...             map(tuple, [
...                 p
...                 for p in set_partitions(lst, k=2)
...                 if abs(half_list_len - len(p[0])) < 1
...             ]))
...
>>> get_bipartions(['A', 'B', 'C'])
[(['A'], ['B', 'C']), (['B'], ['A', 'C'])]
>>> get_bipartions(['A', 'B', 'C', 'D'])
[(['A', 'B'], ['C', 'D']), (['B', 'C'], ['A', 'D']), (['A', 'C'], ['B', 'D'])]
>>> get_bipartions(['A', 'B', 'C', 'D', 'E'])
[(['A', 'B'], ['C', 'D', 'E']), (['B', 'C'], ['A', 'D', 'E']), (['A', 'C'], ['B', 'D', 'E']), (['C', 'D'], ['A', 'B', 'E']), (['B', 'D'], ['A', 'C', 'E']), (['A', 'D'], ['B', 'C', 'E'])]

0 commentaires