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

Ответ 1

Я очень скептически отношусь к тому, что есть решение. Ваша проблема, кажется, очень близка к тому, что было несколько лет назад в математической литературе, приведенное здесь резюме ( "Проблема дублирования обнаружения" , С. Камаль Abdali, 2003), в котором используется обнаружение цикла - идея заключается в следующем:

Если существует дубликат, существует число j между 1 и N, так что следующее приведет к бесконечному циклу:

x := j;
do
{
   x := a[x];
}
while (x != j);

потому что перестановка состоит из одного или нескольких подмножеств S различных элементов s ₀, s ₁,... s _k-1 где s _j= a [s _j-1] для всех j между 1 и k-1 и s ₀= 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} соответственно).

Абдали пытается найти дубликаты. В принципе, следующий алгоритм (используя алгоритм поиска циклов Floyd) работает, если вы попадаете на один из дубликатов, о котором идет речь:

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, там есть интересная дискуссия.

Ответ 2

Это невозможно сделать в O (1) пространстве, по крайней мере, с помощью алгоритма с одним сканированием.

Proof

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

N выбирает N/2 возможных оставшихся наборов. Каждый из них должен быть представлен отдельным внутренним состоянием алгоритма, поскольку в противном случае вы не смогли бы определить оставшиеся элементы. Тем не менее, для хранения X состояний требуется логарифмическое пространство, поэтому требуется BigTta (log (N выбрать N/2)) пространство для хранения N выбирает N/2 состояния. Эти значения растут с N, и поэтому внутреннее состояние алгоритма не может быть помещено в O (1) пространство.

Более формальное доказательство

Вы хотите создать программу P, которая, учитывая конечные элементы N/2 и внутреннее состояние алгоритма линейного времени-постоянного пространства после обработки N/2 элементов, определяет, является ли вся последовательность перестановкой of 1..N. В этой вторичной программе нет времени или пространства.

Предполагая, что существует P, мы можем создать программу Q, используя только внутреннее состояние алгоритма линейного времени-константы, определяющего необходимые конечные N/2 элементы последовательности (если это была перестановка). Q работает путем передачи P всех возможных окончательных элементов N/2 и возврата набора, для которого P возвращает true.

Однако, поскольку Q имеет N, выбирайте N/2 возможных выхода, он должен иметь по крайней мере N выбор N/2 возможных входов. Это означает, что внутреннее состояние исходного алгоритма должно хранить, по крайней мере, N, выбрать N/2 состояния, требуя BigTheta (log N выбрать N/2), который больше, чем постоянный.

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

[Я думаю, что эту идею можно обобщить, но мышление не доказывает.]

Последствия

BigTheta (log (N выбирает N/2)) равна BigTheta (N). Поэтому просто использование логического массива и тикающих значений по мере их возникновения (возможно) является оптимальным по пространству и оптимальным по времени, так как оно требует линейного времени.

Ответ 3

Я сомневаюсь, что вы сможете это доказать;)

  (1, 2, 4, 4, 4, 5, 7, 9, 9)

Я думаю, что в более общем плане эта проблема не разрешима путем обработки чисел по порядку. Предположим, что вы обрабатываете элементы по порядку, и вы находитесь на полпути массива. Теперь состояние вашей программы должно каким-то образом отразить, какие числа вы столкнулись до сих пор. Для этого требуется хранить не менее O (n) битов.

Ответ 4

Это не будет работать из-за сложности, заданной как функция от N, а не от M, подразумевая, что N → M

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

http://en.wikipedia.org/wiki/Bloom_filter

Для каждого элемента массива Запустите k хэш-функции Проверьте наличие в цветном фильтре Если он есть, есть вероятность, что вы видели элемент раньше Если это не так, добавьте его

Когда вы закончите, вы можете сравнить его с результатами массива 1..N по порядку, так как это будет стоить вам только еще N.

Теперь, если я не поставил достаточно оговорок. Это не 100% или даже близко, поскольку вы указали сложность в N, что означает, что N → M, поэтому в принципе это не сработает, как вы указали он.

Кстати, ложная положительная ставка для отдельного товара должна быть e = 2 ^ (- m/(n * sqrt (2)))

Какие обезьяны вокруг вас дадут вам представление о том, насколько большой М должен быть приемлемым.

Ответ 5

Я не знаю, как это сделать в O (N), или даже если это можно сделать в O (N). Я знаю, что это можно сделать в O (N log N), если вы (используйте соответствующий) сортируете и сравниваете.

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

• Проверьте длину. Если неравный, очевидно, не перестановка.
• Создайте отпечаток XOR. Если значение всех элементов XOR'ed вместе не совпадает, то это не может быть перестановкой. Однако совпадение было бы неубедительным.
• Найдите сумму всех элементов. Хотя результат может переполняться, это не должно беспокоиться при сопоставлении этого "отпечатка пальца". Если, однако, вы сделали контрольную сумму, которая включала бы перемножение, а затем переполнение было бы проблемой.

Надеюсь, что это поможет.

Ответ 6

Возможно, вы сможете сделать это в рандомизированном O(n) времени и постоянном пространстве, вычислив sum(x_i) и product(x_i) по модулю связку различных случайно выбранных констант C размером O(n). Это в основном заставляет вас решить проблему, которая product(x_i) становится слишком большой.

Ответ 7

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

Ответ 8

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

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

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

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

Однако проблема заключается в том, является ли пространство M больше N или нет. Если M > N, это решение будет хорошо, но если M < N, то вы не сможете решить проблему со 100% -ной точностью.

Ответ 9

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

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

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

Ответ 10

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

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

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

Ответ 11

Хорошо, это другое, но, похоже, оно работает!

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

    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 для одного списка, я - элемент в определенном списке, 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, это может быть улучшено. Попробуйте начать где-то там.

Ответ 12

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

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

Ответ 13

Здесь proof это невозможно:

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

Если у вас есть нет структурированное представление состояния проблемы до сих пор, то вы сводились к выполнению линейного поиска по всему предыдущему входу для ячейки EACH. Легко видеть, как это оставляет вам алгоритм с квадратичным временем.

Теперь предположим через какую-то умную структуру данных, что вы действительно знаете, какое число вы ожидаете увидеть последним. Тогда, конечно, что знание берет, по крайней мере, достаточно битов, чтобы сохранить номер, который вы ищете - возможно, одну ячейку памяти? Но есть второе и последнее число и второстепенная суб-проблема: тогда вы должны также представлять собой набор из двух возможных чисел, которые еще не видны. Это, конечно, требует большего объема памяти, чем кодирование только для одного оставшегося числа. По прогрессии подобных аргументов размер государства должен расти с размером проблемы, если только вы не согласны с наихудшим случаем с квадратичным временем.

Это компромисс между временным пространством. Вы можете иметь квадратичное время и постоянное пространство, или линейное время и линейное пространство. Вы не можете иметь линейное время и постоянное пространство.

Ответ 14

Проверьте следующее решение. Он использует O (1) дополнительное пространство. Он изменяет массив во время процесса проверки, но возвращает его обратно в исходное состояние в конце.

Идея такова:

• Проверьте, нет ли какого-либо из элементов вне диапазона [1, n] = > O (n).

• Перейдите по порядковым номерам (все они теперь находятся в диапазоне [1, n]) и для каждого числа x (например, 3):

  • перейдите в x-я ячейку (например, [3]), если она отрицательная, то кто-то уже посетил ее перед вами = > Не перестановка. В противном случае (a [3] положительно), умножьте его на -1. = > O (n).
• Перейдите по массиву и отрицайте все отрицательные числа.

Таким образом, мы точно знаем, что все элементы находятся в диапазоне [1, n] и что нет дубликатов = > Массив является перестановкой.

int is_permutation_linear(int a[], int n) {
    int i, is_permutation = 1;

    // Step 1.
    for (i = 0; i < n; ++i) {
        if (a[i] < 1 || a[i] > n) {
            return 0;
        }
    }

    // Step 2.
    for (i = 0; i < n; ++i) {
        if (a[abs(a[i]) - 1] < 0) {
            is_permutation = 0;
            break;
        }
        a[i] *= -1;
    }

    // Step 3.
    for (i = 0; i < n; ++i) {
        if (a[i] < 0) {
            a[i] *= -1;
        }
    }

    return is_permutation;
}

Вот полная программа, которая его тестирует:

/*
 * is_permutation_linear.c
 *
 *  Created on: Dec 27, 2011
 *      Author: Anis
 */

#include <stdio.h>

int abs(int x) {
    return x >= 0 ? x : -x;
}

int is_permutation_linear(int a[], int n) {
    int i, is_permutation = 1;

    for (i = 0; i < n; ++i) {
        if (a[i] < 1 || a[i] > n) {
            return 0;
        }
    }

    for (i = 0; i < n; ++i) {
        if (a[abs(a[i]) - 1] < 0) {
            is_permutation = 0;
            break;
        }
        a[abs(a[i]) - 1] *= -1;
    }

    for (i = 0; i < n; ++i) {
        if (a[i] < 0) {
            a[i] *= -1;
        }
    }

    return is_permutation;
}

void print_array(int a[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        printf("%2d ", a[i]);
    }
}

int main() {
    int arrays[9][8] = { { 1, 2, 3, 4, 5, 6, 7, 8 },
                         { 8, 6, 7, 2, 5, 4, 1, 3 },
                         { 0, 1, 2, 3, 4, 5, 6, 7 },
                         { 1, 1, 2, 3, 4, 5, 6, 7 },
                         { 8, 7, 6, 5, 4, 3, 2, 1 },
                         { 3, 5, 1, 6, 8, 4, 7, 2 },
                         { 8, 3, 2, 1, 4, 5, 6, 7 },
                         { 1, 1, 1, 1, 1, 1, 1, 1 },
                         { 1, 8, 4, 2, 1, 3, 5, 6 } };
    int i;

    for (i = 0; i < 9; i++) {
        printf("array: ");
        print_array(arrays[i], 8);
        printf("is %spermutation.\n",
               is_permutation_linear(arrays[i], 8) ? "" : "not ");
        printf("after: ");
        print_array(arrays[i], 8);
        printf("\n\n");

    }

    return 0;
}

И его вывод:

array:  1  2  3  4  5  6  7  8 is permutation.
after:  1  2  3  4  5  6  7  8 

array:  8  6  7  2  5  4  1  3 is permutation.
after:  8  6  7  2  5  4  1  3 

array:  0  1  2  3  4  5  6  7 is not permutation.
after:  0  1  2  3  4  5  6  7 

array:  1  1  2  3  4  5  6  7 is not permutation.
after:  1  1  2  3  4  5  6  7 

array:  8  7  6  5  4  3  2  1 is permutation.
after:  8  7  6  5  4  3  2  1 

array:  3  5  1  6  8  4  7  2 is permutation.
after:  3  5  1  6  8  4  7  2 

array:  8  3  2  1  4  5  6  7 is permutation.
after:  8  3  2  1  4  5  6  7 

array:  1  1  1  1  1  1  1  1 is not permutation.
after:  1  1  1  1  1  1  1  1 

array:  1  8  4  2  1  3  5  6 is not permutation.
after:  1  8  4  2  1  3  5  6 

Ответ 15

Решение Java ниже отвечает на вопрос частично. Сложность по времени я считаю O (n). (Это убеждение основано на том, что решение не содержит вложенных циклов.) О памяти - не уверен. Вопрос появляется сначала по соответствующим запросам в google, поэтому он может быть полезен для кого-то.

public static boolean isPermutation(int[] array) {   
    boolean result = true;
    array = removeDuplicates(array);
    int startValue = 1;
    for (int i = 0; i < array.length; i++) {
        if (startValue + i  != array[i]){
            return false;
        }
    }
    return result;
}
public static int[] removeDuplicates(int[] input){
    Arrays.sort(input);
    List<Integer> result = new ArrayList<Integer>();
    int current = input[0];
    boolean found = false;

    for (int i = 0; i < input.length; i++) {
        if (current == input[i] && !found) {
            found = true;
        } else if (current != input[i]) {
            result.add(current);
            current = input[i];
            found = false;
        }
    }
    result.add(current);
    int[] array = new int[result.size()];
    for (int i = 0; i < array.length ; i ++){
        array[i] = result.get(i);
    }
    return array;
}
public static void main (String ... args){
    int[] input = new int[] { 4,2,3,4,1};
    System.out.println(isPermutation(input));
    //output true
    input = new int[] { 4,2,4,1};
    System.out.println(isPermutation(input));
    //output false
}

Ответ 16

int solution(int A[], int N) {
  int i,j,count=0, d=0, temp=0,max;
  for(i=0;i<N-1;i++) {
    for(j=0;j<N-i-1;j++) {
      if(A[j]>A[j+1]) {
        temp = A[j+1];
        A[j+1] = A[j];
        A[j] = temp;
      }
    }
  }
  max = A[N-1];
  for(i=N-1;i>=0;i--) {
    if(A[i]==max) {
      count++;
    }
    else {
      d++;
    }
    max = max-1;
  }
  if(d!=0) {
    return 0;
  }
  else {
    return 1;
  }
}