Я немного скептически отношусь к тому, что есть решение. Ваша проблема, кажется, очень близка к той, которая была поставлена несколько лет назад в математической литературе, с приведенным здесь кратким описанием («Проблема обнаружения дубликатов», С. Камаль Абдали, 2003) , в котором используется обнаружение цикла - - идея заключается в следующем:
Если есть дубликат, существует число j между 1 и N, так что следующее приведет к бесконечному циклу:
x := j;
do
{
x := a[x];
}
while (x != j);
, поскольку перестановка состоит из одного или нескольких подмножеств S различных элементов s 0 , s 1 , ... s k-1 , где s j = a [s j-1 ] для всех j от 1 до k-1, а s 0 = a [s k-1 ], поэтому все элементы участвуют в циклах - один из дубликатов не будет частью такого подмножества.
например. если массив = [2, 1, 4, 6, 8 , 7, 9, 3, 8]
тогда элемент, выделенный жирным шрифтом в позиции 5, является дубликатом, поскольку все остальные элементы образуют циклы: {2 -> 1, 4 -> 6 -> 7 -> 9 -> 8 -> 3}. Тогда как массивы [2, 1, 4, 6, 5, 7, 9, 3, 8] и [2, 1, 4, 6, 3, 7, 9, 5, 8] являются действительными перестановками (с циклами {2 -> 1, 4 -> 6 -> 7 -> 9 -> 8 -> 3, 5} и {2 -> 1, 4 -> 6 -> 7 -> 9 -> 8 -> 5 -> 3} соответственно).
Абдали пытается найти дубликаты. В основном, следующий алгоритм (использующий алгоритм поиска цикла Флойда ) работает, если вы сталкиваетесь с одним из дубликатов:
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);
}
Сложность в том, что я не уверен, что ваша проблема в том виде, в котором она изложена, совпадает с той, которая указана в его статье, и я также не уверен, что описанный им метод работает в O (N) или использует фиксированное количество места. Потенциальным контрпримером является следующий массив:
[3, 4, 5, 6, 7, 8, 9, 10, ... N-10, N-9, N-8, N-7, N-2, N-5, N-5 , N-3, N-5, N-1, N, 1, 2]
, который в основном представляет собой единичную перестановку, сдвинутую на 2, при этом элементы [N-6, N-4 и N-2] заменены на [N-2, N-5, N-5]. Это имеет правильную сумму (не правильный продукт, но я не принимаю продукт в качестве возможного метода обнаружения, поскольку требования к пространству для вычисления N! С произвольной арифметикой точности равны O (N), что нарушает дух «фиксированного пространства памяти» требование), и если вы попытаетесь найти циклы, вы получите циклы {3 -> 5 -> 7 -> 9 -> ... N-7 -> N-5 -> N-1} и {4 -> 6 -> 8 -> ... N-10 -> N-8 -> N-2 -> N -> 2}. Проблема состоит в том, что может быть до N циклов (тождественная перестановка имеет N циклов), каждый из которых занимает до O (N), чтобы найти дубликат, и вам нужно каким-то образом отслеживать, какие циклы были отслежены, а какие - нет. Я скептически отношусь к тому, что это можно сделать за фиксированное количество места. Но, возможно, это так.
Это достаточно тяжелая проблема, которую стоит задать на mathoverflow.net (несмотря на то, что большую часть времени mathoverflow.net цитируется в stackoverflow, он предназначен для проблем, которые слишком просты)
edit: Я сделал спрашиваю о mathoverflow , там есть интересное обсуждение.