Discussion :

[unix27]

Salut, je souhaiterais faire une matrice dont chaque ligne désigne une (combinaison unique:exemple 1,2,3,4,5)
Concrètement, j'ai par exemple un tableau de 5 éléments comme ceci:

Code :

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

INT[] t = new INT[] { 1,2,3,4,5};

et je veux avoir une matrice comme cela:

1,2,3,4,5
1,2,3,5,4
1,2,4,3,5
1,2,4,5,3
1,2,5,3,4
1,2,5,4,3

2,1,3,4,5
2,1,3,5,4
2,1,4,3,5
2,1,4,5,3
2,1,3,4,5
2,1,3,5,4

3...
4...
5...

une implémentation sera l'idéale puisque je suis débutant en C#
Merci

[Drezounet218]

Ce que tu souhaites se nomme une 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
 public class Permute
    {
        public static void Commencer(int[] list)
        {
            travaille(list, 0, list.Length - 1);
        }
 
 
        private static void echange(ref int a, ref int b)
        {
            if (a == b) return;
            a ^= b;
            b ^= a;
            a ^= b;
        }
 
 
        private static void  travaille(int[] list, int current, int max)
        {
            int i;
            if (current == max)
            {
 
                foreach (var item in list)
                {
                    Console.Write(Convert.ToString(item));
                }
                Console.WriteLine(" ");
            }
            else
                for (i = current; i <= max; i++)
                {
                    echange(ref list[current], ref list[i]);
                    travaille(list, current + 1, max); // on descend
                    echange(ref list[current], ref list[i]);
                }
        }
    }

Pour l'appeller : Permute.Commencer(new int[] {1,2,3,4,5});

[unix27]

Ce que tu souhaites se nomme une 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
 public class Permute
    {
        public static void Commencer(int[] list)
        {
            travaille(list, 0, list.Length - 1);
        }
 
 
        private static void echange(ref int a, ref int b)
        {
            if (a == b) return;
            a ^= b;
            b ^= a;
            a ^= b;
        }
 
 
        private static void  travaille(int[] list, int current, int max)
        {
            int i;
            if (current == max)
            {
 
                foreach (var item in list)
                {
                    Console.Write(Convert.ToString(item));
                }
                Console.WriteLine(" ");
            }
            else
                for (i = current; i <= max; i++)
                {
                    echange(ref list[current], ref list[i]);
                    travaille(list, current + 1, max); // on descend
                    echange(ref list[current], ref list[i]);
                }
        }
    }

Pour l'appeller : Permute.Commencer(new int[] {1,2,3,4,5});

Un grand merci à Drezounet218 d'avoir lu(e) et répondu(e) à mon post en plus c'est rapide et avec une implémentation
Vraiment top!!

[unix27]

Ce que tu souhaites se nomme une 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
 public class Permute
    {
        public static void Commencer(int[] list)
        {
            travaille(list, 0, list.Length - 1);
        }
 
 
        private static void echange(ref int a, ref int b)
        {
            if (a == b) return;
            a ^= b;
            b ^= a;
            a ^= b;
        }
 
 
        private static void  travaille(int[] list, int current, int max)
        {
            int i;
            if (current == max)
            {
 
                foreach (var item in list)
                {
                    Console.Write(Convert.ToString(item));
                }
                Console.WriteLine(" ");
            }
            else
                for (i = current; i <= max; i++)
                {
                    echange(ref list[current], ref list[i]);
                    travaille(list, current + 1, max); // on descend
                    echange(ref list[current], ref list[i]);
                }
        }
    }

Pour l'appeller : Permute.Commencer(new int[] {1,2,3,4,5});

j'ai juste une petite remarque concernant les éléments à envoyer ,j'ai changé ça:

Code :

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

Permute.Commencer(new int[] {1,2,3,4,5})

avec ça:

Code :

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

Permute.Commencer(new double[] {1.0,2.0,3.0,4.0,5.0})

+j'ai fait toutes les conversions nécessaires en remplaçant int par double mais le compilateur me met cette erreur:

L'opérateur '^=' ne peut pas être appliqué aux opérandes de type 'double' et 'double'

quand il rentre dans la partie

Code :

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

1
2
3
4
5
6
7
 
...
 if (a == b) return;
            a ^= b;
            b ^= a;
            a ^= b;
...

[unix27]

j'ai juste une petite remarque concernant les éléments à envoyer ,j'ai changé ça:

Code :

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

Permute.Commencer(new int[] {1,2,3,4,5})

avec ça:

Code :

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

Permute.Commencer(new double[] {1.0,2.0,3.0,4.0,5.0})

+j'ai fait toutes les conversions nécessaires en remplaçant int par double mais le compilateur me met cette erreur:

L'opérateur '^=' ne peut pas être appliqué aux opérandes de type 'double' et 'double'

quand il rentre dans la partie

Code :

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

1
2
3
4
5
6
7
 
...
 if (a == b) return;
            a ^= b;
            b ^= a;
            a ^= b;
...

autre précision on laissant le script initial sans rien changer (avec des int...) ce jeux de données ne marche pas

Code :

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

Permute.Commencer(new int[] {1,2,3,4,1,2,3,4})

...
il fait des permutations... beaucoup trop de permutations bon ... je continue de chercher un script en C# qui fait toutes les permutations possible ...

[worm83]

Je n'ai pas pu m’empêcher, je m'amusais avec CodeDom, du coup je me suis amusé à faire un script qui genere le code pour un type passé en parametre.

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
   public static string GenerateCode<T>(string className, T[] t)
        {
            StringBuilder retour = new StringBuilder(@"
using System;
using DynamicCompilation;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Microsoft.CSharp;
using System.CodeDom.Compiler;
 
namespace DynamicCombinator{
public class " + className + @" : ICombinaison<" + t.GetType().ToString().Replace("[]", "") + @">{
 
public Action<IEnumerable<" +t.GetType().ToString().Replace("[]","")+@">> EachLine { get; set; }
 
public void Start(" + t.GetType().ToString().Replace("[]", "") + @"[] tab){
 
" +t.GetType()+" retour= new "+t.GetType().ToString().Replace("[]","")+"[tab.Length];");
 
            for (int i = 0; i < t.Length; i++)
            {
                retour.Append(t.GetType() + "t" + i + " = new " + t.GetType() + "{");
                t.ToList().ForEach(x =>
                {
                    retour.Append(x.ToString() + ",");
                });
                retour.Append("};");
                retour.AppendLine();
            }
 
            for (int i = 0; i < t.Length; i++)
            {
                retour.Append("for(int i" + i + "=0;i" + i + " < t" + i + @".Length; i" + i + "++){ retour["+i+"]=t" + i + "[i" + i + "];");
            }
 
            retour.AppendLine("if(EachLine!=null) EachLine(retour);");
            for (int i = 0; i < t.Length; i++)
            {
                retour.AppendLine("}");
            }
 
            retour.Append("}}}");
            return retour.ToString();
        }
    }

l'interface qui est implémenté :

Code :

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

1
2
3
4
5
6
    public interface ICombinaison<T>
    {
        void Start(T[] tab);
 
        Action<IEnumerable<T>> EachLine { get; set; }
    }

Pour l'utiliser :

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
 
            int[] t = new int[] { 1, 2, 3, 4, 5 };
            using (CSharpCodeProvider provider = new CSharpCodeProvider())
            {
                var assemName = "DynamicCombinator";
                var className = "Test";
                CompilerParameters compilParameter = new CompilerParameters(new[] { "DynamicCompilation.dll", "System.dll", "System.Core.dll", "System.Data.dll" });
                compilParameter.GenerateInMemory = true;
                compilParameter.GenerateExecutable = false;
                compilParameter.TempFiles = new TempFileCollection(".", false);
                compilParameter.OutputAssembly = assemName;
 
                var code = CodeGeneration.GenerateCode<int>(className, t);
 
                CompilerResults cr = provider.CompileAssemblyFromSource(compilParameter, code);
                if (cr.Errors.Count > 0) throw new Exception("Erreur sur le code dynamique.");
               var clName = cr.CompiledAssembly.GetType(assemName + "."+className);
                ICombinaison<int> test;
                test= Activator.CreateInstance(clName) as ICombinaison<int>;
 
                test.EachLine = (ligne) =>
                        {
                            foreach (var x in ligne)
                            {
                                Console.Write(x);
                            }
                            Console.Write("\r\n");
 
                        };   
                test.Start(t);               
            }
 
            Console.ReadLine();
 
        }

Et donne pour l'exemple donné :

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
    public class Test : ICombinaison<System.Int32>
    {
        public Action<IEnumerable<System.Int32>> EachLine { get; set; }
 
        public void Start(System.Int32[] tab)
        {
 
            System.Int32[] retour = new System.Int32[tab.Length]; System.Int32[] t0 = new System.Int32[] { 1, 2, 3, 4, 5, };
            System.Int32[] t1 = new System.Int32[] { 1, 2, 3, 4, 5, };
            System.Int32[] t2 = new System.Int32[] { 1, 2, 3, 4, 5, };
            System.Int32[] t3 = new System.Int32[] { 1, 2, 3, 4, 5, };
            System.Int32[] t4 = new System.Int32[] { 1, 2, 3, 4, 5, };
            for (int i0 = 0; i0 < t0.Length; i0++)
            {
                retour[0] = t0[i0];
                for (int i1 = 0; i1 < t1.Length; i1++)
                {
                    retour[1] = t1[i1]; 
                    for (int i2 = 0; i2 < t2.Length; i2++)
                    {
                        retour[2] = t2[i2];
                        for (int i3 = 0; i3 < t3.Length; i3++)
                        {
                            retour[3] = t3[i3]; 
                            for (int i4 = 0; i4 < t4.Length; i4++)
                            {
                                retour[4] = t4[i4]; 
                                if (EachLine != null) EachLine(retour);
                            }
                        }
                    }
                }
            }
        }
    }

Edit : Une bonne refacto serais de passer le type ainsi que la taille du tableau pour la génération. J'ai fait le code rapidement et ne me suis pas penché sur la mutualisation.

[unix27]

oups! j'ai pas réussi à compiler tout cela des erreurs...y'a pas une source plus simple?

[worm83]

Lol j'ai pas tout mis, c'est juste le principe.

Le code final avec les boucle for est le bon. Qui plus est, sur beaucoup d'itérations, il vaut mieux passer par des boucle que du recurssif.
refactorise 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
 
 public class Test
    {
        public Action<IEnumerable<System.Int32>> EachLine { get; set; }
 
        public void Start(System.Int32[] tab)
        {
 
            System.Int32[] retour = new System.Int32[tab.Length]; System.Int32[] t0 = new System.Int32[] { 1, 2, 3, 4, 5, };
            System.Int32[] t1 = new System.Int32[] { 1, 2, 3, 4, 5, };
            System.Int32[] t2 = new System.Int32[] { 1, 2, 3, 4, 5, };
            System.Int32[] t3 = new System.Int32[] { 1, 2, 3, 4, 5, };
            System.Int32[] t4 = new System.Int32[] { 1, 2, 3, 4, 5, };
            for (int i0 = 0; i0 < t0.Length; i0++)
            {
                retour[0] = t0[i0];
                for (int i1 = 0; i1 < t1.Length; i1++)
                {
                    retour[1] = t1[i1]; 
                    for (int i2 = 0; i2 < t2.Length; i2++)
                    {
                        retour[2] = t2[i2];
                        for (int i3 = 0; i3 < t3.Length; i3++)
                        {
                            retour[3] = t3[i3]; 
                            for (int i4 = 0; i4 < t4.Length; i4++)
                            {
                                retour[4] = t4[i4]; 
                                if (EachLine != null) EachLine(retour);
                            }
                        }
                    }
                }
            }
        }
    }

Il faut que tu passe le tableau en paramètre et que tu le copie en 5 fois.

[unix27]

Lol j'ai pas tout mis, c'est juste le principe.

Le code final avec les boucle for est le bon. Qui plus est, sur beaucoup d'itérations, il vaut mieux passer par des boucle que du recurssif.
refactorise 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
 
 public class Test
    {
        public Action<IEnumerable<System.Int32>> EachLine { get; set; }
 
        public void Start(System.Int32[] tab)
        {
 
            System.Int32[] retour = new System.Int32[tab.Length]; System.Int32[] t0 = new System.Int32[] { 1, 2, 3, 4, 5, };
            System.Int32[] t1 = new System.Int32[] { 1, 2, 3, 4, 5, };
            System.Int32[] t2 = new System.Int32[] { 1, 2, 3, 4, 5, };
            System.Int32[] t3 = new System.Int32[] { 1, 2, 3, 4, 5, };
            System.Int32[] t4 = new System.Int32[] { 1, 2, 3, 4, 5, };
            for (int i0 = 0; i0 < t0.Length; i0++)
            {
                retour[0] = t0[i0];
                for (int i1 = 0; i1 < t1.Length; i1++)
                {
                    retour[1] = t1[i1]; 
                    for (int i2 = 0; i2 < t2.Length; i2++)
                    {
                        retour[2] = t2[i2];
                        for (int i3 = 0; i3 < t3.Length; i3++)
                        {
                            retour[3] = t3[i3]; 
                            for (int i4 = 0; i4 < t4.Length; i4++)
                            {
                                retour[4] = t4[i4]; 
                                if (EachLine != null) EachLine(retour);
                            }
                        }
                    }
                }
            }
        }
    }

Il faut que tu passe le tableau en paramètre et que tu le copie en 5 fois.

Merci worm83, je viens de me rendre compte que les deux scripts le tien+celui de Drezounet218 répondent bien au problème je viens de tester ceci :

• Code :

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

  double[] t = new double[] { 1.0,2.0,3.0,4.0};

  donne 24 permutations

• Code :

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

  double[] t = new double[] { 1.0,2.0,3.0,4.0,1.0,2.0,3.0,4.0};

  donne 40320 permutations
• Pour 12 éléments dans le tableau ça donne presque une boucle infinie >15min d'attente ...

Bon ce que je veux faire en globalité c’est la somme des éléments d’un tableau(n) de nombres réels
Et si la somme=6 (somme deux par deux[0]+[1] avec [2]+[3]...) alors s’arrêter.je dois ensuite comparer l’ensemble des sommes (CAD toutes les combinaisons possibles) et de sortir en fin de compte la combinaison la plus optimale par exemple avec :

1. Code :

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

   double[] t = new double[] { 1.9,0.1,0.9,4.1};

2. somme1 = 1.9+0.1+0.9+4,1
3. somme2 = 1.9+0.1+4,1+0.9
4. somme3 = 1.9+0.9+0.1+4,1
5. somme4 = 1.9+0.9+4,1+0.1
6. somme5 = 1.9+4,1+0.1+0.9
7. somme6 = 1.9+4,1+0.9+0.1
   
8. somme7 = 0.1+1.9+0.9+4,1
   ...

Les combinaisons que le programme est censé me retourné sont:
somme5 = 1.9+4,1+0.1+0.9
somme6 = 1.9+4,1+0.9+0.1
puisqu'il y'a eu qu'une somme pour avoir le 6 ...(1.9+4,1)…

J'ai divisé le problème en deux étapes:
1: généré toutes le combinaison possible
2:faire les sommes nécessaire
pour l'instant si j'arrive juste à avoir toutes les combinaisons possibles d'un tableau de réels ça sera bon ... pour les sommes (étape 2)je pense que ça pourrait se faire vite....

[worm83]

Yop,

Heureux que ça ai pu t'aider.

Si tu veux résoudre ta problématique, il va falloir que tu creuse beaucoup plus loin sur l’algorithmie. Déjà il y a des combinaison insensés que tu doit éliminer lors du premier parcourt, comme par exemple 24315.
C'est à dire que si la somme contenu dans le premier membre est déjà > à 6.

Mais on reste dans de la simplification basique, regarde plus en profondeur les algorithme de tris et de parcourt de structures, tu devrait trouver des chose plus évolués mathématiquement.

[unix27]

Décidément, le problème ne peut être résolu avec les tableau ou list(ça prend beaucoup de temps une fois qu'on donne une combinaison de 12 ou 16 éléments dans le tableau) je pense donc à implémenter un pg en langage C (utiliser des pointeurs... revenir aux années d'étude ) et ensuite l'appeler dans mon programme C# je pense qu'avec le C, l'optimisation pourra se faire mais bon je suis un peu perdu

[worm83]

Comme je te disais sur la réponse au dessus, bien entendu que cela va prendre du temps, mais le faire en C ne résoudra pas tes problèmes algorithmiques. Tu va gagner quoi 10% peut être 20% de perf au grand maximum, et encore si tu connait très bien le C, sinon tu ne gagnera rien !!! C'est sur que sur un traitement très long cela n'est pas négligeable, mais si ton traitement mettez 2h en C# tu va te retrouver avec un traitement qui dure tout de même 1h40...

C'est au niveau de l’algorithme qu'il faut te creuser la tête, il y a des algos de tri/parcourt plus ou moins performants suivant les besoins. Comme je te disait tu peux déjà supprimer toutes les valeur non possible lors de la génération ou du premier parcourt, sur 14 éléments si la condition est >6 tu peut quasiment supprimer 70% des valeurs à parcourir, ce qui est plus qu'énorme.
Va voir sur le forum algorithmique, il y a des gens très bon dans les domaine mathématique qui pourrais te donner de bonnes pistes.