Ответ 1

эвристически вы, вероятно, лучше отделить их от размера строки.

псевдокод:

returnvalue = false
if len(a) == len(b)
   if len(a) < threshold
      returnvalue = (sorted(a) == sorted(b))
   else
       returnvalue = naminsmethod(a, b)
return returnvalue

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

Это довольно распространенный способ разделить такие вещи на основе размера или типа ввода. Алгоритмы имеют разные сильные или слабые стороны, и было бы глупо использовать тот, где другой был бы лучше... В этом случае метод Намина - O (n), но имеет больший постоянный множитель, чем метод сортировки O (n log n).

Ответ 2

Вот путь, который O (n), асимптотически лучше, чем два способа, которые вы предлагаете.

import collections

def same_permutation(a, b):
    d = collections.defaultdict(int)
    for x in a:
        d[x] += 1
    for x in b:
        d[x] -= 1
    return not any(d.itervalues())

## same_permutation([1,2,3],[2,3,1])
#. True

## same_permutation([1,2,3],[2,3,1,1])
#. False

Ответ 3

", но первый медленнее, когда (например) первый char a нигде не находится в b".

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

Выполняйте только общий анализ O.

В целом, типы O (n log (n)).

Решение a.count(char) for char in a O (n ²). Каждый счетчик считается полным просмотром строки.

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

В вашем неясном специальном случае ( "первый char of a нигде в b" ) это достаточно часто, чтобы иметь значение? Если это просто особый случай, о котором вы думали, отложите его. Если это факт о ваших данных, тогда рассмотрите его.

Ответ 4

Я думаю, что первый из них - "очевидный" способ. Он короче, яснее и, вероятно, быстрее во многих случаях, потому что встроенный сорт Python сильно оптимизирован.

Ответ 5

Второй пример не будет работать:

all(a.count(char) == b.count(char) for char in a)

будет работать только в том случае, если b не содержит дополнительных символов, не содержащих a. Он также выполняет дублирование работы, если символы в строке повторяются.

Если вы хотите знать, являются ли две строки перестановками одних и тех же уникальных символов, просто выполните:

set(a) == set(b)

Чтобы исправить ваш второй пример:

all(str1.count(char) == str2.count(char) for char in set(a) | set(b))

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

Тем не менее, метод sorted() намного проще и интуитивно понятен, и я бы использовал его.

Ответ 6

Вот несколько приуроченных исполнений на очень маленьких строках, используя два разных метода:
1. сортировка
2. подсчет (в частности, оригинальный метод by @namin).

a, b, c = 'confused', 'unfocused', 'foncused'

sort_method = lambda x,y: sorted(x) == sorted(y)

def count_method(a, b):
    d = {}
    for x in a:
        d[x] = d.get(x, 0) + 1
    for x in b:
        d[x] = d.get(x, 0) - 1
    for v in d.itervalues():
        if v != 0:
            return False
    return True

Среднее время выполнения двух методов более 100 000 циклов:

non-match (строка a и b)

$ python -m timeit -s 'import temp' 'temp.sort_method(temp.a, temp.b)'
100000 loops, best of 3: 9.72 usec per loop
$ python -m timeit -s 'import temp' 'temp.count_method(temp.a, temp.b)'
10000 loops, best of 3: 28.1 usec per loop

match (строка a и c)

$ python -m timeit -s 'import temp' 'temp.sort_method(temp.a, temp.c)'
100000 loops, best of 3: 9.47 usec per loop
$ python -m timeit -s 'import temp' 'temp.count_method(temp.a, temp.c)'
100000 loops, best of 3: 24.6 usec per loop

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

Ответ 7

Я сделал довольно полное сравнение на Java со всеми словами в моей книге. Метод подсчета использует метод сортировки во всех отношениях. Результаты:

Testing against 9227 words.

Permutation testing by sorting ... done.        18.582 s
Permutation testing by counting ... done.       14.949 s

Если кто-то хочет, чтобы алгоритм и тестовый набор данных, прокомментируйте.

Ответ 8

Во-первых, для решения таких проблем, например. Строка 1 и Строка 2 точно совпадают или нет, вы можете использовать "if", так как это O (1). Во-вторых, важно учитывать, являются ли они только числовыми значениями или они могут быть также словами в строке. Если последнее верно (слова и числовые значения находятся в строке одновременно), ваше первое решение не будет работать. Вы можете улучшить его, используя функцию "ord()", чтобы сделать это числовое значение ASCII. Однако, в конце концов, вы используете сортировку; поэтому в худшем случае ваша временная сложность будет равна O (NlogN). На этот раз сложность не плохая. Но вы можете сделать лучше. Вы можете сделать это O (N). Мое "предложение" использует массив (список) и устанавливается одновременно. Обратите внимание, что для нахождения значения в массиве требуется итерация, поэтому сложность времени O (N), но поиск значения в наборе (который, как я предполагаю, реализован с помощью HashTable в Python, я не уверен) имеет сложность O (1)

def Permutation2(Str1, Str2):

ArrStr1 = list(Str1) #convert Str1 to array
SetStr2 = set(Str2) #convert Str2 to set

ArrExtra = []

if len(Str1) != len(Str2): #check their length
    return False

elif Str1 == Str2: #check their values
    return True

for x in xrange(len(ArrStr1)):
    ArrExtra.append(ArrStr1[x])

for x in xrange(len(ArrExtra)): #of course len(ArrExtra) == len(ArrStr1) ==len(ArrStr2)
    if ArrExtra[x] in SetStr2: #checking in set is O(1)
        continue
    else:
        return False

return True

Ответ 9

Пойдите с первым - это намного проще и понятнее. Если вы действительно имеете дело с невероятно большими строками, а производительность - настоящая проблема, тогда не используйте Python, используйте что-то вроде C.

Что касается Zen Python, то должен быть только один очевидный способ делать вещи, относится к маленьким, простым вещам. Очевидно, что для любой достаточно сложной задачи всегда будут существовать небольшие изменения в способах ее выполнения.

Ответ 10

Извините, что мой код не в Python, я его никогда не использовал, но я уверен, что это можно легко перевести на python. Я считаю, что это быстрее, чем все другие уже опубликованные примеры. Это также O (n), но останавливается как можно скорее:

public boolean isPermutation(String a, String b) {
    if (a.length() != b.length()) {
        return false;
    }

    int[] charCount = new int[256];
    for (int i = 0; i < a.length(); ++i) {
        ++charCount[a.charAt(i)];
    }

    for (int i = 0; i < b.length(); ++i) {
        if (--charCount[b.charAt(i)] < 0) {
            return false;
        }
    }
    return true;
}

Сначала я не использую словарь, а массив размером 256 для всех символов. Доступ к индексу должен быть намного быстрее. Затем, когда вторая строка повторяется, я сразу возвращаю false, когда счетчик становится ниже 0. Когда второй цикл завершен, вы можете быть уверены, что строки являются перестановкой, потому что строки имеют одинаковую длину и никакой символ не использовался чаще в b по сравнению с a.

Ответ 11

Здесь код martinus в python. Он работает только для строк ascii:

def is_permutation(a, b):
    if len(a) != len(b):
        return False

    char_count = [0] * 256
    for c in a:
        char_count[ord(c)] += 1

    for c in b:
        char_count[ord(c)] -= 1
        if char_count[ord(c)] < 0:
            return False

    return True

Ответ 12

В Python 3.1/2.7 вы можете просто использовать collections.Counter(a) == collections.Counter(b).

Но sorted(a) == sorted(b) по-прежнему остается самым очевидным IMHO. Вы говорите о перестановках - изменении порядка - поэтому сортировка - это очевидная операция для стирания этой разницы.

Ответ 13

Это функция PHP, о которой я писал неделю назад, которая проверяет, являются ли два слова анаграммами. Как бы это сравнить (если реализовано то же самое в python) с другими предложенными методами? Комментарии?

public function is_anagram($word1, $word2) {
    $letters1 = str_split($word1);
    $letters2 = str_split($word2);
    if (count($letters1) == count($letters2)) {
        foreach ($letters1 as $letter) {
            $index = array_search($letter, $letters2);
            if ($index !== false) {
                unset($letters2[$index]);
            }
            else { return false; }
        }
        return true;
    }
    return false;        
}

Здесь буквальный перевод на Python версии PHP (от JFS):

def is_anagram(word1, word2):
    letters2 = list(word2)
    if len(word1) == len(word2):
       for letter in word1:
           try:
               del letters2[letters2.index(letter)]
           except ValueError:
               return False               
       return True
    return False

Комментарии:

    1. The algorithm is O(N**2). Compare it to @namin version (it is O(N)).
    2. The multiple returns in the function look horrible.

Ответ 14

Эта версия быстрее, чем любые представленные выше примеры, за исключением того, что на коротких строках она на 20% медленнее, чем sorted(x) == sorted(y). Это зависит от вариантов использования, но, как правило, 20% прироста производительности недостаточны для оправдания усложнения кода с использованием другой версии для коротких и длинных строк (как в ответе @patros).

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

def isanagram(iterable1, iterable2):
    d = {}
    get = d.get
    for c in iterable1:
        d[c] = get(c, 0) + 1
    try:
        for c in iterable2:
            d[c] -= 1
        return not any(d.itervalues())
    except KeyError:
        return False

Непонятно, почему эта версия быстрее, чем defaultdict (@namin's) одна для больших iterable1 (проверена на тезаурусе 25 МБ).

Если мы заменим get в цикле на try: ... except KeyError, то он выполняет в 2 раза медленнее для коротких строк, т.е. когда количество дубликатов меньше.

Ответ 15

Это получается из ответа @patros.

from collections import Counter

def is_anagram(a, b, threshold=1000000):
    """Returns true if one sequence is a permutation of the other.

    Ignores whitespace and character case.
    Compares sorted sequences if the length is below the threshold,
    otherwise compares dictionaries that contain the frequency of the
    elements.
    """
    a, b = a.strip().lower(), b.strip().lower()
    length_a, length_b = len(a), len(b)
    if length_a != length_b:
        return False
    if length_a < threshold:
        return sorted(a) == sorted(b)
    return Counter(a) == Counter(b)  # Or use @namin method if you don't want to create two dictionaries and don't mind the extra typing.

Ответ 16

В Swift (или реализации других языков) вы можете посмотреть кодированные значения (в данном случае Unicode) и посмотреть, совпадают ли они.

Что-то вроде:

let string1EncodedValues = "Hello".unicodeScalars.map() {
//each encoded value
$0
//Now add the values
}.reduce(0){ total, value in
    total + value.value
}

let string2EncodedValues = "oellH".unicodeScalars.map() {
    $0
    }.reduce(0) { total, value in
    total + value.value
}

let equalStrings = string1EncodedValues == string2EncodedValues ? true : false

Вам нужно будет обрабатывать пробелы и футляры по мере необходимости.

Ответ 17

def matchPermutation(s1, s2):
  a = []
  b = []

  if len(s1) != len(s2):
    print 'length should be the same'
  return

  for i in range(len(s1)):
    a.append(s1[i])

  for i in range(len(s2)):
    b.append(s2[i])

  if set(a) == set(b):
    print 'Permutation of each other'
  else:
    print 'Not a permutation of each other'
  return

#matchPermutaion('rav', 'var') #returns True
matchPermutaion('rav', 'abc') #returns False

Ответ 18

Это решение O(n) в Python, использующее хеширование со словарями. Обратите внимание, что я не использую словари по умолчанию, потому что код может остановиться таким образом, если мы определим, что две строки не являются перестановками после проверки второй буквы, например.

def if_two_words_are_permutations(s1, s2):
    if len(s1) != len(s2):
        return False
    dic = {}
for ch in s1:
    if ch in dic.keys():
        dic[ch] += 1
    else:
        dic[ch] = 1
for ch in s2:
    if not ch in dic.keys():
        return False
    elif dic[ch] == 0:
        return False
    else:
        dic[ch] -= 1
return True

Ответ 19

Проверка, являются ли две строки перестановками друг друга в Python

# First method
def permutation(s1,s2):
 if len(s1) != len(s2):return False;
 return ' '.join(sorted(s1)) == ' '.join(sorted(s2))


# second method
def permutation1(s1,s2):
 if len(s1) != len(s2):return False;
 array = [0]*128;
 for c in s1:
 array[ord(c)] +=1
 for c in s2:
   array[ord(c)] -=1
   if (array[ord(c)]) < 0:
     return False
 return True