Найти возможную биекцию между символами и цифрами

Допустим, у вас есть строка S и последовательность цифр в списке L, такая что len (S) = len (L).

Какой был бы самый чистый способ проверки, если вы можете найти биекцию между символами строки и цифрами в последовательности, чтобы каждый символ соответствовал одной и только одной цифре.

Например, «aabbcc» должен соответствовать 115522, но не 123456 или 111111.

У меня сложная настройка с двумя dicts и loop, но мне интересно, есть ли чистый способ сделать это, возможно, используя некоторую функцию из библиотек Python.

5 Solutions collect form web for “Найти возможную биекцию между символами и цифрами”

Я бы использовал набор для этого:

In [9]: set("aabbcc") Out[9]: set(['a', 'c', 'b']) In [10]: set(zip("aabbcc", [1, 1, 5, 5, 2, 2])) Out[10]: set([('a', 1), ('c', 2), ('b', 5)]) 

Второй набор будет иметь длину, равную первому множеству, если и только если отображение сюръективно. (если это не так, у вас будет две копии сопоставления букв на один и тот же номер во втором наборе или наоборот)

Вот код, который реализует идею

 def is_bijection(seq1, seq2): distinct1 = set(seq1) distinct2 = set(seq2) distinctMappings = set(zip(seq1, seq2)) return len(distinct1) == len(distinctMappings) and len(distinct2) == len(distinctMappings) 

Это также вернет true, если одна последовательность короче другой, но действительное сопоставление уже установлено. Если последовательности должны быть одинаковой длины, вы должны добавить чек для этого.

Есть более элегантный способ сделать это (с сортировкой и itertools.groupby ), но я готов спать, дебютировав, чтобы понять это прямо сейчас. Но это все равно должно работать:

 In [172]: S = "aabbcc" In [173]: L = [1, 1, 5, 5, 2, 2] In [174]: mapping = collections.defaultdict(list) In [175]: reverseMapping = collections.defaultdict(list) In [176]: for digit, char in zip(L, S): mapping[digit].append(char) reverseMapping[char].append(digit) .....: In [177]: all(len(set(v))==1 for v in mapping.values()) and all(len(set(v))==1 for v in reverseMapping.values()) Out[177]: True In [181]: S = "aabbcc" In [182]: L = [1, 2, 3, 4, 5, 6] In [183]: mapping = collections.defaultdict(list) In [184]: reverseMapping = collections.defaultdict(list) In [185]: for digit, char in zip(L, S): mapping[digit].append(char) reverseMapping[char].append(digit) .....: In [186]: all(len(set(v))==1 for v in mapping.values()) and all(len(set(v))==1 for v in reverseMapping.values()) Out[186]: False 

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

Это соответствует порядку:

 >>> s = "aabbcc" >>> n = 115522 >>> l1 = dict(zip(s, str(n))).items() >>> l2 = zip(s, str(n)) >>> l1 [('a', '1'), ('c', '2'), ('b', '5')] >>> l2 [('a', '1'), ('a', '1'), ('b', '5'), ('b', '5'), ('c', '2'), ('c', '2')] >>> not bool([i for i in l2 if i not in l1]) True >>> n = 115225 >>> l1 = dict(zip(s, str(n))).items() >>> l2 = zip(s, str(n)) >>> not bool([i for i in l2 if i not in l1]) False 

Поскольку вы обычно говорите только о биекциях между наборами, я полагаю, в отличие от других ответов, что порядок цифр не обязательно соответствует порядку букв. Если это так, есть короткое, изящное решение, но для него требуется класс collections.Counter , который был введен в python 2.7. Для тех, кто придерживается более старой версии, есть backport для 2.5+ .

 from collections import Counter def bijection_exists_between(a, b): return sorted(Counter(a).values()) == sorted(Counter(b).values()) 

Тестирование:

 >>> bijection_exists_between("aabbcc", "123123") True >>> bijection_exists_between("aabbcc", "123124") False 

Ваши примеры довольно легки в случаях краев, потому что другой способ чтения вашего вопроса позволяет нести число цифр и количество букв (т. Е. Вы ищете биекцию из набора уникальных символов в набор уникальных цифр, поэтому, например, "aabbcc" будет бичевать на "123333" .). Если это то, что вы имели в виду, используйте эту версию:

 def bijection_exists_between(a, b): return len(set(a)) == len(set(b)) 
 import itertools a = 'aabbcc' b = 112233 z = sorted(zip(str(a), str(b))) x = all( gx == g0 for k, g in itertools.groupby(z, key=lambda x: x[0]) for gx in g for g0 in g ) print x 

или:

 import itertools a = 'aabbcc' b = 112233 z = zip(str(a), str(b)) x = all( (z1[0] == z2[0]) == (z1[1] == z2[1]) for z1 in z for z2 in z ) print x 
  • Python: сортировка списка с несколькими атрибутами и смешанным порядком
  • Как удалить элемент из списка кортежей, если второй элемент в каждом кортеже является дубликатом?
  • Как сделать итератор python назад?
  • Выполнение функции выполняется только для определенных условий в python
  • генератор базового уровня python и список вопросов
  • Python -Интеграция нескольких списков?
  • Как правильно разбить этот список строк?
  • Как наследовать и расширять объект списка в Python?
  • Каков наиболее эффективный способ сопоставления элементов списка с строками в большом файле в Python?
  • Список сортировки в Python двумя другими списками
  • Python - Как проверить монотонность списка
  •  
    Interesting Posts for Van-Lav

    напечатать код, который определяет лямбда-функцию

    Существуют ли технические причины, по которым Ruby DSL, например RSpec, не может быть переписан на Python?

    Matplotlib – логарифмическая шкала, но требует не логарифмических меток

    Использование модуля GitPython для удаленной ветви HEAD

    Python – вручную установить пакет с помощью virtualenv

    Pandas Column математические операции Нет ошибки нет ответа

    Вставить в первую позицию списка в Python

    Как я могу подключить функцию в модуле python?

    Приложения не будут запускаться в GAE – «невозможно связать с localhost: 0»

    python: не может конкатенировать объекты 'str' и 'long'

    Функциональный тест приложения Android с помощью appium и python

    Как процессы передают список между собой в Python?

    Работа с TIFF (импорт, экспорт) в Python с использованием numpy

    Алгоритм Soundex в Python (запрос справки на домашнюю работу)

    Каковы различия в Pythons time.clock () в Mac против Windows?

    Python - лучший язык программирования в мире.