Discussion :

[ane-mais]

Bonjour,


Comment générer toutes les possibilités uniques de 5 nombres construit à partir de (0,1,2,3,4,5), chaque possibilité n'utilisant qu'une seule fois le même chiffre dans les dizaines ou dans les unités.

[EDIT=pour plus de compréhension]
Par exemple cette possibilité n'est pas bonne : 01 02 23 48 51
- l'unité 1 est utilisée plusieurs fois,
- la dizaine 0 est utilisée plusieurs fois,
- il y a un 8 qui n'est pas dans la liste (0,1,2,3,4,5)
[/EDIT]

Voici un extrait du résultat attendu fait à la main , la présentation n'est qu'indicative, pour mieux lire) :

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
'00 11 22 33 44',
 
'01 10 22 33 44',
 
'02 10 21 33 44',
'02 11 20 33 44',
 
'03 10 21 32 44',
'03 10 22 31 44',
'03 11 20 32 44',
'03 11 22 30 44',
'03 12 20 31 44',
'03 12 21 30 44',
 
'04 10 21 32 43',
'04 10 21 33 42',
'04 10 22 31 43',
'04 10 22 33 41',
'04 10 23 31 42',
'04 10 23 32 41',
'04 11 20 32 43',
'04 11 20 33 42',
'04 11 22 33 44',
'04 11 22 34 43',
'04 11 23 30 42',
'04 11 23 32 40',
'04 12 20 31 43',
'04 12 20 33 41',
'04 12 21 30 44',
'04 12 21 34 40',
'04 12 23 30 41',
'04 12 23 31 40',
'04 13 20 31 42',
'04 13 20 32 41',
'04 13 21 30 42',
'04 13 21 32 40',
'04 13 22 30 41',
'04 13 22 31 40'
etc.

Je pense qu'il faudrait une fonction récursive, mais je n'arrive pas à la structurer.
Je m'y perds aussi avec le contrôle des chiffres déjà utilisés.

J'ai essayé de m'inspirer à partir de différents scripts affichant un tirage du loto (6 sur 49), je n'affiche pas le bon résultat.


Merci de votre attention et pour vos orientations, suggestions ou proposions de code.

[CosmoKnacki]

Il n'y a aucun contrôle des chiffres déjà utilisés à faire. Commence par créer une fonction (récursive ou pas) qui renvoie toutes les permutations de range(0, 4). Une fois que tu as réussi à faire ça, les chiffres des dizaines c'est juste de la déco.

[ane-mais]

Bonjour,
Merci de la proposition.
Je connais range(), qui rempli un tableau.
Cependant, je ne comprends pas comment range() peut générer toutes les possibilités uniques de 5 nombres construit à partir de (0,1,2,3,4,5), chaque possibilité n'utilisant qu'une seule fois le même chiffre dans les dizaines ou dans les unités, comme indiqué dans l'exemple (incomplet) que j'ai mis.

[CosmoKnacki]

Ne te fixe pas sur range(0, 4)! C'est juste une autre manière d'écrire [0, 1, 2, 3, 4]. Toujours est-il que tu dois commencer par écrire une fonction qui renvoie toutes les permutations de [0, 1, 2, 3, 4].

[ane-mais]

Toujours est-il que tu dois commencer par écrire une fonction qui renvoie toutes les permutations de [0, 1, 2, 3, 4].

C'est justement là que ça coince ... et que je bloque !
J'ai déjà modifié php.ini pour allouer + de mémoire, + de temps d'exécution.
Mais la fonction récursive je n'y arrive pas mieux que plusieurs boucle for imbriquées.

[cavo789]

Bonjour

Nul doute que d'autres personnes ont déjà écrit de telles fonctions. Premier lien retourné par Ggl : https://stackoverflow.com/a/5506933/1065340

Si j'exécute le code ci-dessous, voici ce que j'obtiens:

• 0 1 2
• 1 0 2
• 0 2 1
• 2 0 1
• 1 2 0
• 2 1 0

Est-ce la réponse à ton besoin ? Il te suffirait alors d'afficher les chiffres par bloc de deux.

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
 
<?php
 
 
function pc_permute($items, $perms = array( )) {
    if (empty($items)) { 
        print join(' ', $perms) . "<br/>";
    }  else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             pc_permute($newitems, $newperms);
         }
    }
}
 
 
pc_permute(array(0, 1, 2));

Pour ton besoin, ce serait donc pc_permute(array(0, 1, 2, 3, 4));

[CosmoKnacki]

Tu trouveras sur cette page la description de plusieurs algorithmes permettant de générer les permutations.

Sinon, la première idée que j'ai eue, c'est cette fonction récursive:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
function genperm($tab) {
    if ( empty($tab) ) return $tab;
    if ( count($tab) === 1 ) return [ [array_pop($tab)] ];
    $result = [];
    foreach($tab as $k => $v) {
        $tmp = $tab;
        unset($tmp[$k]);
        foreach(genperm($tmp) as $p) {
            $result[] = [$v, ...$p];
        }
    }
    return $result;
}

À chaque élément du tableau, on génére les permutations des éléments restants qu'on ajoute à l'élément de départ.
Voilà, comme la plupart des fonctions récursives, c'est pas trés performant (le nombre d'appels augmente rapidement avec la taille du tableau), mais c'est concis. Pour ce qui est de celle-ci, elle présente deux avantages: les résultats sont par ordre croissant et il est facile d'ajouter le chiffre des dizaines qui n'est ni plus ni moins que le niveau de récursion de la fonction, exemple:

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
function genperm($tab, $level = 0) {
    if ( empty($tab) ) return $tab;
    if ( count($tab) === 1 ) return [ [$level . array_pop($tab)] ];
    $result = [];
    foreach($tab as $k => $v) {
        $tmp = $tab;
        unset($tmp[$k]);
        foreach(genperm($tmp, $level + 1) as $p) {
            $result[] = ["$level$v", ...$p];
        }
    }
    return $result;
}
 
$result = genperm(range(0,5));

---

Autre méthode, non récursive:

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
function permute($arr) {
    if (empty($arr)) return [];
    $perms = [[array_pop($arr)]];
 
    foreach ($arr as $n) {
        $tmp = [];
        foreach ($perms as $perm) {
            for ($i = 0; $i <= count($perm); $i++) {
                $tperm = $perm;
                array_splice($tperm, $i, 0, $n);
                $tmp[] = $tperm;
            }
        }
        $perms = $tmp;
    }
 
   return $perms;
}

La méthode consiste à démarrer le tableau des permutations par un seul élément (un seul élément a une seule permutation), puis on réécrit ce tableau en insérant un nouvel élement du tableau de départ à toute les positions possibles de chaque permutation présente dans le tableau des permutations. Par exemple pour [0, 1, 2, 3, 4] ça donne:

Code txt :

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

1
2
3
4
5
6
7
$perms                                                  | $n
--------------------------------------------------------+----
[[4]]                                                   |
[[0,4],                     [4,0]]                      | 0
[[1,0,4], [0,1,4], [0,4,1], [1,4,0], [4,1,0], [4,0,1]]  | 1
[[2,1,0,4], [1,2,0,4], [1,0,2,4],    ...    [4,0,1,2]]  | 2
--------------------------------------------------------+----

Bien plus rapide que le précédent algorithme, par contre il oblige à reparcourir toutes les permutations trouvées pour pouvoir ajouter les chiffres des dizaines. Pour ce faire on peut par exemple exploiter les clefs des permutations lors d'un foreach, ou bien construire dés le départ une chaîne formatée adéquate qu'on exploitera avec vprintf ou vsprintf: vprintf("0%d 1%d 2%d 3%d", [0,1,2,3]);.
Avec cet algorithme, les résultats ne sont pas ordonnés.

---

Le top serait sûrement de créer un générateur utilisant l'algorithme SJT. Il y a peut-être aussi quelque chose à faire du coté des data structures dont certaines disposent d'une méthode rotate (comme par exemple Ds\Vector) qui permettrait de générer facilement des permutations circulaires.

[NoSmoking]

Bonjour,
vous parlez de permutation alors qu'il semblerait que le but et de déterminer les combinaisons de p, ici 5, éléments d'un ensemble de n, ici 55, éléments, avec les contraintes demandées.

Là pour le coup cela représente au départ

            55!
nbrComb = --------------- = 3478761
           5! ( 55 - 5 )!

... c'est pas rien.

Il y a moyen d'« écrémer » dès le départ pour limiter la casse.

[CosmoKnacki]

Là pour le coup cela représente au départ

            55!
nbrComb = --------------- = 3478761
           5! ( 55 - 5 )!

... c'est pas rien.

Attention, nous sommes ici en base 5 donc il n'y a pas 55 éléments mais juste 25 (00 01 02 03 04 10 11 12 13 14 20 21 22 ... 44). Donc le nombre de combinaisons de 5 éléments parmi 25 est "juste" 53130 (ce qui n'est pas rien non plus).

Il y a moyen d'« écrémer » dès le départ pour limiter la casse.

Oui et la ruse c'est de ne pas chercher à produire ces combinaisons pour les filtrer ensuite suivant les contraintes. Il suffit juste de remarquer que le résultat attendu est juste l'ensemble des permutations de 5 éléments auquel on applique un habillage (un masque) pour produire les dizaines:

 permutations  | habillage
---------------+-----------------
 0 1 2 3 4     | 00 11 22 33 44
 0 1 2 4 3     | 00 11 22 34 43
 0 1 3 2 4     | 00 11 23 32 44
 0 1 3 4 2     | 00 11 23 34 42
 0 1 4 2 3     | 00 11 24 32 43
 0 1 4 3 2     | 00 11 24 33 42
 0 2 1 3 4     | 00 12 21 33 44
 ...           | ...
 4 3 2 1 0     | 04 13 22 31 40 

[NoSmoking]

Attention, nous sommes ici en base 5 donc ...

... que dire ...

[CosmoKnacki]

En #7, j'avais émis l'idée d'exploiter les data structures et notamment la méthode rotate de certaines:

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
function permutatronix($arr) {
    $dq = new Ds\Deque();
 
    if (empty($arr)) return $dq;
 
    $perm = new Ds\Vector([$arr[0]]);
    unset($arr[0]);
    $dq->push($perm);
    $format = '0%d';
 
    foreach ($arr as $k => $elt) { 
        $format .= " $k%d";
 
        $count = count($dq);
        for ($i=0; $i < $count; $i++) { // chaque permutation présente précédemment dans la Deque
            $perm = $dq->shift(); // est sortie une à une par la gauche de la Deque
            $perm->push($elt); // on ajoute à la permutation un nouvel élément du tableau
            $dq->push($perm->copy());
 
            for ($j=0; $j < $k; $j++) { // puis on effectue $k permutations circulaires
                $perm->rotate(1);
                $dq->push($perm->copy()); // que l'on enfourne par la droite dans la Deque
            }
        } // toutes les anciennes permutations sont sorties, il ne reste que les nouvelles
    }
    return $dq->map(fn($v) => vsprintf($format, $v->toArray()))->sorted();
}
 
print_r(permutatronix(range(0,5))->toArray());

C'est assez efficace. Il faut bien sûr installer le module Ds.

[ane-mais]

Bonjour et un grand merci à vous tous !

J'ai du être absentes quelques jours et j'apprécie beaucoup vos échanges.

Après réflexion, vous avez raison, à ma grande surprise : les dizaines ce n'est qu'un habillage.
Quoique ! Il va falloir que le 5 remplace au fur et à mesure un chiffre parmi (0,1,2,3,4).

Peut-être que je parle pour rien, car je n'ai que survolé rapidement vos propositions.

Le temps de lire tout ça, de le comprendre et de l'assimiler, et je reviens ...

@+

[CosmoKnacki]

Je viens de tilter que tu souhaites des ensembles de 5 nombres mais composés avec 6 chiffres (et pas 5). Ce que tu peux faire, c'est utiliser n'importe quelle des solutions proposées pour produire des ensembles de 6 nombres à partir de 6 chiffres et pour chaque résultat, enlever un des nombres (il faut donc le faire 6 fois par résultat).

00 11 22 33 44 55 donnera alors:
--------------------------------------
11 22 33 44 55
00 22 33 44 55
00 11 33 44 55
00 11 22 44 55
00 11 22 33 55
00 11 22 33 44

[CosmoKnacki]

Une implémentation utilisant les générateurs ainsi que l'algorithme de Narayana Pandita pour générer le permutation:

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
function NarayanaPandita ($arr) {
    while(true) {
        yield from cloth($arr);
 
        for ($i = 0, $k = -1; $i < count($arr) - 1; $i++) {
            if ( $arr[$i] < $arr[$i + 1] ) $k = $i;
        }
 
        if ($k < 0) return;
 
        $l = $k + 1;
        for ($i = $l + 1; $i < count($arr); $i++) {
            if ( $arr[$k] < $arr[$i] ) $l = $i;
        }
 
        [$arr[$k], $arr[$l]] = [$arr[$l], $arr[$k]];
 
        $tmp = array_reverse(array_slice($arr, $k + 1));
        array_splice($arr, $k+1, count($tmp), $tmp);
    }
}
 
function cloth($elts) {
    foreach($elts as $k => $v) {
        $elts[$k] = "$k$v";
    }
 
    yield from combinate($elts);
}
 
function combinate($elts) {
    foreach($elts as $k => $v) {
        $tmp = $elts;
        unset($tmp[$k]);
        yield array_values($tmp);
    }
}
 
$gen = NarayanaPandita(range(0,5));
$result = [];
foreach ($gen as $comb) {
    $result[] = implode(' ', $comb);
}
 
sort($result);
 
foreach ($result as $res) echo $res, PHP_EOL;

Le sort à la fin n'est nécessaire que pour obtenir les résultats dans l'ordre lexicographique, sinon on peut s'en passer.

[ane-mais]

Bonjour,

Merci pour vos réponses.
Désolée, je n'ai pas eu une minute pour approfondir vos réponses, surtout les bouts de code.

Cependant, à voir vite fait, l'avant dernière réponse de CosmoKnacki semble ne pas correspondre. J'ai bien dit semble car je n'ai pas encore analysé son dernier code.

Je ne cherche pas à permuter 00 11 22 33 44 55 avec 5 nombres, mais à générer toutes les possibilités uniques :
- de 5 nombres construit à partir de (0,1,2,3,4,5),
- chaque possibilité n'utilisant qu'une seule fois le même chiffre dans les dizaines ou dans les unités.

Par exemple cette petite série non exhaustive est comprise dans le "etc." de mon premier exemple :

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
'00 55 22 33 44',
 
'01 23 40 12 34', 
 
'02 50 25 33 44',
'02 55 20 33 44',
 
'03 50 22 35 44',
'03 50 25 32 44',
'03 52 20 35 44',
'03 52 25 30 44',
 
'04 50 22 33 45',
'04 50 22 35 43',
'04 50 23 32 45',
'04 50 23 35 42',
'04 50 25 32 43',
'04 50 25 33 42',
'04 52 20 35 43',
'04 52 20 33 45',
'04 52 23 30 45',
'04 52 23 35 40',
'04 52 25 30 44',
'04 52 25 34 40',
'04 53 20 32 45',
'04 53 20 35 42',
'04 53 22 30 45',
'04 53 22 35 40',
'04 53 25 30 42',
'04 53 25 32 40',
'04 55 20 32 43',
'04 55 20 33 42',
'04 55 22 33 44',
'04 55 22 34 43',
'04 55 23 30 42',
'04 55 23 32 40',
 
'05 50 22 33 44',
 
'11 22 33 44 55',
 
'12 34 51 23 45', 
 
'23 45 02 34 50',
 
'34 23 45 02 50',
ect.

édit du 15/03/2022 :
suite à la pertinente remarque de CosmoKnacki je viens d'ôter la ligne '45 23 02 50 34' qui n'avait rien à faire là

[CosmoKnacki]

Code :

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

1
2
'34 23 45 02 50',
'45 23 02 50 34'

Ces deux entrées contiennent les mêmes nombres, doit-on en conclure que tu recherches non pas toutes les combinaisons de 5 nombres à deux chiffres, mais plutôt tous les arrangements de 5 nombres à deux chiffres répondants aux contraintes?

[ane-mais]

Bonjour et merci CosmoKnacki pour cette perspicacité.

Ce sont biens les combinaisons et non les arrangements que je cherche à obtenir. Heureusement qu'il y a des exemples sur wikipedia, car je n'ai rien compris aux définitions.

[CosmoKnacki]

Donc mon code précédent répond bien à ta question. Ceci dit, on doit pouvoir faire bien plus efficace. Si j'ai une autre idée je la posterai.

[ane-mais]

Je pense avoir compris.
Mais qui sait ?
Je vais m'en servir afin de poursuivre mon projet que je viens d'exposer sur :
https://www.developpez.net/forums/d2...s-predictions/

Ce n'était pas la peine de vous prendre la tête avec le projet en entier, vu que c'est cette histoire de combinaisons qui me perturbait.

Merci encore pour vos réponses et votre disponibilité.

Je vais attendre un peu avant de définir comme "résolu" ce sujet, au cas où j'aurai des soucis de compréhension au moment de le mettre en oeuvre.

[ane-mais]

Une implémentation utilisant les générateurs ainsi que l'algorithme de Narayana Pandita pour générer le permutation:

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
function NarayanaPandita ($arr) {
    while(true) {
        yield from cloth($arr);
 
        for ($i = 0, $k = -1; $i < count($arr) - 1; $i++) {
            if ( $arr[$i] < $arr[$i + 1] ) $k = $i;
        }
 
        if ($k < 0) return;
 
        $l = $k + 1;
        for ($i = $l + 1; $i < count($arr); $i++) {
            if ( $arr[$k] < $arr[$i] ) $l = $i;
        }
 
        [$arr[$k], $arr[$l]] = [$arr[$l], $arr[$k]];
 
        $tmp = array_reverse(array_slice($arr, $k + 1));
        array_splice($arr, $k+1, count($tmp), $tmp);
    }
}
 
function cloth($elts) {
    foreach($elts as $k => $v) {
        $elts[$k] = "$k$v";
    }
 
    yield from combinate($elts);
}
 
function combinate($elts) {
    foreach($elts as $k => $v) {
        $tmp = $elts;
        unset($tmp[$k]);
        yield array_values($tmp);
    }
}
 
$gen = NarayanaPandita(range(0,5));
$result = [];
foreach ($gen as $comb) {
    $result[] = implode(' ', $comb);
}
 
sort($result);
 
foreach ($result as $res) echo $res, PHP_EOL;

Le sort à la fin n'est nécessaire que pour obtenir les résultats dans l'ordre lexicographique, sinon on peut s'en passer.

Parse error: syntax error, unexpected 'from' (T_STRING) à la ligne 4
certainement la version de mon php 5.4

Avant l'existence de yield, ma fonction retournait un tableau de valeurs ou de tableaux.
Il va falloir que j'évolue, je ne connaissais par yield. C'est depuis quelle version de php ?