Discussion :

[sullian85]

Hello,

Je souhaite développer un jeu de lettres.

Quel serait l'algorithme pour obtenir toutes les combinaisons d'une série de lettres aléatoire ?

Exemple

Chaine : "ABCD"

Résultat souhaité (sans les chiffres)
En 3 lettres
1110 ABC
1101 ABD
1011 ACD
0111 BCD

nota : je ne cherche pas à obtenir la chaine CBA qui pour mon jeu est la même que ABC ou BCA...

La longueur de la chaine peut varier de 4 à 8 et je ne souhaite pas les combinaisons de 2 lettres.

Donc par exemple pour 6 lettres je souhaite obtenir :

Les combinaisons de 5, 4 et 3 lettres.

Merci par avance pour votre aide.

Bien cordialement

[Bousk]

Un algo tout fait est std::sample en C++.
Faire un algo à partir d'un énoncé s'apelle faire ton travail et on pratique pas ça ici.
Tu peux sûrement trouver des implémentations de sample en C sur internet. Ou créer la tienne.

[WhiteCrow]

Bonsoir,

D'une manière générale, et plus particulièrement pour les jeux de lettres, l'algo pour générer les combinaisons uniques et triées s'inspire fortement de l'algo de l'odomètre. Par exemple, si tu as un tirage comme AABCCCD, tu représentes ça comme un multiensembe genre [ (A,2), (B,1), (C,3), (D,1) ]. L'algo de l'odomètre va te permettre de parcourir les nombres dont le premier chiffres est compris entre 0et 2, le second entre 0 et 1, le troisième entre 0 et 3 et le quatrième entre 0 et 1. Tu ne retiens que les combinaisons ayant au moins 3 éléments. Par exemple, l'algo te donnera successivement :
0000 → somme = 0, on passe au suivant
0001 → somme = 1, on passe au suivant
0010 → somme = 1, on passe au suivant
0011 → somme = 2, on passe au suivant
0020 → somme = 2, on passe au suivant
0021 → somme = 3, on visite CCD
0030 → somme = 3, on visite CCC
0031 → somme = 4, on visite CCCD
0100 → somme = 1, on passe au suivant
0101 → somme = 2, on passe au suivant
0110 → somme = 2, on passe au suivant
0111 → somme = 3, on visite BCD
0120 → somme = 3, on visite BCC
0121 → somme = 4, on visite BCCD
ainsi de suite …

Mais ce n'est pas forcément une technique adaptée dans tous les cas de figures (de jeux de lettres). Il y en a d'autres … mais pour cela il faudra être un peu plus précis dans l'explication de ce que tu veux faire et pas comment tu veux faire.
Par exemple ce n'est pas du tout adapté pour un jeu comme Wordle/Sutom, la tendance du moment.

[Sve@r]

Bonjour

https://www.dcode.fr/combinaisons. Il y a même un code en javascript dans la page.

tu veux les combinaisons sans répétition (ou 1 truc approchant)

Nan nan, c'est pas approchant, c'est exactement ça, des combinaisons.
Quand il y a répétition (ex ABC et CBA pris en compte comme deux résultats possibles) ce sont des arrangements.

[foetus]

Cela sent la recursion et l'algo doit être trouvable sur Internet

Je vois 1 algo comme cela avec ce code ... mais pas de gestion d'erreurs, pas de tests s'il y a des fuites, pas d'optimisations, qu'1 sortie en affichage

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 
void generate_1(char* sequence, size_t sequence_length, size_t nb_samples, size_t nb, size_t start_pos, char* result) {
    size_t pos;
 
//  printf("debug: generate_1 %lu, %lu, %s\n", nb, start_pos, result);
 
    if (nb < (nb_samples - 1)) {
        for (pos=start_pos; pos <= (sequence_length - nb_samples + nb); ++pos) {
            result[nb] = sequence[pos];
 
//          printf("debug: for %lu (%lu) -> %lu\n", start_pos, pos, (sequence_length - nb_samples + nb));
 
            generate_1(sequence, sequence_length, nb_samples, (nb + 1), (pos + 1), result);
        }
    } else {
        for (pos=start_pos; pos < sequence_length; ++pos) {
            result[nb] = sequence[pos];
 
            printf("*) %s\n", result);
        }
    }
 
    result[nb] = '\0'; // maybe useless, clean current element
}
 
 
void generate(char* sequence, size_t sequence_length, size_t nb_samples) {
    if (nb_samples < sequence_length) {
        if (nb_samples > 0) {
            char* result = malloc((nb_samples + 1) /* * sizeof(char)*/);
 
            if (result != NULL) {
                memset(result, '\0', (nb_samples + 1));
 
                generate_1(sequence, sequence_length, nb_samples, 0, 0, result);
 
                free(result);
                result = NULL;
            } else {
                printf("generate - error: malloc\n");
            }
        } else {
            printf("generate: nothing to do\n");
        }
    } else if (nb_samples == sequence_length) {
        printf("*) %s\n", sequence);
    } else {
        printf("generate - error: nb_samples > sequence_length\n");
    }
}
 
 
/*****************************************************************************/
/***********************************  Main  **********************************/
/*****************************************************************************/
 
int main(int argc, char* argv[])
{
    char sequence[] = {'A', 'B', 'C', 'D', 'E', '\0'};
    size_t nb;
 
    for(nb=0; nb <= 5; ++nb) {
        printf("\nNb elements %lu:\n", nb);
        generate(sequence, 5, nb);
    }
 
 
    return EXIT_SUCCESS;
}

Édit : nettoyage du code

[Sve@r]

Je vois 1 algo comme cela avec ce code ... mais pas de gestion d'erreurs, pas de tests s'il y a des fuites, pas d'optimisations, qu'1 sortie en affichage

On peut l'optimiser un peu. Déjà malloc()+memset(0) c'est typiquement calloc(). Mais pourquoi tout mettre à 0 alors que seul le dernier char de la string doit l'être ? => (*result)[nb_samples]='\0'. Les autres sont remplis ensuite au fur et à mesure de l'avancée (une string c'est des char puis ensuite un '\0' après ou bien un '\0' puis ensuite des char avant ).
Ensuite inutile de tester le null avant le free puisque free(NULL) est accepté.
Et surtout dans generate(), le paramètre "sequence_length" n'est pas utile car il est récupérable via strlen(sequence).

Mais c'est un joli travail technique

[foetus]

Quand il y a répétition (ex ABC et CBA pris en compte comme deux résultats possibles) ce sont des arrangements.

J'avais fais cela en mathématiques terminale S la théorie je comprends, mais la pratique c'est très mitigé
Donc je me méfie

...

En gros, calloc ne veut pas fonctionner, je voulais qu'à chaque étape le résultat n'ait pas 1 reste des étapes précédentes, j'ai déplacé l'allocation dynamique, je n'ai pas pensé au strlen parce qu'à la fin on doit avoir des tableaux/ listes.
Édit: j'ai lu trop vite la documentation de calloc : le premier paramètre n'est pas la valeur comme memset

Mais c'est un joli travail technique

En regardant ton lien, c'est le même principe : 1 boucle for en récursif, et à chaque fois, on prend l'élément courant, et on lance la récursivité sur la suite de la séquence.
La seule différence c'est la signification de la variable nb : soit c'est quel élément on traite (à 1 près, 0 index) (mon cas, de 0 à (max - 1)) soit c'est le reste des éléments à prendre (ton lien, de max à 1).

[Sve@r]

En gros, calloc ne veut pas fonctionner, je voulais qu'à chaque étape le résultat n'ait pas 1 reste des étapes précédentes, j'ai déplacé l'allocation dynamique

Bizarre, j'ai remplacé ton malloc() par (*result) = calloc((nb_samples + 1), sizeof(char)) et ça fonctionne chez-moi. Probablement une erreur autre qui a disparu quand tu as déplacé l'allocation.

je n'ai pas pensé au strlen parce qu'à la fin on doit avoir des tableaux/ listes.

Hop là danger confusion !!!
En C, un tableau de char c'est un tableau de char, ok, jusque là rien de compliqué. Mais si tu rajoutes dans ce tableau un '\0', ou si tu garantis que quoi qu'il arrive le tableau contiendra en fin de traitement un '\0' dans la plage des char alloués, alors tu as parfaitement le droit de le considérer ensuite comme string. C'est d'ailleurs la définition basique d'une string en C => un tableau de char contenant un '\0'. Souvent toute la difficulté consiste, quand on n'a qu'un simple tableau de char, à savoir où placer le '\0' sans utiliser de fonctions style strlen() (qui considèrent que le '\0' y est déjà). C'est un truc qui se mord parfois la queue (zut, j'aimerais bien utiliser strlen() pour placer le \0' mais je dois d'abord placer le '\0' pour utiliser strlen()).
D'ailleurs quand tu écris en fin de récursivité printf("*) %s\n", (*result)) tu considères implicitement (*result) comme string. Sinon t'as pas le droit d'utiliser "%s"

Et donc souvent, même quand on n'a besoin que d'un tableau, on rajoute quand-même le '\0' car ça ne mange qu'un octet et ça simplifie beaucoup de traitements ensuite.

[foetus]

tu considères implicitement (*result) comme string

Ce que je voulais dire c'est que le o.p. @sullian85 demande 1 algo, mais il n'a rien dit sur le stockage : stockage d'1 combinaison et stockage d'1 liste de combinaisons (et soit dit en passant ni même sur la séquence qui semble être 1 chaîne de caractères)
Et comme je l'ai dit, j'ai été au + simple : 1 seul tableau considéré comme 1 chaîne de caractères pour afficher la combinaison et je ne stocke rien, j'écrase (c'est pour cela comme tu l'as noté je fais du nettoyage 1 peu inutile pour supprimer les combinaisons précédentes)

[sullian85]

Bonjour,

Merci pour vos retours.
Je vais me permettre de vous proposer une solution suite à une transcription d'un algorithme trouvé en langage VB.

Avant cela je n'ai pas compris le retour de "Bousk" qui m'écrit : "Faire un algo à partir d'un énoncé s'apelle faire ton travail et on pratique pas ça ici."
Etant de nature bienveillante je ne me formaliserai pas.
Je ne demande à personne de faire mon travail.
J'ai cherché mais cela dépassait mon niveau en maths et en langage C.
Je ne pensais pas m'être trompé en postant ma demande dans un forum "Débutant" en langage C.

En tout cas voici ma proposition (Code::Blocks 20.03 mode console) issue je le redis d'un algorithme en VB qui n'est pas de ma conception.
En passant un argument il est possible de limiter les combinaisons remontées, dans le cas présent je ne souhaite pas avoir les combinaisons d'une seule lettre.
Je n'ai pas codé des cas d'erreurs possibles de valeurs des arguments.
Désolé je n'ai pas su inclure ce code dans une fenêtre comme ci-dessus, je suis preneur de la manip.

Bien cordialement

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define _LONGUEUR_CHAINE 256
 
void sub_combinatoire (char *, int);
 
void sub_combinatoire (char *chaine, int profondeur)
{
 
    char chaine_sortie[_LONGUEUR_CHAINE] = {""};
 
    int i,j;
    int puissance_1;
    int puissance_2;
    int index_chaine_sortie;
    int resultat_et;
 
    // Elever 2 à la puissance de la longueur de la chaine
    puissance_1 = pow (2,strlen(chaine));
 
    // Initialisation buffer de sortie
    memset (chaine_sortie, '\0', sizeof(chaine_sortie));
 
    index_chaine_sortie = 0;
 
    printf("Combinaisons possibles :\n");
 
    for (i=1; i < puissance_1; i++)
    {
 
        for (j=1; j < strlen(chaine)+1; j++)
        {
 
            puissance_2 = pow (2,j-1);
 
            resultat_et = puissance_2 & i;
 
            if (resultat_et != 0)
            {
                chaine_sortie[index_chaine_sortie] = chaine[j-1];
                index_chaine_sortie++;
            }
        }
 
        if (strlen(chaine_sortie) > profondeur)
        {
            printf("  %s\n", chaine_sortie);
        }
 
        memset (chaine_sortie, '\0', sizeof(chaine_sortie));
        index_chaine_sortie = 0;
 
    }
}
 
int main (void)
{
 
    sub_combinatoire ("ABCDE", 2);
    exit(0);
 
}

[Guesset]

Bonjour,

En C on remplacera puissance_1 = pow(2, strlen(chaine)); par puissance_1 = 1 << strlen(chaine); En général, il faut éviter de passer par des flottants pour obtenir un entier à partir d'entiers (même avec des conversions implicites). Code plus léger et beaucoup plus efficace.

De fait, la bibliothèque math n'est pas utilisée, l'include peut disparaître.

C'est du détail mais on peut revoir à la baisse la taille de la chaîne de sortie, même en supposant que les int soient remplacés par des uint64_t, la taille maximale n'excédera pas 65 (avec le 0 terminal).

Il faudrait peut être s'assurer au préalable que chaîne a une longueur minimale (au moins = profondeur) et profondeur > 1.

Pourquoi travailler avec j à partir de 1 si c'est pour l'utiliser dans des expressions systématiquement avec j-1 ? Autant commencer à 0, faire disparaître le +1 du test sur j et remplacer tous les j-1 par j.

Les remplissages de \0 ne servent à rien. Quand la boucle j se termine l'indice index_chaine_sortie donne le nombre de caractères. C'est donc lui qui doit être comparé à profondeur. Si index_chaine_sortie >= profondeur, on ajoute le caractère '\0' en chaine_sortie[index_chaine_sortie] = '\0'; pour terminer proprement la chaîne puis on affiche.

La boucle i pourrait commencer à (1 << profondeur) -1. Dans l'exemple, on voit bien que i = 1 ou 2 ne pourra avoir deux bits à 1 comme l'exige profondeur (2). La première valeur est 3 c'est à dire 2^2 - 1;

La boucle j travaille trop. Il faudrait la remplacer par for(j=0, ii = i; ii; j++, ii = ii >> 1). Le test devient if(ii & 1)....

Salutations

[Sve@r]

Il faut éviter les boucles type for (i=0; i < strlen(chaine); i++). Car le test de fin est fait à chaque itération => à chaque fois il va compter la chaine.
La solution immédiate serait de stocker sa longueur dans une variable et tester i < var. Mais la solution la plus efficace sera de passer par un pointeur qui balaye la chaine
Ainsi une boucle de ce type size_t i; for (i=0; i < strlen(chaine); i++) printf("%c", chaine[i]) devient char *pt; for (pt=chaine; *pt != '\0'; pt++) printf("%c", *pt).

Il faut aussi se méfier de sizeof() car c'est un faux ami. Sur un tableau, il se comportera parfaitement. Mais sur un pointeur il te donne juste la taille du pointeur !!! (remarque il se comporte là aussi parfaitement sauf que ce qu'il te donne ce n'est pas ce à quoi tu t'attends...)

Imagine le code

Code c :

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

1
2
char chaine[10];
memset(chaine, 0, sizeof(chaine))

C'est ok. Puis tu décides de découper un peu plus et de déporter ça dans une fonction. Tu écris naturellement

Code c :

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

1
2
3
4
5
6
void raz(char *c) {
    memset(c, 0, sizeof(c));
}
 
char chaine[10];
raz(chaine);

Et là, ton programme explose en vol et tu mets 10 ans à comprendre pourquoi.

Utilise les macros, c'est ce qu'il y a de plus fiable. Et tu peux même indiquer que tu n'oublies pas le '\0'.

Code c :

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

1
2
3
4
#define SZ_CHAINE          (10)
 
char chaine[SZ_CHAINE + 1];
memset(chaine, 0, SZ_CHAINE + 1)

Et surtout ça se fout pas mal du fait que le tableau ne soit qu'un pointeur

Code c :

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

1
2
3
4
5
6
7
8
#define SZ_CHAINE          (10)
 
void raz(char *c) {
    memset(c, 0, SZ_CHAINE + 1);
}
 
char chaine[SZ_CHAINE + 1];
raz(chaine);