Enumérer tous les sous-ensembles à k éléments parmi n

Bonjour,
je voudrais donc énumérer tous les sous-ensembles à k éléments parmi n sous formes de listes. Par exemple, pour n=5 et k=2, on obtient :
[0, 0, 0, 1, 1]
[0, 0, 1, 0, 1]
[0, 1, 0, 0, 1]
[1, 0, 0, 0, 1]
[0, 0, 1, 1, 0]
[0, 1, 0, 1, 0]
[1, 0, 0, 1, 0]
[0, 1, 1, 0, 0]
[1, 0, 1, 0, 0]
[1, 1, 0, 0, 0]
J'ai procédé comme ça:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 def construction_sous_ensemble(n,k): liste=list(range(n)) for i in range(0,n-k): liste[i]=0 for i in range(n-k,n): liste[i]=1 print(liste) x=0#la position du 1 apres les 0 #on deplace vers la gauche le premier 1 situé après le premier 0 while x <n: x=0 while liste[x]==1: x+=1 nb_un=x # la position du dernier 1 rencontré while x<n and liste[x]==0: x+=1 # x = position du premier 1 du deuxième "paquet" de 1 if x<n: liste[x]=0 for k in range(1,nb_un+2): liste[x-k]=1 for k in range(nb_un+2,x+1): liste[x-k]=0 print(liste)
Ca marche (à ceci près que le dernier ensemble est cité 2 fois mais c'est pas très grave...) mais j'aurais besoin que ça soit un peu optimisé pour pouvoir l'utiliser avec des valeurs raisonnablement grandes de n et k.
Quelqu'un aurait des idées ?

Merci à tous,

HT

Salut,

avec itertools tu peux simplifier.

Code:

1
2
3
4
5
6
7
8
9
 
>>> n = 6
>>> k = 3
>>> l = [0 for i in range(n-k)]
>>> l.extend([1 for i in range(k)])
>>> l
[0, 0, 0, 1, 1, 1]
>>> for p in itertools.permutations(l):
...     print(p)

Merci beaucoup pour ta réponse, je pense qu'il doit y avoir un truc à creuser de ce côté là mais là il semblerait que ça ne marche pas. Chaque liste est renvoyée plusieurs fois...
En fait ça renvoie les n! permutations en distinguant tous les 1 et tous les 0. Donc il y en a k!(n-k)! trop !

Merci quand même,

HT

Je comprend ce que tu veux dire, mets-les dans un set dans ce cas là.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
 
>>> from itertools import permutation as perm
>>> l = [0, 0, 0, 1, 1]
>>> s = set()
>>> for p in perm(l):
...     s.add(p)
... 
>>> s
{(0, 0, 1, 1, 0), (1, 1, 0, 0, 0), (0, 0, 1, 0, 1), (0, 0, 0, 1, 1), (1, 0, 1, 0, 0), (0, 1, 1, 0, 0), (0, 1, 0, 1, 0), (1, 0, 0, 1, 0), (0, 1, 0, 0, 1), (1, 0, 0, 0, 1)}
>>> sorted(s)
[(0, 0, 0, 1, 1), (0, 0, 1, 0, 1), (0, 0, 1, 1, 0), (0, 1, 0, 0, 1), (0, 1, 0, 1, 0), (0, 1, 1, 0, 0), (1, 0, 0, 0, 1), (1, 0, 0, 1, 0), (1, 0, 1, 0, 0), (1, 1, 0, 0, 0)]
>>>

Citation:

Envoyé par VinsS

Code:

1
2
3
4
5
6
7
 
>>> n = 6
>>> k = 3
>>> l = [0 for i in range(n-k)]
>>> l.extend([1 for i in range(k)])
>>> l
[0, 0, 0, 1, 1, 1]

moué ... ?

Code:

1
2
3
>>> foo = lambda n,k: [0]*(n-k)+[1]*k
>>> foo(6,3)
[0, 0, 0, 1, 1, 1]

J'aime pas les lambda, ça a un aspect "bricolage".

Opinion personnelle, bien sur.

Merci à tous pour vos réponses,
pour éviter de parcourir plusieurs fois, on peut utiliser combinations(n,r) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
>>> from itertools import *
>>> l=list(0 for k in range(6))
>>> m=list(k for k in range(6))
>>> for p in combinations(m,2):
	for i in range(6):
		if i in p:
			l[i]=1
		else:
			l[i]=0
	print(l)
 
 
[1, 1, 0, 0, 0, 0]
[1, 0, 1, 0, 0, 0]
[1, 0, 0, 1, 0, 0]
[1, 0, 0, 0, 1, 0]
[1, 0, 0, 0, 0, 1]
[0, 1, 1, 0, 0, 0]
[0, 1, 0, 1, 0, 0]
[0, 1, 0, 0, 1, 0]
[0, 1, 0, 0, 0, 1]
[0, 0, 1, 1, 0, 0]
[0, 0, 1, 0, 1, 0]
[0, 0, 1, 0, 0, 1]
[0, 0, 0, 1, 1, 0]
[0, 0, 0, 1, 0, 1]
[0, 0, 0, 0, 1, 1]

Merci encore à tous et bonne journée,

HT