Discussion :

[margagn]

Bonjour à tous,

Je sais que plusieurs d'entre-vous avez déjà parlé de ce sujet sur ce forum, mais je n'ai pas trouvé une réponse qui me convient. J'ai un tableau et j'aimerais afficher les n! permutations possible de ce même tableau. J'ai besoin d'un algorithme itératif et j'ai trouvé le suivant sur Wikipedia sous la rubrique Permutation :

Code :

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

1
2
3
4
5
6
7
8
function permutation(k, s) {
  var int factorial:= 1;
  for j = 2 to length(s) {
    factorial := factorial* (j-1);
    swap s[j - ((k / factorial) mod j)] with s[j];
  }
  return s;
}

L'algorithme est simple et pas très diffcile à comprendre et c'est essentiellement ce que je chercher. Je n'ai qu'a passer le numéro de permutation (<n!) la chaine et le tour est joué. Cependant, il y a un bogue dans cette algo et je n'arrive pas a trouver. Voici ma conversion de cette algo en C# 2.0 :

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
public static T[] Permutation<T>(int k, T[] array)
{
    int factorial = 1;
    for (int j = 2; j < array.Length; j++)
    {
        factorial *= (j - 1);
        int pos = j - ((k / factorial) % j) - 1;
 
        T temp = array[pos];
        array[pos] = array[j];
        array[j] = temp;
    }
 
    return array;
}

S'il vous plait, aidez-moi à trouver une correction à cette algo. Une correction qui va me donner une fonction simple (qui tiens en quelques lignes). Merci beaucoup de votre aide!

Martin

[titfab]

Je vois qu'une erreur de parenthèse :

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
public static T[] Permutation<T>(int k, T[] array)
{
    int factorial = 1;
    for (int j = 2; j < array.Length; j++)
    {
        factorial *= (j - 1);
        int pos = j - ((k / factorial) % j)) - 1;

        T temp = array[pos];
        array[pos] = array[j];
        array[j] = temp;
    }

    return array;
}

[margagn]

Mon code compile très bien. Il n'y a donc pas de problème de parenthèse. C'est un erreur dans mon algo que je ne trouve pas. Voici le résultat que j'obtiens

ABC(00000) = ACB
ABC(00001) = CBA
ABC(00002) = ACB
ABC(00003) = CBA
ABC(00004) = ACB
ABC(00005) = CBA

Voici les résultats que je devrais obtenir

ABC(00000) = ABC
ABC(00001) = ACB
ABC(00002) = BAC
ABC(00003) = BCA
ABC(00004) = CAB
ABC(00005) = CBA

Merci !

[FrancisSourd]

Je pense qu'il y a un problème dans les indices du tableau qui vont de 1 à s dans l'algo mais de 0 à s-1 dans ton code. Tu devrais utiliser array[j-1] dans ton code et la boucle doit avoir pour condition de fin j <= array.Length

[margagn]

Merci Francis !