Как сказать, является ли массив перестановкой в O (n)?
Вход: массив только для чтения элементов N, содержащих целочисленные значения от 1 до N (некоторые целочисленные значения могут появиться несколько раз!). И зона памяти фиксированного размера (10, 100, 1000 и т.д. - не в зависимости от N).
Как сказать в O (n), если массив представляет перестановку?
- Чего я достиг до сих пор (ответ доказал, что это не было хорошо):-
- Я использую область ограниченной памяти для хранения суммы и продукта массива.
- Я сравниваю сумму с N* (N+1)/2 и продукт с N!
Я знаю что, если условие (2) верно, что у меня могла бы быть перестановка. Я задаюсь вопросом, существует ли способ доказать, что условие (2) достаточно, чтобы сказать, есть ли у меня перестановка. До сих пор я не понял это...
10 ответов
Я очень скептически отношусь к тому, что решение существует. Ваша проблема кажется очень близкой к проблеме, поставленной несколько лет назад в математической литературе, с кратким изложением, приведенным здесь ("The Duplicate Detection Problem", S. Kamal Abdali, 2003), которая использует обнаружение цикла - идея следующая:
Если есть дубликат, то существует число j между 1 и N такое, что следующее приведет к бесконечному циклу:
x := j;
do
{
x := a[x];
}
while (x != j);
поскольку перестановка состоит из одного или более подмножеств S различных элементов s0, s1, ... ... sk-1, где sj = a[sj-1] для всех j от 1 до k-1, и s0 = a[sk-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 } соответственно). В
Abdali рассматривается способ поиска дубликатов. В основном следующий алгоритм (использующий Floyd's cycle-finding algorithm) работает, если вы случайно наткнулись на один из дубликатов:
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, там есть интересное обсуждение.
Во-первых, теоретико-информационная причина, почему это возможно. Мы можем тривиально проверить, что числа в массиве находятся в пределах времени O (N) и пространства O (1). Чтобы указать любой такой массив входящих чисел, требуется N log N битов информации. Но для определения перестановки требуется приблизительно (N log N) - N бит информации (приближение Стирлинга). Таким образом, если мы сможем получить N бит информации во время тестирования, мы сможем узнать ответ. Это тривиально сделать за N времени (на самом деле, в статическом пространстве M мы можем довольно легко получить информацию log M за шаг, и при особых обстоятельствах мы может получить информацию журнала N ).
С другой стороны, мы можем хранить только что-то вроде M log N битов информации в нашем статическом пространстве хранения, что предположительно намного меньше, чем N , поэтому это зависит от какова форма поверхности принятия решения между «перестановкой» и «не».
Я думаю, что это почти возможно, но не совсем с учетом постановки задачи. Я думаю, что «предполагается» использовать трюк с циклическим перемещением (как в ссылке, которую упомянул Юлиан), но ключевое предположение о наличии хвоста здесь не выполняется, потому что вы можете проиндексировать последний элемент массива с перестановкой.
Я не знаю, как это сделать за O(N), и даже можно ли это сделать за O(N). Я знаю, что это можно сделать за O(N log N), если вы (используете соответствующую) сортировку и сравнение.
Тем не менее, есть много O(N) методов, которые можно использовать, чтобы показать, что одно НЕ является перестановкой другого.
- Проверьте длину. Если она неравна, очевидно, что это не перестановка.
- Создайте XOR-отпечаток. Если значение всех элементов XOR'ed вместе не совпадает, то это не может быть перестановкой. Однако совпадение будет неубедительным.
- Найдите сумму всех элементов. Хотя результат может переполниться, это не должно вызывать беспокойства при сопоставлении этого "отпечатка пальца". Однако если бы вы делали контрольную сумму, которая включает умножение, то переполнение стало бы проблемой.
Надеюсь, это поможет.
Это не будет работать из-за того, что сложность задается как функция от N, а не от M, подразумевая, что N >> M
Это была моя попытка, но чтобы фильтр Блюма был полезен, вам нужно большое M, и в этот момент вы можете использовать простое переключение битов для чего-то вроде целых чисел
http://en.wikipedia.org/wiki/Bloom_filter
Для каждого элемента в массиве Выполнить k хэш-функций Проверяем на включение в фильтр цветения Если он там есть, есть вероятность, что вы видели этот элемент раньше. Если нет, добавьте его
Когда вы закончите, вы можете сравнить его с результатами массива 1...N по порядку, так как это будет стоить вам еще N.
Теперь, если я не сделал достаточно оговорок. Это не 100%, или даже близко, так как вы указали сложность в N, что подразумевает, что N >> M, так что в принципе это не будет работать так, как вы указали.
BTW, коэффициент ложных срабатываний для отдельного элемента должен быть равен e = 2^(-m/(n*sqrt(2)))
Что, пошарив вокруг, даст вам представление о том, насколько большим должно быть M, чтобы быть приемлемым.
Я сомневаюсь, что вы сможете это доказать;)
(1, 2, 4, 4, 4, 5, 7, 9, 9)
Я думаю, что в более общем плане эта проблема не решается путем обработки чисел по порядку. Предположим, вы обрабатываете элементы по порядку и находитесь на половине массива. Теперь состояние вашей программы должно каким-то образом отражать, какие числа вы уже встречали. Для этого требуется как минимум O (n) бит.
Это невозможно сделать в пространстве O(1), по крайней мере, с помощью односканового алгоритма.
Доказательство
Предположим, что вы обработали N/2 из N элементов. Если предположить, что последовательность является перестановкой, то, учитывая состояние алгоритма, вы должны быть в состоянии определить набор из N/2 оставшихся элементов. Если вы не можете определить оставшиеся элементы, то алгоритм можно обмануть, повторив некоторые из старых элементов.
Существует N вариантов N/2 возможных оставшихся наборов. Каждое из них должно быть представлено отдельным внутренним состоянием алгоритма, потому что иначе вы не сможете вычислить оставшиеся элементы. Однако для хранения X состояний требуется логарифмическое пространство, поэтому для хранения N состояний из N выбираем N/2 требуется пространство BigTheta(log(N выбираем N/2)). Эта величина растет с N, и поэтому внутреннее состояние алгоритма не может уместиться в пространстве O(1).
Более формальное доказательство
Вы хотите создать программу P, которая, учитывая конечные N/2 элементов и внутреннее состояние линейно-временно-константно-пространственного алгоритма после обработки N/2 элементов, определяет, является ли вся последовательность перестановкой 1...N. Для этой вторичной программы нет ограничений по времени или пространству.
Предполагая, что P существует, мы можем создать программу Q, принимающую только внутреннее состояние алгоритма linear-time-constant-space, которая определяет необходимые конечные N/2 элементов последовательности (если она была перестановкой). Q работает, передавая P все возможные конечные N/2 элементов и возвращая набор, для которого P возвращает true.
Однако, поскольку у Q есть N вариантов N/2 возможных выходов, у него должно быть по крайней мере N вариантов N/2 возможных входов. Это означает, что внутреннее состояние оригинального алгоритма должно хранить по крайней мере N choose N/2 состояний, что требует BigTheta(log N choose N/2), что больше, чем постоянный размер.
Поэтому оригинальный алгоритм, который действительно имеет временные и пространственные границы, также не может работать правильно, если он имеет внутреннее состояние постоянного размера.
[Я думаю, эту идею можно обобщить, но думать - не значит доказывать]
Последствия
BigTheta(log(N choose N/2)) равна BigTheta(N). Поэтому использование булевого массива и тиканье значений по мере их появления является (вероятно) оптимальным с точки зрения пространства, и оптимальным с точки зрения времени, поскольку это занимает линейное время.
В зависимости от того, сколько места у вас есть относительно N, вы можете попробовать использовать хеширование и сегменты.
То есть перебирать весь список, хешировать каждый элемент и сохранять его в корзине. Вам нужно будет найти способ уменьшить количество столкновений ведер с хешами, но это решенная проблема.
Если элемент пытается попасть в корзину с идентичным ему элементом, это перестановка.
Этот тип решения будет O (N), поскольку вы касаетесь каждого элемента только один раз.
Однако проблема заключается в том, больше ли пространство M, чем N, или нет. Если M> N, это решение подойдет, но если M
это перестановка тогда и только тогда, когда в массиве нет повторяющихся значений, это должно быть легко проверить в O (N)
Вы могли бы сделать это в случайном O (n) пространстве времени и констант, вычислив сумму (x_i) и произведение (x_i) по модулю набора различных случайно выбранных констант C размера O (n) . Это в основном помогает решить проблему, заключающуюся в том, что product (x_i) становится слишком большим.
Тем не менее, остается много открытых вопросов, например, if sum (x_i) = N (N + 1) / 2 и product (x_i) = N! являются достаточными условиями, чтобы гарантировать перестановку, и какова вероятность того, что неперестановка сгенерирует ложное срабатывание (я надеюсь ~ 1 / C для каждого C, который вы пытаетесь, но, возможно, нет).
Сумма и произведение не гарантируют правильного ответа, так как эти хэши подвержены конфликтам, т.е. разные входные данные могут потенциально давать идентичные результаты. Если вам нужен идеальный хеш, результат с одним числом, который действительно полностью описывает числовой состав массива, это может быть следующее.
Представьте, что для любого числа i в диапазоне [1, N] вы можете создать уникальное простое число P (i) (например, P (i) - i-е простое число). Теперь все, что вам нужно сделать, это вычислить произведение всех P (i) для всех чисел в вашем массиве. Продукт полностью и однозначно опишет состав вашего массива, не обращая внимания на порядок значений в нем. Все, что вам нужно сделать, это предварительно вычислить «идеальное» значение (для перестановки) и сравнить его с результатом для данного входа :)
Конечно, подобный алгоритм не сразу удовлетворяет заявленным требованиям. Но в то же время он интуитивно слишком универсален: он позволяет обнаруживать перестановку абсолютно любой числовой комбинации в массиве. В вашем случае вам нужно обнаружить перестановку определенной комбинации 1, 2, ..., N . Может быть, это как-то можно использовать для упрощения ... Наверное, нет.