Discussion :

[corky813]

Bonjour,

Je travaille sur une génération de matrice (considérée comme tableau à 2 dim) de test dont les dimensions évolue, en C++.
Le nombre de colonnes est N et le nombre de lignes varie de 1 à N-1
Mon but est de mettre un et un seul des éléments de chaque ligne à 1, sans doublons et sans permutations et de créer toutes les combinaisons possibles de matrices de tailles 1*N à N-1*N, vérifiant ces conditions.

Par exemple pour n=3 mes résultats seraient :

1 0 0

0 1 0

0 0 1

1 0 0
0 1 0

1 0 0
0 0 1

0 1 0
0 0 1

Une manière évidente de faire cela aurait été d'utiliser des boucles imbriquées mais N peut changer donc cela ne marcherait pas.
J'essaye de trouver une manière récursive de faire cela mais je n'y arrive pas et c'est pour cela que je sollicite votre aide.

Merci d'avance.

[prgasp77]

Bonjour,
d'une part, que veux-tu dire par « sans doublons et sans permutations » ?
d'autre part, en quoi le fait que « N peut changer » empêche la simple itération ?

Cdlt,

[corky813]

Bonjour,

Par sans doublon, je veux dire que je ne met pas 2 fois 1 sur la même colonne et par sans permutation je veux dire que par exemple

1 0 0
0 1 0

et

0 1 0
1 0 0

représentent le même cas donc l'un des 2 est inutile.

Le fait que N peut changer implique que je ne peut pas imbriquer N boucles "en dur" dans le code étant donner que ce nombre n'est pas fixe.

[Nebulix]

tu peux coder chaque ligne de ta matrice par la position du "1". Ton exemple devient
1
2
3
12
13
23
....

[corky813]

C'est pas faux, mais dans ce cas je me retrouve quasiment avec le même problème, excepté que maintenant il me faut trouver toutes les combinaisons de longueur 1 à N-1 de N entiers, sans doublons ni permutations.

[Acrim]

Si tu utilises le codage de Nebulix

sans doublons, ni permutations.

Je pense que ca se traduit par : la valeur de la ligne i doit être strictement inférieur à la valeur de la ligne j, pour i < j.

[prgasp77]

Salut, avec du papier et un crayon on arrive à des choses intéressantes. Il existe une solution récursive, elle est assez claire mais les cas critiques sont assez lourds à traiter.

Voici ce que je propose. Soit N un entier donné. Pour chaque n compris entre 1 et N-1 nous allons lister les matrices possibles de n lignes et N colonnes. Pour cela, on part d'un tableau de n entiers représentant la position du 1 sur la colonne. Par exemple, pour N=6, {5, 2, 1} représente la matrice

0 0 0 0 0 1
0 0 1 0 0 0
0 1 0 0 0 0

On part donc de {N-1, N-2, ..., N-n} et on crée un nouveau tableau suivant cette règle :

Code C :

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

1
2
3
4
5
6
7
8
9
10
11
int dec(int *arr, int size, int step) {
   if(step ==  arr[size-1])
      return 1;
   if(arr[size-1]>step)
      arr[size-1]--;
   else {
      dec(arr, size-1, step+1);
      arr[size-1] = arr[size-2]-1;
   }
   return 0;
}

Code C :

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

1
2
3
4
do {
   matrix m = create_matrix_from_array(arr, N, n);
   add_matrix_to_matrixes(m);
} while(0 == dec(arr, n, 0))

Cordialement,

[corky813]

Merci prgasp77

J'ai adapté ton code pour avoir les matrices dans l'ordre "croissant" (voir l'exemple de Nebulix).
J'ai gardé la même fonction dec
Voici mon code

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
for(int i = 1; i < N; i++)
    {
        int *arr;
        arr = new int [i];
        for(int j = 0; j < i; j++)
        {
            arr[j] = N-j-1;
        }
        do {
            double **p = matrix(i,N);
            //double **q = matrix(i,1);
            //double **omega;
            zero_matrix(p,i,N);
            //zero_matrix(omega,i,i);
            for(int j = 0; j < i; j++)
            {
                p[j][(N-1)-arr[j]] = 1.0;
            }
 
             for(int j = 0; j < i; m++)
              {
                  delete [] p[j];
              }
            }while(0 == dec(arr, i, 0));
        delete[] arr;
 
       }

En l'appliquant pour N=3 j'obtiens les matrices suivantes :
1 0 0

0 1 0

0 0 1

1 0 0
0 1 0

1 0 0
0 0 1

Mais la dernière matrice qui devrait être
0 1 0
0 0 1

n'est pas générée et je n'arrive pas à voir pourquoi.

[Alikendarfen]

Je me trompe ou bien ce qu'on cherche est simplement les combinaisons C(np) ??

Pour reprendre les exemples de Corky :

100, 010, 001 = C(3,1) = {1, 2, 3}

[100,010], [100,001], [010,001] = C(3,2) = { [1,2], [1,3], [2,3] }

... une fois qu'on a ces combinaisons en nombres, les traduire en tableau est assez simple.

Code C# pour obtenir C(n,p) (chaque résultat est traité par la continuation 'action') :

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
 
        public static void Combinaisons<T>( this List<T> list, int p, Action<IEnumerable<T>> action )
        {
            Combinaisons( list, p, new T[p], 0, action );
        }
 
        static void Combinaisons<T>( List<T> list, int p, T[] result, int from, Action<IEnumerable<T>> action )
        {
            if ( p == 0 )
                action( result );
            else
            {
                int levelIndex = result.Length - p;
                int limit = list.Count - p + 1;
 
                for ( int i = from ; i < limit ; i++ )
                {
                    result[levelIndex] = list[i];
 
                    Combinaisons( list, p - 1, result, i + 1, action );
                }
            }
        }

Pour l'appel :

Code :

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

1
2
 
{1,2,3}.Combinaisons( i, CreerTableau );

Après on boucle sur i = 1 à n-1...

[corky813]

Et en C++ ça donnerait quoi?

[Alikendarfen]

Puréeeee... en C++, ça va être approximatif de ma part, mais ça donne qq chose comme ça :

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
 
        void Combinaisons( int *list, int n, int p, Continuation &c )
        {
            Combinaisons( list, n, p, p, new int[p], 0, c );
        }
        void Combinaisons( int *list, int n, int p0, int p, int *result, int level, Continuation &c )
        {
            if ( p == 0 )
            {
                c.CreerTableau( result, n, p0 );
            }
            else
            {
                int levelIndex = p0 - p;
                int limit = n - p + 1;
 
                for ( int i = 0 ; i < limit ; i++ )
                {
                    result[levelIndex] = list[i];
 
                    Combinaisons( list, n, p0, p - 1, result, i + 1, c );
                }
            }
        }

Mais là, j'ai pas les outils pour tester.

Il faut toujours créer int *list avec N valeurs de 1 à N.
Et boucler sur Combinaisons avec p de 1 à N-1.

Après la classe 'Continuation' implémente une méthode 'CreerTableau' pour faire chacun de tes tableaux en 0/1.

[corky813]

OK merci Alikendarfen je vais essayer de regarder ça.

[Alikendarfen]

Par contre, je n'ai pas réussi à comprendre le raisonnement de prgasp (avec sa fonction 'dec'), ni du coup pourquoi ta dernière matrice n'est pas générée...

[corky813]

Je n'ai pas forcément tout compris non plus.
J'ai essayer de jouer avec les indices et compagnie que ce soit dans la fonction dec ou ma boucle for mais je n'ai jamais réussi à générer cette dernière matrice.

[prgasp77]

J'ai peut être commis une erreur sur la condition d'arrêt de la fonction dec. Celle-ci termine toute l'itération lorsqu'elle renvoie 1, peut être ais-je été trop stricte à ce propos (ligne 2) if(step == arr[size-1]). Le test d'égalité pourrait être remplacé par un test d'infériorité, qu'est-ce que ça donne dans ce cas ?

Cdlt,

[corky813]

Bonjour,

Si je met un test d'infériorité à la ligne 2 le programme me renvoie seulement :
1 0 0

et

1 0 0
0 1 0

[prgasp77]

Oui en effet, je suis fatigué ...

Code C :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
int dec(int *arr, int size, int step) {
   if(0==size)
      return 1;
   if(arr[size-1]>step) {
      arr[size-1]--;
      return 0;
   }
   if(0 == dec(arr, size-1, step+1)) {
      arr[size-1] = arr[size-2]-1;
      return 0;
   }
   return 1;
}

[corky813]

Ok, la dernière matrice est générée avec cette fonction.
Je vais tester sur d'autres valeurs pour voir.

Merci

[prgasp77]

Le cas échéant, pense à cliquer sur le bouton .