Comment partitionner un ensemble en tous ses sous-ensembles possibles en Python ?

Partitionnement d'ensembles en Python

La tâche à accomplir est de partitionner un ensemble donné d'éléments en tous les sous-ensembles possibles. Par exemple, le partitionnement de l'ensemble [1, 2, 3] donne les sous-ensembles suivants :

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

Solution récursive

Une approche de ce problème est la récursion. Étant donné une partition de n-1 éléments, nous pouvons l'étendre pour créer une partition de n éléments en incluant le nième élément dans l'un des sous-ensembles existants ou en créant un nouveau sous-ensemble singleton contenant uniquement le nième élément.

Cet algorithme récursif partitionne efficacement l'ensemble d'entrées tout en évitant les sorties en double et les dépendances inutiles sur des bibliothèques externes :

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

    first = collection[0]
    for smaller in partition(collection[1:]):
        # insert `first` in each of the subpartition's subsets
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[ first ] + subset]  + smaller[n+1:]
        # put `first` in its own subset 
        yield [ [ first ] ] + smaller

something = list(range(1,5))

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

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!