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