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:
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.
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)
Quelqu'un aurait des idées ?
Merci à tous,
HT
Partager