Liste des parties d'un ensemble

JCJ · July 2017

Salut! J'ai besoin d'un algorithme pour obtenir la liste des parties à k élément de {1,....n}.
On peut le faire récursivement mais auriez-vous une idée pour éliminer facilement les doublons?
Je suis sur Python et pas très calé, si vous pouviez m'expliquer votre idée d'algorithme point par point ce serait cool, merci d'avance ^^'

samok · July 2017

Bonsoir,

générer des nombres en binaire sous forme de liste, qui code "l'élément est dans l'ensemble oui/non" , c'est comme ça que je ferais.

S

gerard0 · July 2017

Bonjour.

Si tu le fais récursivement, il n'y a aucune raison d'avoir des doublons.
Explique ton algorithme récursif ...

Cordialement.

NB : Bien sûr, tu as lu "à lire avant de poster", en particulier la fin du 1.

Mieses · July 2017

Bonjour, en reprenant l'idée de samok.
Soit $P$ une partie à $k$ éléments, $x_{i}$ est un booléen ($x_{i} = 0$ ou $1$) correspondant à l'appartenance de $i$ ($1 \leq i \leq n$) à $P$.
On est amené à chercher les $n$-uplets solutions de $x_{1} + x_{2} + \cdots + x_{n} = k.$

Mieses · July 2017

Ma proposition d'algorithme (itératif) :

Pour $N$ variant de $0$ à $2^{n} - 1$ faire
convertir $N$ en binaire
compter le nombre $u$ de $1$ dans $N$ (éventuellement en convertissant $N$ en une chaîne de caractères)
si $u=k$, $N$ est solution
Fin Pour

GaBuZoMeu · July 2017

J'espère que c'est du python standard :

Bon, je garde ma réponse sous le coude en attendant que le questionneur nous en dise plus sur ce qu'il a essayé.
Allez, je mets tout de même l'idée :
Les sous-ensembles à $k$ éléments de $\{1,\ldots,n\}$ sont :
- les sous-ensembles à $k$ éléments de $\{1,\ldots,n-1\}$
plus
- les sous-ensembles à $k-1$ éléments de $\{1,\ldots,n-1\}$ auxquels on ajoute $n$
(sans doublon).
Il reste à bien gérer les bords.

samok · July 2017

Bonsoir GaBuZoMeu,

dans les effets de bord, je ne sais pas si vous avez été brillant mais c'était scintillant cette différence entre [[]] et [].
La surcharge de + n'a pas été supporté par mon serpent, de base.

Il pleut sur ma ville.

S

bisam · July 2017

Une autre façon de décrire est de tenir une liste des positions des éléments sélectionnés et de définir une fonction qui calcule la liste "suivante" (par exemple dans l'ordre lexicographique).

Bref, dans tous les cas, en Python, c'est une dizaine de lignes à tout casser (si on n'utilise pas la bibliothèque "itertools" qui contient une fonction qui fait cela !)

GaBuZoMeu · July 2017

La procédure récursive que j'ai suggérée : sous_ensrec(n,k) pour fabriquer la liste des sous-ensembles à $k$ éléments de $\{1,\ldots,n\}$.
La procédure suggérée par samok explicitée par Mieses : sous_enssam(n,k) pour fabriquer la liste des entiers $\leq 2^n-1$ qui codent des sous-ensembles à $k$ éléments de $\{1,\ldots,n\}$.
Tout d'abord, on vérifie que ça fait bien ce qu'il faut. Ensuite, on compare les temps d'éxécution. Peut-être me suis-je mal débrouillé. Mais tout de même, $2^n$, c'est exponentiel en $n$. 65242

Liste des parties d'un ensemble

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 23