Discussion :

[Kaluza]

Bonjour.

Je travaille en C++ et mon problème est le suivant :

D'un côté, j'ai un tableau de référence tabref remplis d'éléments tous différents.

De l'autre j'ai une fonction qui prend un tableau en paramètre et qui effectue un certain nombre d'opérations.

Ce que je cherche à faire c'est exécuter cette fonction pour tous les arrangements possibles (ordre des éléments) du tableau tabref.

Comment faire cela le plus simplement possible ?

Merci beaucoup

[Alikendarfen]

Bonjour,

Une démarche peut être la suivante :
- Implémentation récursive
- Utilisation d'une continuation (pointeur sur fonction, ou instance implémentant une méthode)

Deux fonctions sont à définir :
- Le point d'entrée de la récursion :

Code :

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

1
2
3
4
 
Initialisation d'un tableau indiquant les valeurs déjà utilisées
Initialisation d'un tableau qui contiendra le résultat
Appel de la fonction récursive avec un niveau 0 en paramètre

- La fonction récursive :

Code :

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

1
2
3
4
5
6
7
8
9
 
Si le niveau = la taille du tableau alors appeler la continuation
Sinon,
     Boucler sur les indices du tableau
          Si la valeur n'est pas déjà utilisée
               Marquer la valeur comme utilisée
               Assigner la valeur dans le résultat
               Appeler la fonction récursivement avec le niveau + 1
               Marquer la valeur comme non utilisée

En C#, ça donne ça (j'ai tout oublié de mon c++... désolé... mais j'ai mis plein de commentaires pour aider à la transposition) :

Code C# :

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
 
// list = ton tableau d'origine
// action = la continuation (en c++ implémenter sous forme d'un pointeur sur fonction ou passer un objet portant une méthode définie pour traiter les résultats
public static void Arrangement<T>( List<T> list, Action<IEnumerable<T>> action )
{
    // Initialisation d'un tableau de flag (false = non encore utilisé, true = déjà utilisé)
    // Ici, à l'allocation, tout est false par défaut
    bool[] flags = new bool[list.Count];
    // Le tableau qui va contenir le résult (il fait la taille du tableau d'origine)
    T[] result = new T[list.Count];
 
    // Appel de la fonction récursive avec tout ça et au niveau 0
    Arrangement( list, flags, result, 0, action );
}
 
static void Arrangement<T>( List<T> list, bool[] flags, T[] result, int level, Action<IEnumerable<T>> action )
{
    // Si le niveau = taille du tableau, alors on a fini
    if ( level == list.Count )
    {
        action( result );
    }
    else
    {
        // Boucle sur toutes les positions
        for ( int i = 0 ; i < list.Count ; i++ )
        {
            // Si pas déjà utilisé
            if ( flags[i] == false )
            {
                // Marquer comme utilisé
                flags[i] = true;
                // Mettre le résultat à sa position
                result[level] = list[i];
 
                // Appel récursif
                Arrangement( list, flags, result, level + 1, action );
 
                // Enlever le marquage
                flags[i] = false;
            }
        }
    }
}

Une implémentation récursive pour ce type de problème est souvent plus efficace qu'une implémentation itérative, car elle utilise peu de mémoire.

L'utilisation d'une continuation permet de ressortir simplement les résultats (pas besoin de "retourner" les résultats, on les exploite dès qu'on les a).

Mais attention le nombre d'arrangements grimpe très vite ! Donc sur des tableaux un peu grands, ça va prendre du temps de calcul !!

[Vakhyw]

Essaie next_permutation. La STL le fait pour toi moyennant la comparaison ;-)