Discussion :

[HelloThury]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[VinsS]

Salut,

avec itertools tu peux simplifier.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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)

[HelloThury]

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

[VinsS]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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)]
>>>

[josmiley]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[VinsS]

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

Opinion personnelle, bien sur.

[HelloThury]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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