Найти возможную биекцию между символами и цифрами
Допустим, у вас есть строка S и последовательность цифр в списке L, такая что len (S) = len (L).
Какой был бы самый чистый способ проверки, если вы можете найти биекцию между символами строки и цифрами в последовательности, чтобы каждый символ соответствовал одной и только одной цифре.
- Когда следует использовать list.count (0) и как мне сбрасывать товар «False»?
- Функции sort () и reverse () не работают
- Ссылка на элемент в списке кортежей
- Понимание вложенного списка
- python: добавление словаря в список - я вижу указатель вроде поведения
Например, «aabbcc» должен соответствовать 115522, но не 123456 или 111111.
У меня сложная настройка с двумя dicts и loop, но мне интересно, есть ли чистый способ сделать это, возможно, используя некоторую функцию из библиотек Python.
- Python: удалить словарь из списка
- Можно ли использовать sys.platform == 'win32' для проверки на 64-битном Python?
- Удаление элементов из списка при повторении без использования дополнительной памяти в Python
- Python: возвращает индекс первого элемента списка, который делает переданную функцию true
- Ротация списка 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