Comment générer toutes les partitions d'ensemble possibles d'un tableau en Python ?

Définir des partitions en Python

La division d'un tableau en sous-ensembles distincts, où chaque élément appartient à exactement un sous-ensemble, est connue sous le nom de partitionnement d'ensemble. Étant donné un tableau d'éléments, comment pouvons-nous générer toutes les partitions d'ensemble possibles à l'aide de Python ?

Considérons un tableau [1, 2, 3]. Nous visons à obtenir les partitions suivantes :

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

Solution récursive

Notre solution exploite la récursivité pour réaliser ce partitionnement. Pour une partition de n-1 éléments, nous envisageons deux options pour accueillir le nième élément :

1. Ajouter le nième élément à un sous-ensemble existant.
2. Créer un nouveau sous-ensemble contenant uniquement le nième élément.

En appliquant ces options de manière itérative, nous pouvons construire toutes les partitions possibles.

Mise en œuvre

<code class="python">def partition(collection):
    if len(collection) == 1:
        yield [collection]
        return

    first = collection[0]
    for smaller in partition(collection[1:]):
        # Insert first into existing subsets
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[first] + subset] + smaller[n+1:]
        # Create a new subset
        yield [[first]] + smaller


something = list(range(1, 5))

for n, p in enumerate(partition(something), 1):
    print(n, sorted(p))</code>

Sortie

1 [[1, 2, 3, 4]]
2 [[1], [2, 3, 4]]
3 [[1, 2], [3, 4]]
4 [[1, 3, 4], [2]]
5 [[1], [2], [3, 4]]
6 [[1, 2, 3], [4]]
7 [[1, 4], [2, 3]]
8 [[1], [2, 3], [4]]
9 [[1, 3], [2, 4]]
10 [[1, 2, 4], [3]]
11 [[1], [2, 4], [3]]
12 [[1, 2], [3], [4]]
13 [[1, 3], [2], [4]]
14 [[1, 4], [2], [3]]
15 [[1], [2], [3], [4]]

Cette solution génère efficacement toutes les partitions d'ensemble possibles du tableau donné.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!