Discussion :

[Iradrille]

Hello,

On m'a récemment poser une question intéressante (pour une fois ) lors d'un entretien d'embauche :
Comment trouver des paires dans une liste de nombres et quelle est la complexité ?
Exemple : Dans la liste [1, 1, 1, 2, 4, 2, 2, 2]
Résultats : 3 paires (1, 2, 2), il y a 3 '1' -> on peut faire qu'une seule paire avec et 4 '2' -> 2 paires de '2'

Il y a une solution en O(n), on ajoute tous les nombres dans une hash map, et pour chaque nombre on divise le nombre d’occurrences par deux.
code (C++)

Code C++ :

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

1
2
3
4
5
6
7
8
9
10
std::unordered_map<int, int> hm;
auto nbs = {1, 1, 1, 2, 4, 2, 2, 2};
for(auto n: nbs) {
   ++hm[n];
}
int nbPairs = 0;
for(auto const& kv: hm) {
   nbPairs += (kv.second / 2);
}
std::cout << nbPairs << std::endl;

Puis, puis même question pour trouver des triplets.
Exemple : Dans la liste [1, 1, 1, 2, 4, 2, 2, 2]
Résultats : 2 triplets (1, 2), il y a 3 '1' -> 1 triplet; 4 '2' -> 1 triplet

Sur le coup, j'ai donné un algo en O(n²), qui en y réfléchissant n'a pas de sens : appliquer 2 fois l'algo précédent de manière imbriqué. La complexité en O(n²) que j'ai donné n'a pas choqué, l'algo par contre ... :p
Alors que le même algo en O(n) semble marcher :

Code C++ :

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

1
2
3
4
5
6
7
8
9
10
std::unordered_map<int, int> hm;
auto nbs = {1, 1, 1, 2, 4, 2, 2, 2};
for(auto n: nbs) {
   ++hm[n];
}
int nbPairs = 0;
for(auto const& kv: hm) {
   nbPairs += (kv.second / 3);
}
std::cout << nbPairs << std::endl;

Du coup ma question : Si une complexité en O(n²) ne choque pas, c'est qu'il y a un algo (probablement naïf); Mais j'arrive pas à trouver, une idée ?

[BufferBob]

salut,

un peu au pif, pour chaque valeur du tableau parcourir l'intégralité des valeurs restantes ?

[Iradrille]

Hum,

Ça pose pas de problème avec les triplets détectés plusieurs fois ?
Pour '2', il serait détecté 2 fois :
- Itération sur le 1er '2' : [4, 2, 2, 2] -> 1 paire, + 1 triplet
- Itération sur le 2eme '2' : [2, 2] -> 1 paire, + 1 triplet
=> 2 est compté comme 2 triplets.

Quelque chose comme ça marcherait ?

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
auto nbs = { 1, 1, 1, 2, 4, 2, 2, 2 };
int nbPairs = 0;
for (auto b = nbs.begin(), e = nbs.end(); b != e; ++b) {
	int n = 0;
	for (auto it = b + 1; it != e; ++it) {
		if (*it == *b) {
			++n;
		}
	}
	nbPairs += n / 2;
}
nbPairs /= 3;
++nbPairs;
std::cout << nbPairs << std::endl;

Division du nombre de pairs par 3 + 1 à la fin pour corriger la détection multiple. C'est correct ?

[Flodelarab]

Bonjour

J'ai rien compris.
Tu comptes les occurrences pour chaque motif et tu divises par 2 pour les couples, par 3 pour les triplets et par 6 pour les hexuplets.
Mais tu trouves ça trop simple. Alors tu viens ici demander plus compliqué ?

Euh ... pourquoi faire compliqué ?

Et puisqu'on se balance du code à la figure, tiens, prends

Code bash :

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
$ cat triplets.txt 
1
1
1
2
4
2
2
2 
$ awk '{a[$1]++;} END{for (i in a) print i,"->",int(a[i]/2),"couple(s)";}' triplets.txt                                                                                                              
4 -> 0 couple(s)
1 -> 1 couple(s)
2 -> 2 couple(s)
$ awk '{a[$1]++;} END{for (i in a) print i,"->",int(a[i]/3),"triplet(s)";}' triplets.txt                                                                                                             
4 -> 0 triplet(s)
1 -> 1 triplet(s)
2 -> 1 triplet(s)
$ awk '{a[$1]++;} END{for (i in a) print i,"->",int(a[i]/6),"hexuplet(s)";}' triplets.txt 
4 -> 0 hexuplet(s)
1 -> 0 hexuplet(s)
2 -> 0 hexuplet(s)

[Iradrille]

Mais tu trouves ça trop simple. Alors tu viens ici demander plus compliqué ?

Euh ... pourquoi faire compliqué ?

Par simple curiosité, une solution existe en O(n²), je voyais pas trop comment.

[BufferBob]

Ça pose pas de problème avec les triplets détectés plusieurs fois ?

ben l'idée c'est de "retirer" (pop ?) les valeurs du tableau au fur et à mesure, nécessairement

alors en C++ flemme mais en python (2.7) ça donnerait un truc comme ça très naïvement :

Code python :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# -*- coding: utf8 -*-
L = [1, 1, 1, 2, 4, 2, 2, 2]
paires = []
while True:
   current = L[0]
   L.pop(0)  # reste le tableau moins le premier élément qui sert de référence (current)
   for i in range(len(L)): # on parcourt tout le tableau restant donc
      if L[i] == current:
         L.pop(i)  # on retire du tableau l'élément appairé via son indice
         paires.append(current) # et on ajoute l'élément dont on a trouvé la paire dans une autre liste, pour affichage à la fin...
         print '- paire de %d trouvée, reste %s' % (current, str(L))
         break
   if len(L) < 2: # s'il reste 0 ou 1 élément dans le tableau on ne peut plus trouver de paire, donc on sort
      break
print '%d paires trouvées %s' % (len(paires), str(paires))

et le résultat :

Code :

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

1
2
3
4
- paire de 1 trouvée, reste [1, 2, 4, 2, 2, 2]
- paire de 2 trouvée, reste [4, 2, 2]
- paire de 2 trouvée, reste []
3 paires trouvées [1, 2, 2]

[tbc92]

Et pourquoi pas trier la liste ( avec un algo en n*log(n) )
Puis ensuite parcourir le résultat avec une boucle de ce genre

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
 
 
Procedure recherche(Ma_liste_triee  , n = 3 )        // n = 2 pour la recherche de couples , n=3 pour la recherche de triplets , etc.
t = taille(ma_liste_triee)
n_uplets = 0
i=0      // ou i = 1 si les éléments sont numérotés de 1 a t
tantque i +n-1 < t      
  si   ma_liste_triee[i] = ma_liste_triee[i+ n-1] alors 
      n_uplets ++
      i+= n
  sinon
      i++
  fin
fin
renvoyer n_uplets

[Trap D]

Si on est sur d'avoir des entiers, Pourquoi pas la méthode du tri du panier, un premier parcours pour trouver le plus grand, nombre, on cree le tableau , on parcours la liste pour compter les occurences opuis le tableau résultat. En gros O(3 * n)

[Iradrille]

@BufferBob : ça à l'air d'être ça, merci.

@tbc92 : c'est une idée, mais on est pas en O(n²).

@Trap D : Toujours pas en O(n²).

[DonQuiche]

Si on est sur d'avoir des entiers, Pourquoi pas la méthode du tri du panier, un premier parcours pour trouver le plus grand, nombre, on cree le tableau , on parcours la liste pour compter les occurences opuis le tableau résultat. En gros O(3 * n)

Le bucket sort ? Mais il faut en plus que les entiers soient petits. A ce compte-là pas besoin de trier, il suffit d'un tableau de compteurs.

Plus généralement on utilise un sac (multiset) : un ensemble dans lequel on compte le nombre d'instances de chaque élément. Comme toutes les structures communes basées sur des hashes, les temps d'accès sont en O(1).

Donc O(n).