Discussion :

[TgRoX]

Bonjour,

Je bute depuis un moment sur l'algorithme qui me permettra de vérifier qu'un tableau 2D ne comporte que des chiffres uniques. J'ai eu un élan d'inspiration qui s'est vite estompé, je vous l'écris :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
   int chiffreTeste;
   for(int idLig = 0; idLig < TailleTableau2D; idLig++){
      chiffreTeste = idLig;
      for(int idCol = 0; idCol < TailleTableau2D; idCol++){
         if(idLig == idColà){
            continue;
         }
         if(tableau2D[idLig][idCol] == chiffreTest){
            cout << "Le tableau ne comporte pas que des valeurs uniques";
            break;
         }
      }
   }

Je me suis très vite rendu compte que ma variable chiffreTeste s'incrémentait à chaque tour de boucle et que par conséquent je n'effectue le test de chiffreTeste que sur une ligne et non sur le tableau entier.

Quelques conseils ?

Merci à vous

[cob59]

A ma connaissance on ne peut pas le faire directement avec la STL, mais c'est tout comme :

Code :

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

1
2
3
4
std::vector<int> vec ( tableau2D, tableau2D + TailleTableau2D );
std::sort( vec.begin(), vec.end() );
auto it = std::adjacent_find(vec.begin(), vec.end());
assert ( it == vec.end() );

Ou plus fourbe encore :

Code :

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

1
2
3
 
std::set<int> s( tableau2D, tableau2D + TailleTableau2D );
assert ( s.size() == TailleTableau2D );

Après, il y a sûrement plus optimal.

[Iradrille]

Code :

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

1
2
std::set<int> s( idLig, idLig + TailleTableau2D );
assert ( s.size() == TailleTableau2D );

Intuitivement je serai parti la dessus.

Les deux solutions que tu proposes sont en O(n * log n).

Code :

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

1
2
std::unordered_set<int> s( idLig, idLig + TailleTableau2D );
assert ( s.size() == TailleTableau2D );

Devrait être meilleur pour de grands tableaux (O (n)).
Pour de petits tableaux, il faudrait tester pour voir ce qui est le meilleur.

Si le tableau est déjà trié, alors un std::adjacent_find est clairement la meilleure solution (O(n)).

edit: à adapter si la mémoire du tableau 2D n'est pas consécutive. Il faut dans ce cas faire nbLignes (ou nbColonnes) insertions.

[Bousk]

Si tu es en C++11 tu as accès à
http://www.cplusplus.com/reference/algorithm/any_of/
http://www.cplusplus.com/reference/algorithm/all_of/
http://www.cplusplus.com/reference/algorithm/none_of/
Sinon, tu peux toujours ruser avec
http://www.cplusplus.com/reference/algorithm/find_if/

Si tu veux les réimplémenter c'est assez trivial, et tu peux par exemple utiliser l'exemple Python pour te rendre compte d'où mettre tes return en particulier
http://docs.python.org/2/library/functions.html#all
http://docs.python.org/2/library/functions.html#any

[TgRoX]

Bonjour,

Merci à vous pour vos réponses. J'ai entre temps réalisé un code qui semble fonctionner. Je vais étudier vos solutions un peu plus en détail car je n'ai pas encore le niveau nécessaire en c++ me permettant de les utiliser sans me poser de questions.

Pour ma part j'ai réalisé le code suivant (je ne recherche pas actuellement le code le plus optimisé, je cherche juste une solution qui marche, après quoi je vois si je peux faire quelque chose).

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
 
   if(ok){
 
      for(int iTest = 0; iTest < tailleCarre; iTest++){
         if(ok == false){
            break;
         }
         for(int jTest = 0; jTest < tailleCarre; jTest++){
            if(ok == false){
               break;
            }
            int chiffreTeste = carreMagique[iTest][jTest];
            for(int idLig = 0; idLig < tailleCarre; idLig++){
               if(ok == false){
                  break;
               }
               for(int idCol = 0; idCol < tailleCarre; idCol++){
                  if(idCol == jTest){
                     continue;
                  }
                  if(carreMagique[idLig][idCol] == chiffreTeste){
                     ok = false;
                     cout << "no !" << endl;
                     cout << carreMagique[idLig][idCol] << ' ' << chiffreTeste;
                     break;
                  }
               } 
            }
         }
      }   
   }

C'est très moche je vous l'accorde mais ça semble fonctionner. J'étudie de ce pas vos solutions !

[Bousk]

Tous ces if(ok) sont vraiment très moches et je comprends pas comment un esprit logique peut arriver à ça
alors qu'il suffit de placer un return false au milieu et un return true tout en bas.

[oodini]

Si tu stockais ton tableau 2D comme un tableau aplati, comme cela est souvent recommandé, tu pourrais utiliser std::unique_copy, puis comparer sa longueur avec celle du tableau original.

[Mat.M]

je suis d'accord avec Bousk c'est mal programmé
J'ai lu rapidement le code une fonction récursive serait peut-être plus appropriée