Как проверить, являются ли две строки перестановками друг друга, используя O (1) дополнительное пространство?

13

Учитывая две строки, как вы можете проверить, являются ли они перестановкой друг друга, используя пространство O (1)? Модификация строк никоим образом не допускается.
Примечание: O (1) пробел по отношению как к длине строки, так и к размеру алфавита.

анонимное
источник
3
Как вы думаете? Что вы пробовали и где застряли? Строки над алфавитом постоянного размера? Вы пытались вычислить их гистограммы?
Ювал
@YuvalFilmus это должно быть O (1) пробел как по длине строки, так и по размеру алфавита
Anonymous
Это кажется явно невозможным. Любой алгоритм потребует дополнительного пространства для хранения хотя бы позиции в одной строке или одном символе. Ни одна из этих вещей не является O (1).
Дэвид Шварц
@DavidSchwartz - как? O (1) означает константу, а не один бут. Неважно, какова длина строки, позиция в ней - одно число.
Давор
Это зависит от модели машины, очевидно, нет проблем в единообразных моделях. В модели логарифмической стоимости индекс хранится O(log n)для строк длины n, которая не является ни постоянной по длине, ни по размеру алфавита. Когда строки могут быть временно изменены, я думаю, что есть решение с увеличенным алфавитом, который является линейным по размеру алфавита, но постоянным по длине строки в логарифмической модели.
кап

Ответы:

7

Наивным подходом было бы построение гистограмм обеих строк и проверка их одинаковости. Так как нам не разрешено хранить такую ​​структуру данных (размер которой был бы линейным по отношению к размеру алфавита), который мог бы быть вычислен за один проход, нам нужно подсчитать количество каждого возможного символа после другого:

function count(letter, string)
    var count := 0
    foreach element in string
        if letter = element
            count++
    return count

function samePermutation(stringA, stringB)
    foreach s in alphabet
        if count(s, stringA) != count(s, stringB)
            return false
    return true

Это, конечно, предполагает, что счетчики и индексы итераторов являются целыми числами постоянного размера, а не зависят от длины строк.

Берги
источник
В качестве оптимизации вы можете использовать один массив и вычислять только гистограммы букв, с которыми вы сталкиваетесь. Таким образом, сложность становится независимой от размера алфавита.
Юваль
Чтобы расширить комментарий @YuvalFilmus, вам также необходимо 1) проверить, что длины строк одинаковы или 2) выполнить итерацию по обеим входным строкам. Вам нужен один из них, так как возможно, что некоторые буквы в одной не в другой. Вариант 1 должен иметь меньше расчетов.
BurnsBA
@YuvalFilmus Я хотел бы избежать этого, поскольку это означало бы квадратичную сложность времени, я ожидал бы, что алфавит будет меньше, чем средний размер строки. Для маленьких строк и упорядоченного алфавита я бы рассмотрел вычисление следующего наименьшего существующего символа вместе со счетчиком во внутреннем цикле, чтобы можно было пропустить несколько итераций цикла алфавита - со сложностью O(n * min(n, |Σ|)). Хм, теперь, когда я думаю об этом, это звучит как «разрешено повторить» решение из вашего ответа, не так ли?
Берги
countнет O(1)(то есть может переполниться)
reinierpost
1
@Eternalcode Я никогда не говорил , что countбыло int:-) Да, это не будет работать, но в Java , что не может случиться так или иначе
Берги
12

Обозначим массивы через и предположим, что они имеют длину n .A,ВN

Предположим сначала, что значения в каждом массиве различны. Вот алгоритм, который использует пространство :О(1)

  1. Вычислите минимальные значения обоих массивов и убедитесь, что они идентичны.

  2. Вычислите вторые минимальные значения обоих массивов и убедитесь, что они идентичны.

  3. И так далее.

Для вычисления минимального значения массива явно используется пространство . Учитывая k- й наименьший элемент, мы можем найти ( k + 1 ) -й наименьший элемент, найдя минимальное значение, превышающее k- й наименьший элемент (здесь мы используем тот факт, что все элементы различны).О(1)К(К+1)К

Когда элементам разрешено повторяться, мы модифицируем алгоритм следующим образом:

  1. Вычислите минимальные значения для обоих массивов, посчитайте, сколько раз каждый из них появляется, и проверьте, что m A , 1 = m B , 1 и что значения идентичны.мA,1,мВ,1мA,1знак равномВ,1

  2. Вычислите минимальные значения превышающие m A , 1 , m B , 1 в двух массивах (соответственно), и подсчитайте, сколько раз каждый из них появляется. Убедитесь, что m A , 2 = m B , 2 и что количество идентичных.мA,2,мВ,2мA,1,мВ,1мA,2знак равномВ,2

  3. И так далее.

Юваль Фильмус
источник
1
Будет ли такой подход поскольку кажется, что единственный способ найти элемент min в пространстве O ( 1 ) и доступ к массиву только для чтения - это перебирать все элементы? O(n2)O(1)
Райана
4
Это требует упорядочения по алфавиту, хотя алгоритм легко изменить, не требуя этого. Однако в случае «имеет дубликаты» для этого требуется пространство , а не O ( 1 ) . Подсчет занимает место. О(Л.Г.N)О(1)
Дерек Элкинс покинул SE
7
Подсчет требует (логарифмического) пространства, но - согласно этому определению использования пространства - так же, как итерация по массиву. Таким образом, в строгом смысле использования пространства нет способа сделать это в постоянном пространстве.
Даниэль Жур
4
@DanielJour, это зависит от того, какую модель затрат вы используете. При одинаковых затратах это возможно в постоянном пространстве.
Райана
7
Если вам разрешено только постоянное число битов, вы можете обрабатывать только алфавиты постоянного размера (это следует из теории обычных языков).
Юваль
2

Определите некоторую функцию f (c), которая отображает некоторый символ c на уникальное простое число (a = 2, b = 3, c = 5 и т. Д.).

set checksum = 1
set count = 0 <-- this is probably not even necessary, but it's another level of check
for character c in string 1
    checksum = checksum * f(c)
    count = count + 1
for character c in string 2
    checksum = checksum / f(c)
    count = count = 1

permutation = count == 0 and checksum == 1

О(1)

Алекс Стассе
источник
е(с)О(1)О(1)
Еще одна проблема, которую я осознал после публикации, заключается в том, что контрольная сумма будет гигантским числом для больших строк, поскольку она сама по себе может нарушать требования к пространству O (1). Эту проблему можно решить, используя числа с плавающей точкой и умножение на символ в одной строке, затем деление на другую, а затем просто говоря, что контрольная сумма должна быть близка к 1. Строки должны быть по-настоящему гигантскими, чтобы ошибка с плавающей запятой представляла проблему.
Алекс Стассе
4
Такие ответы - причина, по которой мы должны быть осторожны с нашей моделью вычислений. Обычная модель, которую мы используем при анализе алгоритмов, рассчитывает память в единицах машинных слов , которые имеют размерО(журналN)биты. Таким образом, вы не можете делать вычисления в целых числах. Если вы переключитесь на число с плавающей запятой, ваш алгоритм может потерпеть неудачу, даже если две строки являются перестановками друг друга, и, наоборот, не обязательно даст правильный ответ, если это не так.
Юваль
4
Это не использует постоянное пространство. Даже для фиксированного алфавита размер целочисленной контрольной суммы будетΘ(N) биты для входов длины N,
Дэвид Ричерби
0

Вы можете сделать это O(nlogn). Сортируйте две строки и сравнивайте их индекс по индексу. Если они где-то отличаются, они не являются перестановками друг друга.

Для O(n)решения проблемы можно использовать хеширование. Эта функция хеширования будет работать, и eдля любой буквы будет ее значение ascii. Если два хэша строк различаются, они не являются перестановками друг друга.

Функция хеширования в ссылке:

Одним из потенциальных кандидатов может быть это. Зафиксируйте нечетное целое число R. Для каждого элемента e, который вы хотите хэшировать, вычислите коэффициент (R + 2 * e). Затем вычислите произведение всех этих факторов. Наконец, разделите произведение на 2, чтобы получить хеш.

Коэффициент 2 в (R + 2e) гарантирует, что все факторы являются нечетными, следовательно, избегая того, чтобы продукт когда-либо становился равным 0. Деление на 2 в конце состоит в том, что продукт всегда будет нечетным, следовательно, деление просто удаляет постоянный бит ,

Например, я выбираю R = 1779033703. Это произвольный выбор, поэтому некоторые эксперименты должны показать, является ли данный R хорошим или плохим. Предположим, ваши значения [1, 10, 3, 18]. Продукт (рассчитанный с использованием 32-битных целых)

(R + 2) * (R + 20) * (R + 6) * (R + 36) = 3376724311 Следовательно, хеш будет

3376724311/2 = 1688362155.

Использование двойного хеширования (или даже для избыточного убийства) путем изменения значения R успешно идентифицирует их как перестановки с очень высокой вероятностью.

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

Допустим, у вас есть две строки с именами s и t.

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

  1. s.length == t.length
  2. сумма символов s == сумма символов в t
  3. [так же, как в 2. но с xor вместо sum]

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

  1. отсортировать одну строку, чтобы она была равна другой, и сравнить (O (n ^ 2))
  2. отсортировать оба и сравнить (O (2n log (n))
  3. проверьте для каждого символа в s, есть ли одинаковые суммы в обеих строках (O (n ^ 2))

Конечно, вы не можете сортировать так быстро, если вам не разрешено использовать дополнительное пространство. Таким образом, не имеет значения, какой алгоритм вы выберете - каждый алгоритм будет нуждаться в O (n ^ 2) времени, когда есть только O (1) пространство и если эвристика не смогла доказать, что они не могут быть равны.

MurksVomOrk
источник
3
« Модификация строк никоим образом не допускается ».
Берги
0

В коде в стиле C для всей процедуры:

for (int i = 0; i < n; i++) {
   int k = -1;
   next: for (int j = 0; j <= i; j++)
       if (A[j] == A[i]) {
          while (++k < n)
              if (B[k] == A[i])
                  continue next;
          return false; // note at this point j == i
       }
}
return true; 

Или в очень подробном псевдокоде (с использованием индексации на основе 1)

// our loop invariant is that B contains a permutation of the letters
// in A[1]..A[i-1]
for i=1..n
   if !checkLetters(A, B, i)
      return false
return true

где функция checkLetters (A, B, i) проверяет, что если в A [1] .. A [i] имеется M копий A [i], то в B имеется как минимум M копий A [i]:

checkLetters(A,B,i)
    k = 0 // scan index into B
    for j=1..i
      if A[j] = A[i]
         k = findNextValue(B, k+1, A[i])
         if k > n
            return false
    return true

и функция findNextValue ищет в B значение, начинающееся с индекса, и возвращает индекс, где оно было найдено (или n + 1, если не найдено).

Идея в том, что мы уже проверили, что у нас есть перестановка символов перед i во внешнем цикле. В цикле j мы проходим все символы, которые соответствуют A [i], и мы должны быть в состоянии найти уникальные индексы в B, которые соответствуют им (включая i-ую позицию). Таким образом, для каждого из них нам нужно продвинуть наше сканирование вперед через B. Время равно O (N2).

Мотин
источник
Можете ли вы преобразовать код C в псевдокод? Это не сайт программирования.
Юваль
Это похоже на другой вариант ответа Берги (с некоторыми несущественными отличиями).
Юваль
Это похоже, но не вариант. Берги ответО(Nм)где m = размер алфавита. ЭтоО(N2),
MotiN
0

Я думаю, что это самый простой алгоритм (с О(N3) время, N длина струн)

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

Вот кусок питона, чтобы сделать это точным

s1="abcaba"
s2="aadbba"

def check_if_permutations(string1, string2):
  for string in [string1, string2]:
    # string references string1 
    #  string2, it is not a copy
    for char in string:
      count1=0
      for char1 in string1:
        if  char==char1:
          count1+=1
      count2=0
      for char2 in string2:
        if  char==char2:
          count2+=1
      if count1!=count2:
        print('unbalanced character',char)
        return()
  print ("permutations")
  return()

check_if_permutations(s1,s2)

Программа нуждается в некоторых указателях на строки ( string, string1, string2, char, char1, char2) и переменного размераО(журналN)для подсчета ( count1, count2). Нужно проверить, равны ли символы или нет, но не нужно упорядочивать эти символы. Возможно, для небольших целых чисел нужны переменные (например, для хранения логических значений или для представления позиции stringв [string1, string2].

Конечно, вам даже не нужны переменные count, но вы можете использовать указатели.

s1="abcaba"
s2="aadbba"

def check_if_permutations(string1, string2):
  for string in [string1, string2]:
    # string references one of string1 
    # or string2, it is not a copy
    for char in string:
      # p1 and p2 should be views as pointers
      p1=0
      p2=0
      while (p1<len(string1)) and (p2<len(string2)):
        # p1>=len(string1): p1 points to beyond end of string
        while (p1<len(string1)) and (string1[p1]!=char) :
          p1+=1
        while(p2<len(string2)) and (string2[p2]!=char):
          p2+=1
        if (p1<len(string1)) != (p2<len(string2)):
          print('unbalanced character',char)
          return()
        p1+=1
        p2+=1
  print ("permutations")
  return()

check_if_permutations(s1,s2)

Эта вторая программа нуждается в переменных, аналогичных первой, за исключением того, что она не нуждается в О(журнал(N))переменные для хранения значений счетчика.

Так что на самом деле это не зависит от N или размер алфавита.

miracle173
источник
Это то же самое, что и решение Берги ниже.
Юваль
@YuvalFilmus Нет, он не выполняет итерацию по всему алфавиту, поэтому его время выполнения не зависит от размера алфавита. Он использует только две строки, которые должны быть проверены. Также вторая программа избегает подсчета.
miracle173
@YuvalFilmus Теперь я вижу, что ваши и другие комментарии указывают на то, как я использовал в своей программе.
miracle173