Discussion :

[xlurp]

bonjour,
je voudrais découper un tableau de longueur x en toutes les combinaisons de nombres de longueur n, n variant de 1 a x
ex :
tableau : [0, 1, 2, 3, 4, 5, 6]
on obtient:
0
1
...
6
0 1
0 2
0 3
....
1 2
1 3
....
3 4 5
3 4 6
3 5 6
.....

et ainsi de suite, la longueur du tableau n'etant pas connu a l'avance

ps j'ai oublié de preciser : l'ordre n'ayant pas d'importance, 0 1 2 3 et 1 2 3 0 sont pour moi identique

[Invité(e)]

Bonjour
Dans quel but veux tu réaliser ce programme, c'est un exercice ?

ALors un idée à creuser :
les combinaisons de taille 1 sont faciles à réaliser : 0, 1, 2, 3...

Les combinaisons de taille 2 sont en fait l'ensemble des combinaisons des combinaisons de taille 1

c'est à dire :

Code :

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

combinaisons_2 = combisaisons_1 ¤ combinaisons_1

jusque là, rien de difficile, si ce n'est qu'il faudra créer le tout dynamiquement.

pour les combinaisons de taille 3, on remarquera que c'est en fait l'ensemble des combinaisons de taille 2 combinées à celles de taille 1 :

Code :

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

combinaisons_3 = combisaisons_2 ¤ combinaisons_1

et ainsi de suite jusqu'à n = taille du tableau :

Code :

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

1
2
 
combinaisons_n = combisaisons_(n-1) ¤ combinaisons_1

Voilà pour l'algorithme.
L'inconvénient de cette méthode est qu'elle implique un stockage en mémoire des tableaux créés.

à creuser : il y a certainement d'autres méthodes plus élégantes.

mabu

[xlurp]

merci de ton aide mais ta méthode a l'inconvenient de devoir stocker un nombre important de tableau, donc comme ça va etre appelé un nombre important de fois sur des tableaus differents, ça va alourdir le prog

ensuite si j'ai bien compris ta methode :
elle va creer des doublons,si on prend un tableau de longueur 5 on a les combinaisons :
0 1 2 3 4 pour 1
01
02
03
04
12
13
14
....
pour deux
si on prend toute les combiaisons de 1 et 2
0 01
0 02
<== ça ne va pas car chaque nombre doit etre unique

0 12
1 02
<== pour moi ces combianisons sont identiques, l'ordre n'ayant pas d'importance


merci quand meme


ps : oui c'est pour une sous (sous)partie d'un exercice

[xlurp]

je crois que j'ai trouvela reponse :

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
 
        String delTmp="";
		//nbComp est le nombre total de combinaisons avec byteLine.Length Peg soit 2^(byteLine.length+1) -1
		int nbComb= (1<<(byteLine.lentgh))-1;
		/*
		*on se sait de i comme d'un tableau de boolean pour les byteLine.length premiers bits, le reste etant inutilisé
		*on se sert de i comme d'un masque sur le tableau byteLine pour savoir
		*quels sont les Pegs a prendre pour toutes les combinaisons de 1 a byteLineLength
		*si  "true" est a la position j, alors on prend le Peg a la position j du tableau
		*
		*/
		for(int i=1;i<=nbComb;++i){
			for(int j=0;j<byteLine.length;++j){
				if((i>>j &1)==1){
					delTmp+=(char)byteLine[j];
				}
			}
      }

c'est du java (pour ceux qui ont un doute)

si quelqu'un trouve plus elegant (ou plus rapide) faite moi signe, je serai content
[edit] j'ai changé

Code :

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

 int nbComb= (1<<(byteLine.lentgh+1))-1;

en

Code :

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

 int nbComb= (1<<(byteLine.lentgh))-1;

sinon ça ne marchait , ça crée des combinaisons trop longues avec des doubles dedans
[/edit]