Как определить, является ли массив перестановкой в ​​O (n)?

Question

Ввод: A только для чтения массив из N элементов, содержащих целочисленные значения от 1 до N (некоторые целочисленные значения могут появляться более одного раза!).И зона памяти размером фиксированный (10, 100, 1000 и т. Д. - не в зависимости от N).

Как сказать в O (n) если массив представляет собой перестановку?

- Чего я достиг к настоящему моменту (ответ доказал, что это не хорошо): -

1. Я использую ограниченную область памяти для хранения суммы и произведения массива.
2. Я сравниваю сумму с N * (N + 1) /2 и произведение с N!

Я знаю, что если условие (2) истинно, я может иметь перестановку.Мне интересно, есть ли способ доказать, что условие (2) достаточно, чтобы сказать, если у меня есть перестановка.Пока что я не понял этого ...

Answer 1

похоже на запрос поиска дубликата в массиве со стековой машиной.

кажется невозможным знать полную историю стека, пока вы извлекаете каждое число и имеете ограниченные знания о числах, которые были изъяты.

Answer 2

Хорошо, это не так, но, похоже, работает!

Я запустил эту тестовую программу (C #):

    static void Main(string[] args) {
        for (int j = 3; j < 100; j++) {
            int x = 0;
            for (int i = 1; i <= j; i++) {
                x ^= i;
            }
            Console.WriteLine("j: " + j + "\tx: " + x + "\tj%4: " + (j % 4));
        }
    }

Краткое объяснение: x - это результат всех XOR для одного списка, i - элемент в определенном списке, а j - размер списка. Поскольку все, что я делаю, это XOR, порядок элементов не имеет значения. Но я смотрю на то, как выглядят правильные перестановки при применении.

Если вы посмотрите на j% 4, вы можете переключиться на это значение и получить что-то вроде этого:

    bool IsPermutation = false;
    switch (j % 4) {
        case 0:
            IsPermutation = (x == j);
            break;
        case 1:
            IsPermutation = (x == 1);
            break;
        case 2:
            IsPermutation = (x == j + 1);
            break;
        case 3:
            IsPermutation = (x == 0);
            break;
    }

Теперь я признаю, что это, вероятно, требует некоторой тонкой настройки. Это не 100%, но это хороший простой способ начать. Возможно, с небольшими проверками, выполняемыми в цикле XOR, это может быть улучшено. Попробуйте начать где-то там.

Answer 3

Сумма и произведение не гарантируют правильного ответа, поскольку эти хэши подвержены коллизиям, т. Е. Разные входные данные могут потенциально давать идентичные результаты. Если вам нужен идеальный хеш, результат с одним числом, который фактически полностью описывает числовой состав массива, это может быть следующим.

Представьте, что для любого числа i в диапазоне [1, N] вы можете создать уникальное простое число P(i) (например, P(i) - это i-е простое число). Теперь все, что вам нужно сделать, это вычислить произведение всех P(i) для всех чисел в вашем массиве. Продукт будет полностью и однозначно описывать состав вашего массива, не обращая внимания на порядок значений в нем. Все, что вам нужно сделать, - это предварительно рассчитать «идеальное» значение (для перестановки) и сравнить его с результатом для данного ввода:)

Конечно, такой алгоритм не сразу удовлетворяет заявленным требованиям. Но в то же время он интуитивно слишком универсален: он позволяет обнаружить перестановку абсолютно любой числовой комбинации в массиве. В вашем случае вам нужно обнаружить перестановку определенной комбинации 1, 2, ..., N. Может быть, это можно как-то использовать для упрощения вещей ... Наверное, нет.

Answer 4

Во-первых, теоретико-информационная причина, почему это возможно. Мы можем тривиально проверить, что числа в массиве находятся в границах в O (N) времени и O (1) пространстве. Для указания любого такого массива внутренних чисел требуется N log N бит информации. Но для определения перестановки требуется примерно (N log N) - N бит информации (приближение Стирлинга). Таким образом, если бы мы могли получить N бит информации во время тестирования, мы могли бы знать ответ. Это тривиально сделать за N время (фактически, с M статическим пространством мы можем довольно легко получить log M информацию за шаг, и при особых обстоятельствах мы можем получить log N информацию).

С другой стороны, мы можем хранить только что-то вроде M log N битов информации в нашем статическом пространстве хранения, которое, вероятно, намного меньше, чем N, поэтому очень сильно зависит то, какая форма поверхности решения находится между "перестановка" и "не".

Я думаю, что это почти возможно, но не совсем, учитывая проблему установки. Я думаю, что «предполагается» использовать трюк с циклом (как в ссылке, упомянутой Юлианом), но ключевое предположение о наличии хвоста здесь не выполняется, потому что вы можете индексировать последний элемент массива с перестановкой.

Answer 5

В зависимости от того, сколько у вас места, относительно N, вы можете попробовать использовать хеширование и сегменты.

То есть перебираем весь список, хешируем каждый элемент и сохраняем его в корзине. Вам нужно будет найти способ уменьшить количество столкновений блоков из хэшей, но это решенная проблема.

Если элемент пытается войти в корзину с идентичным ему элементом, это перестановка.

Решением такого типа будет O (N), поскольку вы касаетесь каждого элемента только один раз.

Однако проблема заключается в том, больше ли пространство М, чем N, или нет. Если M> N, это решение будет хорошо, но если M

Answer 6

это перестановка, если и только если в массиве нет повторяющихся значений, должно быть легко проверить это в O (N)