Comment puis-je vérifier si une chaîne a les mêmes caractères? Python

J'ai besoin d'être en mesure de discerner si une chaîne de caractères d'une longueur arbitraire, supérieur à 1 (et uniquement en minuscules), a le même jeu de caractères à l'intérieur d'une base ou d'un modèle de chaîne de caractères.

Prenez, par exemple, la chaîne "aabc": "azbc" et "aaabc" serait fausse, alors que "acba" serait vrai.

Est-il un moyen rapide de le faire en python, sans garder la trace de toutes les permutations de la première chaîne, puis en les comparant à la chaîne de test?

Est-ce grave si il y a des répétitions? Comment aaaaaaabc comparer?
Qui serait fausse, je vais modifier ma question.
La création de toutes les permutations peut être plus rapide si vous testez beaucoup de valeurs par rapport à la même clé. Il vous en coûtera beaucoup de mémoire supplémentaire si.
C'est un peu trompeur de parler de "jeux" lors de la répétition des questions.
Stocker les permutations dans un comprimé trie ou d'un hachage de l'arbre au lieu d'une table de hachage pourrait être un compromis intéressant.

OriginalL'auteur Monte Carlo | 2013-08-20

  1. 10

    Trier les deux chaînes et de les comparer:

    sorted(str1) == sorted(str2)

    Si les chaînes de caractères peuvent ne pas être de la même longueur, vous pouvez vous assurer que pour gagner du temps:

    len(str1) == len(str2) and sorted(str1) == sorted(str2)
    L'optimisation ajoutée peut être utile, mais alors il peut beaucoup d'autres choses (par exemple, str1 == str2 or sorted(str1) == sorted(str2)); je ne vais pas la peine d'ajouter de la complexité à moins que vous savez que c'est un goulot d'étranglement et vous savez quelque chose sur les données.
    Je ne note que c'est vrai seulement si les deux ne sont pas de la même longueur. Si les chaînes sont longues, il serait probablement gagner du temps, même si seule une minorité ne sont pas égaux.
    Merci beaucoup, j'ai du nouveau, il doit y avoir un moyen plus intuitif que de faire toutes les combinaisons possibles, et la vérification de chaque permutation au modèle ou à la chaîne de test.
    Bien sûr, il serait probablement gagner du temps, mais si le gain de temps n'a pas d'importance, il n'en vaut pas la complexité ajoutée.

    OriginalL'auteur David Robinson

  2. 5

    C'est le O(n) solution

    from collections import Counter
Counter(str1) == Counter(str2)

    Mais la O(n * log n) solution à l'aide de sorted est probablement plus rapide pour mieux les valeurs de n

    Je ne sais pas pourquoi, mais cette solution semble effectivement assez lent, selon mon timeit tests. Peut-être trop de frais généraux? J'ai fourni les résultats de test dans ma réponse.
    oui Counter est assez lent pour ce que c'est, mais ensuite, il y a moins de chance pour les bugs, il est donc nécessaire de trouver un compromis. Peut-être que quelqu'un va optimiser mieux un jour

    OriginalL'auteur John La Rooy

  3. 1

    Voici une variation sur @Joowani solution qui n'utilise qu'un dictionnaire et va encore plus vite (du moins sur ma machine) :

    def cmp4(str1, str2):
    if len(str1) != len(str2):
        return False
    d = collections.defaultdict(int)
    for c in str1:
        d[c] += 1
    for c in str2:
        d[c] -= 1
    return all(v == 0 for v in d.itervalues())
    Génial! +10 j'ai confirmé qu'il s'exécute plus rapidement sur ma machine.

    OriginalL'auteur lmjohns3

  4. 0

    Voici un autre O(n) solution, plus longue mais légèrement plus vite que les autres:

    def cmp(str1, str2):
    if len(str1) != len(str2):
        return False

    d, d2 = {}, {}
    for char in str1:
        if char not in d:
            d[char] = 1
        else:
            d[char] += 1
    for char in str2:
        if char not in d:
            return False
        if char not in d2:
            d2[char] = 1
        else:
            d2[char] += 1

    return d == d2

    Il se fait de la même chose que gnibber de la solution (mais pour des raisons étranges les Counter() à partir des collections de la bibliothèque semble assez lent). Voici quelques timeit résultats:

    setup = '''
import collections
from collections import Counter

s1 = "abcdefghijklmnopqrstuvwxyz" * 10000
s2 = s1[::-1]

def cmp1(str1, str2):
    if len(str1) != len(str2):
        return False

    d, d2 = {}, {}
    for char in str1:
        if char not in d:
            d[char] = 1
        else:
            d[char] += 1
    for char in str2:
        if char not in d:
            return False
        if char not in d2:
            d2[char] = 1
        else:
            d2[char] += 1
    return d == d2

def cmp2(str1, str2):
    return len(str1) == len(str2) and sorted(str1) == sorted(str2)

def cmp3(str1, str2):    
    return Counter(str1) == Counter(str2)

def cmp4(str1, str2):
    if len(str1) != len(str2):
        return False
    d = collections.defaultdict(int)
    for c in str1:
        d[c] += 1
    for c in str2:
        d[c] -= 1
    return all(v == 0 for v in d.itervalues())
'''

    timeit.timeit("cmp1(s1, s2)", setup=setup, number = 100)
    8.027034027221656
    timeit.timeit("cmp2(s1, s2)", setup=setup, number = 100)
    8.175071701324946
    timeit.timeit("cmp3(s1, s2)", setup=setup, number = 100)
    14.243422195893174
    timeit.timeit("cmp4(s1, s2)", setup=setup, number = 100)
    5.0937542822775015

    Aussi, la solution de David qui vient de sortir sur le dessus quand la chaîne sont de petites tailles et en fait ils ont les mêmes caractères.

    EDIT: mis à jour les résultats de l'essai

    Vous pouvez utiliser d, d2 = dict.from_keys(str1), dict.from_keys(str2) Ensuite, vous n'aurez pas à faire la in test dans la boucle

    OriginalL'auteur Joohwan

  5. 0

    Heres une autre manière. En utilisant ce que nous ignorons la plupart des "ensembles":

    if len(set(str1) - set(str2)) == 0:
    print "Yes"

    OriginalL'auteur anarcky