Comment diviser une liste en n groupes dans toutes les combinaisons possibles de longueur de groupe et d'éléments au sein du groupe?

Nous pouvons utiliser l'algorithme récursif de base de cette réponse et le modifier pour produire des partitions d'une longueur particulière sans avoir à générer et filtrer les partitions indésirables.

def sorted_k_partitions(seq, k):
    """Returns a list of all unique k-partitions of `seq`.

    Each partition is a list of parts, and each part is a tuple.

    The parts in each individual partition will be sorted in shortlex
    order (i.e., by length first, then lexicographically).

    The overall list of partitions will then be sorted by the length
    of their first part, the length of their second part, ...,
    the length of their last part, and then lexicographically.
    """
    n = len(seq)
    groups = []  # a list of lists, currently empty

    def generate_partitions(i):
        if i >= n:
            yield list(map(tuple, groups))
        else:
            if n - i > k - len(groups):
                for group in groups:
                    group.append(seq[i])
                    yield from generate_partitions(i + 1)
                    group.pop()

            if len(groups) < k:
                groups.append([seq[i]])
                yield from generate_partitions(i + 1)
                groups.pop()

    result = generate_partitions(0)

    # Sort the parts in each partition in shortlex order
    result = [sorted(ps, key = lambda p: (len(p), p)) for ps in result]
    # Sort partitions by the length of each part, then lexicographically.
    result = sorted(result, key = lambda ps: (*map(len, ps), ps))

    return result

Il se passe beaucoup de choses ici, alors laissez-moi vous expliquer.

Tout d'abord, nous commençons par une implémentation procédurale ascendante (teminologie?) Du même algorithme récursif mentionné ci-dessus :

def partitions(seq):
    """-> a list of all unique partitions of `seq` in no particular order.

    Each partition is a list of parts, and each part is a tuple.
    """
    n = len(seq)
    groups = []  # a list of lists, currently empty

    def generate_partitions(i):
        if i >= n:
            yield list(map(tuple, groups))
        else:
            for group in groups
                group.append(seq[i])
                yield from generate_partitions(i + 1)
                group.pop()

            groups.append([seq[i]])
            yield from generate_partitions(i + 1)
            groups.pop()

    if n > 0:
        return list(generate_partitions(0))
    else:
        return [[()]]

L'algorithme principal est dans la generate_partitionsfonction imbriquée . Fondamentalement, il parcourt la séquence, et pour chaque élément, il: 1) place l'élément dans chacun des groupes actuels (aka parties) dans l'ensemble de travail et se répète; 2) place l'élément dans son propre nouveau groupe.

Lorsque nous atteignons la fin de la séquence ( i == n), nous produisons une copie (complète) de l'ensemble de travail que nous avons construit.

Maintenant, pour obtenir des partitions d'une longueur particulière, nous pourrions simplement filtrer ou regrouper les résultats pour ceux que nous recherchons et en finir avec, mais cette approche effectue beaucoup de travail inutile (c'est-à-dire des appels récursifs) si nous voulions juste partitions d'une certaine longueur k.

Notez que dans la fonction ci-dessus, la longueur d'une partition (c'est-à-dire le nombre de groupes) est augmentée chaque fois que:

            # this adds a new group (or part) to the partition
            groups.append([seq[i]])
            yield from generate_partitions(i + 1)
            groups.pop()

...est exécuté. Ainsi, nous limitons la taille d'une partition en mettant simplement une garde sur ce bloc, comme ceci:

def partitions(seq, k):
    ...

    def generate_partitions(i):
        ...

            # only add a new group if the total number would not exceed k
            if len(groups) < k:
                groups.append([seq[i]])
                yield from generate_partitions(i + 1)
                groups.pop()

L'ajout du nouveau paramètre et uniquement de cette ligne à la partitionsfonction l'amènera désormais à ne générer que des partitions d'une longueur maximale de k . C'est presque ce que nous voulons. Le problème est que la forboucle génère encore parfois des partitions de longueur inférieure à k .

Afin d'élaguer ces branches récursives, nous n'avons besoin d'exécuter la forboucle que lorsque nous pouvons être sûrs que nous avons suffisamment d'éléments restants dans notre séquence pour étendre l'ensemble de travail à un total de kgroupes. Le nombre d'éléments restants - ou d'éléments qui n'ont pas encore été placés dans un groupe - est n - i(ou len(seq) - i). Et k - len(groups)est le nombre de nouveaux groupes que nous devons ajouter pour produire une k-partition valide. Si n - i <= k - len(groups), alors nous ne pouvons pas gaspiller un élément en l'ajoutant à l'un des groupes actuels, nous devons créer un nouveau groupe.

Nous ajoutons donc simplement une autre garde, cette fois à l'autre branche récursive:

    def generate_partitions(i):
        ...

            # only add to current groups if the number of remaining items
            # exceeds the number of required new groups.
            if n - i > k - len(groups):
                for group in groups:
                    group.append(seq[i])
                    yield from generate_partitions(i + 1)
                    group.pop()

            # only add a new group if the total number would not exceed k
            if len(groups) < k:
                groups.append([seq[i]])
                yield from generate_partitions(i + 1)
                groups.pop()

Et avec cela, vous avez un générateur de partition k fonctionnel. Vous pourriez probablement réduire encore plus certains des appels récursifs (par exemple, s'il y a 3 éléments restants et que nous avons besoin de 3 groupes supplémentaires, vous savez déjà que vous devez diviser chaque élément dans leur propre groupe), mais je voulais montrer le fonctionne comme une légère modification de l'algorithme de base qui génère toutes les partitions.

La seule chose qui reste à faire est de trier les résultats. Malheureusement, plutôt que de trouver comment générer directement les partitions dans l'ordre souhaité (un exercice pour un chien plus intelligent), j'ai triché et juste trié après la génération.

def sorted_k_partitions(seq, k):
    ...
    result = generate_partitions(0)

    # Sort the parts in each partition in shortlex order
    result = [sorted(ps, key = lambda p: (len(p), p)) for ps in result]
    # Sort partitions by the length of each part, then lexicographically.
    result = sorted(result, key = lambda ps: (*map(len, ps), ps))

    return result

Un peu explicite, sauf pour les fonctions clés. Le premier:

key = lambda p: (len(p), p) 

dit de trier une séquence par longueur, puis par séquence elle-même (qui, en Python, sont ordonnées lexicographiquement par défaut). Les pstands pour «partie». Ceci est utilisé pour trier les parties / groupes dans une partition. Cette clé signifie que, par exemple, (4,)précède (1, 2, 3), donc c'est [(1, 2, 3), (4,)]trié comme [(4,), (1, 2, 3)].

key = lambda ps: (*map(len, ps), ps) 
# or for Python versions <3.5: lambda ps: tuple(map(len, ps)) + (ps,)

Le psici signifie «parties», pluriel. Celui-ci dit de trier une séquence par les longueurs de chacun de ses éléments (qui doivent être séquence eux-mêmes), puis (lexicographiquement) par la séquence elle-même. Ceci est utilisé pour trier les partitions les unes par rapport aux autres, de sorte que, par exemple, [(4,), (1, 2, 3)]précède [(1, 2), (3, 4)].

Le suivant:

seq = [1, 2, 3, 4]

for k in 1, 2, 3, 4:
    for groups in sorted_k_partitions(seq, k):
        print(k, groups)

produit:

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