Discussion :

[[ZiP]]

Bonjour,

Je voudrais afficher toutes les combinaisons possibles à partir d'une chaine de référence qui est : "0123456789".

Afin d'avoir sous forme de caractères (pas de nombre) :

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
 
0
1
2
3
4
5
6
7
8
9
00
01
02
03
04
05
06
07
08
09
10
11
12
13
etc...
9999999999

Pouvez-vous m'aiguiller sur les fonctions et la méthode à employer ?

Code :

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

1
2
 
char chaine[] = "0123456789";

Merci,
ZiP

[SofEvans]

a chaud, je pense pour une suite de boucle for imbriqué. Est ce que cela ne va pas generer trop de nombre et prendre trop de temps ?

[Pouet_forever]

Ca fait beaucoup tout ça !
Dans quel but tu veux faire ça ? parce que pour lister toutes les possibilités il va te falloir un bon bout de temps

[[ZiP]]

Bonjour,

C'est pour alimenter un algorithme de brute force.

Il faudrait donc 3 boucles : longueur, parcours et caractères.
Qu'en pensez-vous ?

Je voudrais le faire de manière à ce que je puisse à l'avenir ajouter ou enlever des caractères dans ma chaine afin que le code soit réutilisable.

Merci,
ZiP

[[ZiP]]

J'ai commencé à développer un petit bout de code :

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
int _tmain(int argc, _TCHAR* argv[])
{
	char table[] = "0123456789";
	int taille_table = strlen(table);
	char buffer[15] = "";
	int longueur, position, index;
 
	for(longueur=1; longueur<=taille_table; longueur++)
	{
		for(position=0; position<longueur; position++)
		{
			for(index=0; index<taille_table; index++)
			{
				buffer[position] = table[index];
				printf("longueur=%d position=%d index=%d buffer=%s\n",longueur,position,index,buffer);
			}
			system("pause");
		}
	}
 
	system("pause");
	return 0;
}

Mais ça ne semble pas donner le résultat que je souhaite

Pouvez-vous m'aider à le corriger ?

Merci,
ZiP

[Pouet_forever]

Le brute force n'est pas le meilleur moyen à mon avis. J'ai codé ça et je l'ai laissé tourner 5 minutes, je me suis retrouvé avec un fichier de 10Go et il n'en était pas à la moitié

Après si tu veux vraiment le faire, je pense que le plus simple est de le faire en récursif

[[ZiP]]

Pouet_forever : je ne vais pas stocker les chaines générées mais les utiliser directement avec l'algorithme que j'ai rippé.

Peux-tu me donner un exemple simplifié avec du récursif pour me mettre sur la bonne voie ?

Merci,
ZiP

[Pouet_forever]

Voilà ce que j'ai fait :

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
29
30
31
32
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void faire_combi(char * str, char * tmp, int len, int ind) {
	int i;
 
	if (ind >= len) {
		printf("%s\n", tmp);
		return;
	}
 
	for (i = 0; i < len; i++) {
		tmp[ind] = str[i];
		faire_combi(str, tmp, len, ind+1);
	}
}
 
void combinaisons(char * str) {
	int len = strlen(str);
	char * tmp = calloc(len + 1, sizeof(char));
 
	faire_combi(str, tmp, len, 0);
 
	free(tmp);
}
 
int main(void) {
	char str[] = "01234";
	combinaisons(str);
	return 0;
}

[[ZiP]]

Pouet_forever : ton code marche très bien par contre, j'ai une question, au début, on a tout à 0 comme par exemple avec "0123456789" j'ai "0000000001" puis "0000000002" alors que je souhaite avoir : "0", "1", etc... "00", "01", "02", etc... "000", "001", "002", "003", etc...

Merci,
ZiP

[Pouet_forever]

Tu m'as demandé un exemple, pas la solution
Déjà là tu as tout pour faire ce que tu veux

[[ZiP]]

C'est vrai, j'ai un exemple de récursivité, je vais le modifier pour qu'il réponde à mes besoins !

ZiP

[darrylsite]

C'est vrai, j'ai un exemple de récursivité, je vais le modifier pour qu'il réponde à mes besoins !
ZiP

J'ai un code java qui fait exactement ce que tu veux. Si ça t'interesse je te le file pour que tu le convertisses.

[[ZiP]]

Bonjour darrylsite,

Je ne suis pas contre, pour voir la méthode utilisée.

Merci,
ZiP

[darrylsite]

Voilà le code

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
 
public class Main
{
    static String tab="1234";
    static int taille=tab.length();
 
    public static void main(String[] args)
    {
       for(int i=1; i<=taille; i++)
        generer(i, "");
    }
 
// loop : nombre caractere dans que les chaine generées doivent contenir
public static void generer(int loop, String sb)
   {
    if (sb.length()>=loop)
    {
         //on affiche la combinaison
         System.out.println( sb);
         return;
    }
   //taille est la longeur totale de la chaine de reference
    for(int i=0; i<taille; i++)
    {
      generer(loop, sb+tab.charAt(i));
    }
   }
}

[[ZiP]]

Voici le code en C modifié :

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
29
30
31
32
33
 
void bf(char *chaine, int taille_chaine, char *buffer, int longueur, int ind)
{
	int i;
 
	if(ind>=longueur)
	{
		printf("%s\n",buffer);
		return;
	}
 
	for(i=0; i<taille_chaine; i++)
	{
		buffer[ind] = chaine[i];
		bf(chaine,taille_chaine,buffer,longueur,ind+1);
	}
}
 
int _tmain(int argc, _TCHAR* argv[])
{
	char table[] = "0123456789";
	int taille_table = strlen(table);
	char * buffer = (char*)calloc(taille_table+1,sizeof(char));
 
	for(int i=1; i<taille_table; i++)
	{
		bf(table,taille_table,buffer,i,0);
	}
 
	free(buffer);
	system("pause");
	return 0;
}

Merci pour votre aide Pouet_forever et darrylsite !

ZiP

[darrylsite]

Voici le code en C modifié :

Code :

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

1
2
3
4
5
 
for(int i=1; i<taille_table; i++)
	{
		bf(table,taille_table,buffer,i,0);
	}

Je crois que tu dois plutot faire

Code :

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

1
2
3
4
5
 
for(int i=1; i<=taille_table; i++)
	{
		bf(table,taille_table,buffer,i,0);
	}

[[ZiP]]

Effectivement, c'est mieux comme ça

Merci,
ZiP

[Obsidian]

Je voudrais afficher toutes les combinaisons possibles à partir d'une chaine de référence qui est : "0123456789". Afin d'avoir sous forme de caractères (pas de nombre) :

Code :

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

1
2
3
4
5
6
7
 
…
8
9
00
01
…06

Pouvez-vous m'aiguiller sur les fonctions et la méthode à employer ?

Il y a une difficulté supplémentaire dans l'exemple que tu présentes : le fait que tu utilises le caractère « vide » ! C'est-à-dire que tu veux avoir « [ ]9 » avant « 00 ». Tu peux le faire en intégrant, de manière implicite ou explicite, ce caractère vide en début de chaîne.

Pour le reste, c'est de la numération. Il faut incrémenter la première colonne, puis la remettre à zéro lorsque tu atteins le maximum et incrémenter celle d'à côté. Tu peux faire un algorithme qui traite une chaîne d'une longueur arbitraire mais il te faut quand même, à l'usage, fixer un maximum car ta mémoire n'est pas infinie et tu vas avoir besoin de connaître la taille de ton buffer pour pouvoir l'afficher.

L'astuce étant de tenir compte du caractère vide : lorsque l'on « revient à zéro », il faut ré-incrémenter une fois de plus la colonne courante avant de passer à la suivante.

Moi, je procèderais comme suit :

Code C :

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
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
#include <string.h>
 
#define MAXLENGTH 5
#define TABLESIZE 11
 
int main (void)
{
    unsigned char           buffer [MAXLENGTH];
    char                    table  [TABLESIZE]  = "_abcdefghij";
    int                     x                   = 0;
    int                     y                   = 1;
 
    memset (buffer,0,MAXLENGTH);
    buffer [0] = 1;
 
    do
    {
        for (x=0;x<y;++x) putchar (table[buffer[y-x-1]]);
        puts ("");
 
        x=0;
        do
        {
            buffer [x] ++;
            buffer [x] %= TABLESIZE;
 
            if (!buffer[x])
            {
                buffer[x++]++;
                if (x>=y) y++;
            }
            else break;
        }
        while (x<MAXLENGTH);
    }
    while (x<MAXLENGTH);
 
    return 0;
}

[eyquem]

Bonjour,



Et moi j’ai écrit en 3 minutes (il a quand même fallu que je revois la doc pour choisir la bonne fonction)le code en Python qui fait aussi la chose en question:

Code :

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

1
2
3
4
5
6
7
from itertools import product
 
ch = '0123456789'
 
for k in xrange(1,11):
    for u in product(ch,repeat=k):
        print ''.join(u)

La fonction product() crée un itérateur qui crachote les valeurs du produit cartésien de ses arguments.

Par exemple:

Code :

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

print list(product('0123','AHY'))

affiche

[('0', 'A'), ('0', 'H'), ('0', 'Y'), ('1', 'A'), ('1', 'H'), ('1', 'Y'), ('2', 'A'), ('2', 'H'), ('2', 'Y'), ('3', 'A'), ('3', 'H'), ('3', 'Y')]

Pour obtenir les caractères rassemblés dans une seule chaîne, on utilise ''.join()

Code :

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

print list(''.join(u) for u in product('0123','AHY'))

affiche

['0A', '0H', '0Y', '1A', '1H', '1Y', '2A', '2H', '2Y', '3A', '3H', '3Y']

Le résultat de product() est un itérateur = les valeurs qu’il fournit sont délivrées à mesure qu’elles sont réclamées dans une itération, elles ne sont pas stockées toutes ensemble dans une structure de donnéees dans la mémoire.

product('0123','AHY') étant un itérateur, je le soumets à list() pour en faire une liste.







Pour faire un produit cartésien d’une même chaîne avec elle même, on écrit repeat=n comme argument, avec n un nombre

Par exemple list(product(’ABC’,repeat=3)) donne

['AAA', 'AAB', 'AAC', 'ABA', 'ABB', 'ABC', 'ACA', 'ACB', 'ACC', 'BAA', 'BAB', 'BAC', 'BBA', 'BBB', 'BBC', 'BCA', 'BCB', 'BCC', 'CAA', 'CAB', 'CAC', 'CBA', 'CBB', 'CBC', 'CCA', 'CCB', 'CCC']

L’argument qui suit ’repeat=’ contrôle le nombre de caractères assemblés dans chaque produit unitaire (’BAC“, CBA“...) du produit cartésien.






Enfin , bref, tout ça pour arriver à répondre à ta question:

Code :

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

1
2
3
4
5
6
7
8
9
10
from itertools import product
 
ch = '012'
 
li = []
for k in xrange(1,5):
    for u in product(ch,repeat=k):
        li.append( ''.join(u) )
 
print li

affiche

['0', '1', '2', '00', '01', '02', '10', '11', '12', '20', '21', '22', '000', '001', '002', '010', '011', '012', '020', '021', '022', '100', '101', '102', '110', '111', '112', '120', '121', '122', '200', '201', '202', '210', '211', '212', '220', '221', '222', '0000', '0001', '0002', '0010', '0011', '0012', '0020', '0021', '0022', '0100', '0101', '0102', '0110', '0111', '0112', '0120', '0121', '0122', '0200', '0201', '0202', '0210', '0211', '0212', '0220', '0221', '0222', '1000', '1001', '1002', '1010', '1011', '1012', '1020', '1021', '1022', '1100', '1101', '1102', '1110', '1111', '1112', '1120', '1121', '1122', '1200', '1201', '1202', '1210', '1211', '1212', '1220', '1221', '1222', '2000', '2001', '2002', '2010', '2011', '2012', '2020', '2021', '2022', '2100', '2101', '2102', '2110', '2111', '2112', '2120', '2121', '2122', '2200', '2201', '2202', '2210', '2211', '2212', '2220', '2221', '2222']

Je pense que c’est ce que tu veux (j'ai limité les nombres pour pouvoir mettre le resultat ici, sinon il y a 11111111110 chaines telles que tu les veux)



À une chose près: tu ne le veux pas en Python.

Mais comme Python est implémenté en C, j’ai pensé que tu pourrais regarder le code source pour t’en inspirer.




Maintenant, je retourne dans Pythonland.



PS

Pardon, pour utiliser au mieux les possibilités de Python, il est mieux d'utiliser un générateur:

Code :

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

1
2
3
4
5
6
from itertools import product
 
g = ( ''.join(u) for k in xrange(1,11) for u in product('0123456789',repeat=k) )
 
for emps in g:
    print emps

Comme ça, au cas improbable où ça interesserait quelqu’un.......

[Obsidian]

La fonction product() crée un itérateur qui crachote les valeurs du produit cartésien de ses arguments.

À une chose près: tu ne le veux pas en Python.

Mais comme Python est implémenté en C, j’ai pensé que tu pourrais regarder le code source pour t’en inspirer.

Maintenant, je retourne dans Pythonland.

Pour aller plus loin, l'ensemble des mots que [ZiP] cherche a obtenir s'écrit {0,1,2,3,4,5,6,7,8,9}*, soit l'étoile de Kleene, bien connue lorsque l'on traite des expressions régulières. En C, on ne dispose − par défaut − ni des listes, ni de la fonction produit(), par contre elle peuvent se trouver dans de nombreuses bibliothèques.

Sauf que dans le cas présent, on n'a besoin ni de l'une de l'autre pour parvenir au résultat.