Discussion :

[CosmoKnacki]

Dans le but de sortir toutes les combinaisons de p éléments parmi n éléments, je me suis référé à The Art of Computer Programming volume IV de Donald Knuth. On y trouve plusieurs algorithmes pour ce faire. J'ai donc essayé d'implémenter en PHP certains de ces algorithmes tels qu'ils sont écrits en pseudo-code pour voir ce que ça donne.

Regardons l'algorithme T:

T1. [Initialize.] Set c_j ⟵ j - 1 for 1 ≤ j ≤ t; then set c_{t + 1} ⟵ n, c_{t + 2} ⟵ 0, and j ⟵ t.
T2. [Visit.] (At this point j is the smallest index such that c_{j + 1} > j.) Visit the combination c_t … c₂c₁. Then, if j > 0, set x ⟵ j and go to step T6.
T3. [Easy case?] If c₁ + 1 < c₂, set c₁ ⟵ c₁ + 1 and return to T2. Otherwise set j ⟵ 2.
T4. [Find j.] Set c_{j - 1} ⟵ j - 2 and x ⟵ c_j + 1. If x = c_{j + 1}, set j ⟵ j + 1 and repeat step T4.
T5. [Done?] Terminate the algorithm if j > t.
T6. [Increase c_j.] Set c_j ⟵ x, j ⟵ j - 1, and return to T2.

Ce qui, en "traduction littérale" vers PHP donne ceci:

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
function combinations_DK_AOCP_Alg_T($n, $t) {
    $result = [];
 
    T1_Initialize:
        $c = array_combine(range(1, $t), range(0, $t - 1));
        $c[$t + 1] = $n;
        $c[$t + 2] = 0;
 
        $j = $t;
 
    T2_Visit:
        $result[] = array_slice($c, 0, $t);
 
        if ($j > 0) {
            $x = $j;
            goto T6_Increase_cj;
        }
 
    T3_Easy_case:
        if ($c[1] + 1 < $c[2]) {
            $c[1]++;
            goto T2_Visit;
        }
 
        $j = 2;
 
    T4_Find_j:
        $c[$j - 1] = $j - 2;
        $x = $c[$j] + 1;
 
        if ($x === $c[$j + 1]) {
            $j++;
            goto T4_Find_j;
        }
 
    T5_Done:
        if ($j > $t) return $result;
 
    T6_Increase_cj:
        $c[$j] = $x;
        $j--;
        goto T2_Visit;
}

Seulement voilà, goto c'est le mal, un vestige du passé pour les langages récents, la porte ouverte au code spaghetti, voire au n'importe quoi. (Avec le risque de se faire manger par un vélociraptor).
Alors je le réécris sans gotos ni labels du mieux possible:

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
function combinations($n, $p) {
    $combinations = [];
 
    // T1 Initialize
    $c = array_combine(range(1, $p), range(0, $p - 1));
    $c[$p + 1] = $n;
    $c[$p + 2] = 0;
 
    $j = $p;
 
    while (true) {
        // T2 Visit
        $combinations[] = array_slice($c, 0, $p);
 
        if ($j > 0) {
            $x = $j;
        } else {
            // T3 Easy case?
            if ($c[1] + 1 < $c[2]) {
                $c[1]++;
                continue;
            }
 
            $j = 2;
 
            // T4 Find j
            do {
                $c[$j - 1] = $j - 2;
                $x = $c[$j] + 1;
            } while ($x === $c[$j + 1] && $j++);
 
            // T5 Done 
            if ($j > $p) return $combinations;
        }
 
        // T6 Increase cj
        $c[$j] = $x;
        $j--;
    }
}

Les deux codes fonctionnent et ont les mêmes performances pour ce que je veux en faire. Mais avec ce dernier, j'ai du vilain:

• une boucle infinie while (true)
• trois niveaux d'imbrication
• un continue deux niveaux plus loin que le while auquel il se rapporte
• une condition de do...while dans laquelle j'ai dû fourrer une incrémentation && $j++

Mis à part le prêchi-prêcha à propos de l'Art du bien coder, je n'ai pas vraiment l'impression d'avoir gagner au change sur ce coup là. (À noter qu'avec un des autres algorithmes plus complexe que celui-ci, le revolving door algorithm c'est encore pire).

Qu'en pensez-vous? Voyez-vous une autre manière d'écrire ce même algorithme? (hormis renommer des variables ou remplacer le array_combine par une boucle for).

[mathieu]

quand vous dites "ont les mêmes performances", est ce que vous avez calculé si les modifications augmentent la complexité du code ?

[CosmoKnacki]

Si je ne me trompe pas, les deux fonctions sont en Ο(2ⁿ) dans le pire des cas lorsque t (ou p dans l'autre fonction) est proche de n/2. L'algorithme reste le même à peu de chose près, la seule différence du point de vue complexité réside dans le && $j++ de la deuxième fonction: alors que la première se contente d'incrémenter $j, celle-ci évalue $j comme condition supplémentaire. À noter que cette évaluation est effectuée C(n-2,p-2) fois. On peut aussi noter le remplacement du saut inconditionnel goto T2_Visit par un while(true): si insignifiante soit-elle, cette condition est évaluée C(n,p) fois.
Mais ce n'est pas trés important car je n'ai pas l'intention d'aller au delà de n=10, et qu'aucune différence de vitesse d'éxecution est notable. Ma question porte plus sur la lisibilité du code en rapport avec la façon dont il est structuré: peut-on faire ça mieux? Avec moins d'imbrications peut-être? Est-ce qu'au final la version littérale avec ses gotos et ses labels qui s'entrecroisent n'est pas plus claire?

[mathieu]

à performances égales, je préfère la version sans "goto".
même à mon inscription sur developpez.com en 2003, j'entendais déjà beaucoup de personnes qui recommandaient de ne pas l'utiliser donc j'ai toujours fait mon maximum pour l'éviter dans mon code php. donc je trouve la 2e version plus claire mais je ne suis peut-être pas objectif puisque ce choix vient de la ressemblance de ce code avec ma façon d'écrire du php.

[CosmoKnacki]

Moi même, je me demande si je ne suis pas influencé par la présentation "par étapes" de l'algorithme en pseudo-code.