Je suis très légèrement sceptique quant à l'existence d'une solution. Votre problème semble être très proche d'un problème posé il y a plusieurs années dans la littérature mathématique, avec un résumé donné ici ("The Duplicate Detection Problem", S. Kamal Abdali, 2003) qui utilise la détection de cycle, l'idée étant la suivante :
S'il y a un doublon, il existe un numéro j entre 1 et N tel que ce qui suit conduirait à une boucle infinie :
x := j;
do
{
x := a[x];
}
while (x != j);
car une permutation consiste en un ou plusieurs sous-ensembles S d'éléments distincts s 0 , s 1 , ... s k-1 où s j \= a[s j-1 ] pour tous les j entre 1 et k-1, et s 0 \= a[s k-1 ], donc tous les éléments sont impliqués dans les cycles -- l'un des doublons ne ferait pas partie d'un tel sous-ensemble.
Par exemple, si le tableau = [2, 1, 4, 6, 8 , 7, 9, 3, 8]
alors l'élément en gras en position 5 est un doublon car tous les autres éléments forment des cycles : { 2 -> 1, 4 -> 6 -> 7 -> 9 -> 8 -> 3}. Alors que les tableaux [2, 1, 4, 6, 5, 7, 9, 3, 8] et [2, 1, 4, 6, 3, 7, 9, 5, 8] sont des permutations valides (avec les cycles { 2 -> 1, 4 -> 6 -> 7 -> 9 -> 8 -> 3, 5 } et { 2 -> 1, 4 -> 6 -> 7 -> 9 -> 8 -> 5 -> 3 } respectivement).
Abdali explique comment trouver les doublons. En gros, l'algorithme suivant (utilisant L'algorithme de recherche de cycle de Floyd ) fonctionne si vous tombez sur l'un des doublons en question :
function is_duplicate(a, N, j)
{
/* assume we've already scanned the array to make sure all elements
are integers between 1 and N */
x1 := j;
x2 := j;
do
{
x1 := a[x1];
x2 := a[x2];
x2 := a[x2];
} while (x1 != x2);
/* stops when it finds a cycle; x2 has gone around it twice,
x1 has gone around it once.
If j is part of that cycle, both will be equal to j. */
return (x1 != j);
}
La difficulté est que je ne suis pas sûr que votre problème tel qu'il est énoncé corresponde à celui de son article, et je ne suis pas non plus sûr que la méthode qu'il décrit fonctionne en O(N) ou utilise une quantité fixe d'espace. Un contre-exemple potentiel est le tableau suivant :
[3, 4, 5, 6, 7, 8, 9, 10, ... N-10, N-9, N-8, N-7, N-2, N-5, N-3, N-5, N-1, N, 1, 2]
qui est en fait la permutation d'identité décalée de 2, avec les éléments [N-6, N-4 et N-2] remplacés par [N-2, N-5, N-5]. La somme est correcte (mais pas le produit correct, mais je rejette l'idée de prendre le produit comme méthode de détection possible, car l'espace nécessaire pour calculer N ! avec une précision arithmétique arbitraire est de O(N), ce qui viole l'esprit de l'exigence d'un "espace mémoire fixe"), et si vous essayez de trouver des cycles, vous obtiendrez les cycles { 3 -> 5 -> 7 -> 9 -> .... N-7 -> N-5 -> N-1 } et { 4 -> 6 -> 8 -> ... N-10 -> N-8 -> N-2 -> N -> 2}. Le problème est qu'il pourrait y avoir jusqu'à N cycles (la permutation d'identité a N cycles), chacun prenant jusqu'à O(N) pour trouver un duplicata, et vous devez garder la trace d'une manière ou d'une autre des cycles qui ont été tracés et de ceux qui ne l'ont pas été. Je suis sceptique quant à la possibilité de faire cela dans une quantité fixe d'espace. Mais c'est peut-être le cas.
C'est un problème suffisamment important pour qu'il vaille la peine de le poser sur le site de la Commission. mathoverflow.net (malgré le fait que la plupart du temps mathoverflow.net est cité sur stackoverflow c'est pour des problèmes qui sont trop faciles)
éditer : Je l'ai fait. demander sur mathoverflow il y a une discussion intéressante là-dessus.
