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

Ваш второй пример на самом деле не сработает:

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 () перегружают побитовый оператор ИЛИ, так что он вычисляет объединение обоих наборов. Это гарантирует, что вы пройдете цикл по всем символам обеих строк только для каждого символа.

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

Вот способ, который является 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

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

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

Вот несколько выполнений по времени на очень маленьких строках с использованием двух разных методов:
1. sorting
2. подсчет (в частности, оригинальный метод @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 циклов составляет:

несоответствие (строка 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

совпадение (строка 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

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

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

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

Выполняйте только «общий» анализ в стиле О.

В целом, это сортировки О (п log (п)).

Решение a.count(char) for char in a - О (п²). Каждый проход счета - это полное исследование строки.

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

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

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

Псевдокод:

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).

Это функция 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's version (it is O(N)).
    2. The multiple returns in the function look horrible.

Эта версия быстрее, чем все представленные примеры, за исключением того, что она на 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) для большого iterable1 (проверена на тезаурусе 25 МБ).

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

Извините, что мой код написан не на 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.

Вот код мартинуса на питоне. Это работает только для строк 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

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

Testing against 9227 words.

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

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

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

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

Это получено из @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's method if you don't want to create two dictionaries and don't mind the extra typing.

В 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

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

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

Это решение 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

Проверка, являются ли две строки перестановками друг друга в 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

Во-первых, для решения таких задач, например независимо от того, являются ли String 1 и String 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

Как насчет этого. Довольно прямолинейно и легко читается. Это для строк, так как согласно OP.

Учитывая, что сложность sorted () равна O (n log n).

def checkPermutation(a,b):
    # input: strings a and b
    # return: boolean true if a is Permutation of b

    if len(a) != len(b):
        return False
    else:
        s_a = ''.join(sorted(a))
        s_b = ''.join(sorted(b))
        if s_a == s_b:
            return True
        else:
            return False

# test inputs
a = 'sRF7w0qbGp4fdgEyNlscUFyouETaPHAiQ2WIxzohiafEGJLw03N8ALvqMw6reLN1kHRjDeDausQBEuIWkIBfqUtsaZcPGoqAIkLlugTxjxLhkRvq5d6i55l4oBH1QoaMXHIZC5nA0K5KPBD9uIwa789sP0ZKV4X6'
b = 'Vq3EeiLGfsAOH2PW6skMN8mEmUAtUKRDIY1kow9t1vIEhe81318wSMICGwf7Rv2qrLrpbeh8bh4hlRLZXDSMyZJYWfejLND4u9EhnNI51DXcQKrceKl9arWqOl7sWIw3EBkeu7Fw4TmyfYwPqCf6oUR0UIdsAVNwbyyiajtQHKh2EKLM1KlY6NdvQTTA7JKn6bLInhFvwZ4yKKbzkgGhF3Oogtnmzl29fW6Q2p0GPuFoueZ74aqlveGTYc0zcXUJkMzltzohoRdMUKP4r5XhbsGBED8ReDbL3ouPhsFchERvvNuaIWLUCY4gl8OW06SMuvceZrCg7EkSFxxprYurHz7VQ2muxzQHj7RG2k3khxbz2ZAhWIlBBtPtg4oXIQ7cbcwgmBXaTXSBgBe3Y8ywYBjinjEjRJjVAiZkWoPrt8JtZv249XiN0MTVYj0ZW6zmcvjZtRn32U3KLMOdjLnRFUP2I3HJtp99uVlM9ghIpae0EfC0v2g78LkZE1YAKsuqCiiy7DVOhyAZUbOrRwXOEDHxUyXwCmo1zfVkPVhwysx8HhH7Iy0yHAMr0Tb97BqcpmmyBsrSgsV1aT3sjY0ctDLibrxbRXBAOexncqB4BBKWJoWkQwUZkFfPXemZkWYmE72w5CFlI6kuwBQp27dCDZ39kRG7Txs1MbsUnRnNHBy1hSOZvTQRYZPX0VmU8SVGUqzwm1ECBHZakQK4RUquk3txKCqbDfbrNmnsEcjFaiMFWkY3Esg6p3Mm41KWysTpzN6287iXjgGSBw6CBv0hH635WiZ0u47IpUD5mY9rkraDDl5sDgd3f586EWJdKAaou3jR7eYU7YuJT3RQVRI0MuS0ec0xYID3WTUI0ckImz2ck7lrtfnkewzRMZSE2ANBkEmg2XAmwrCv0gy4ExW5DayGRXoqUv06ZLGCcBEiaF0fRMlinhElZTVrGPqqhT03WSq4P97JbXA90zUxiHCnsPjuRTthYl7ZaiVZwNt3RtYT4Ff1VQ5KXRwRzdzkRMsubBX7YEhhtl0ZGVlYiP4N4t00Jr7fB4687eabUqK6jcUVpXEpTvKDbj0JLcLYsneM9fsievUz193f6aMQ5o5fm4Ilx3TUZiX4AUsoyd8CD2SK3NkiLuR255BDIA0Zbgnj2XLyQPiJ1T4fjStpjxKOTzsQsZxpThY9Fvjvoxcs3HAiXjLtZ0TSOX6n4ZLjV3TdJMc4PonwqIb3lAndlTMnuzEPof2dXnpexoVm5c37XQ7fBkoMBJ4ydnW25XKYJbkrueRDSwtJGHjY37dob4jPg0axM5uWbqGocXQ4DyiVm5GhvuYX32RQaOtXXXw8cWK6JcSUnlP1gGLMNZEGeDXOuGWiy4AJ7SH93ZQ4iPgoxdfCuW0qbsLKT2HopcY9dtBIRzr91wnES9lDL49tpuW77LSt5dGA0YLSeWAaZt9bDrduE0gDZQ2yX4SDvAOn4PMcbFRfTqzdZXONmO7ruBHHb1tVFlBFNc4xkoetDO2s7mpiVG6YR4EYMFIG1hBPh7Evhttb34AQzqImSQm1gyL3O7n3p98Kqb9qqIPbN1kuhtW5mIbIioWW2n7MHY7E5mt0'

print(checkPermutation(a, b)) #optional

def permute(str1,str2):
    if sorted(str1) == sorted(str2):
        return True
    else:
        return False

str1 = "hello"
str2='olehl'
a=permute(str1,str2)
print(a

from collections import defaultdict
def permutation(s1,s2):
    h = defaultdict(int)
    for ch in s1:
        h[ch]+=1
    for ch in s2:
        h[ch]-=1
    for key in h.keys():
        if h[key]!=0 or len(s1)!= len(s2):
            return False
        return True
print(permutation("tictac","tactic"))