Python – проверьте возможную биекцию между последовательностью символов и цифр
В математике биекция относится к функции, которая устанавливает взаимно однозначное соответствие между двумя множествами. Это означает, что каждый элемент в одном наборе имеет уникальный и отличный аналог в другом наборе, и наоборот. Другими словами, биекция гарантирует отсутствие дубликатов или недостающих элементов в отображении.
С точки зрения программирования, в частности Python, проверка биекции часто включает в себя проверку существования взаимно однозначного соответствия между элементами двух последовательностей или коллекций. Например, имея два списка, A и B, мы можем проверить, существует ли биекция между их элементами, сравнивая длины списков и проверяя, имеет ли каждый элемент в одном списке уникальный и отличный соответствующий элемент в другом списке.
Возможная биекция между последовательностью символов и цифр
В Python для проверки возможной биекции, т. е. взаимно-однозначного сопоставления между последовательностью символов и цифр, мы должны выполнить описанные ниже шаги.
Убедитесь, что последовательности имеют одинаковую длину. Прежде чем проверять биекцию, убедитесь, что последовательность символов и последовательность цифр имеют одинаковую длину. Если они имеют разную длину, биекция невозможна.
Создайте два словаря для сопоставления символов с цифрами и наоборот. Затем нам нужно инициализировать два пустых словаря: один для сопоставления символов с цифрами, а другой — для сопоставления цифр с символами.
-
Перебирайте последовательности и заполняйте словари. Теперь одновременно перебирайте символы и цифры, используя функцию zip(). Для каждой пары «символ-цифра» проверьте, существует ли уже этот символ в словаре «символ-цифра» и существует ли цифра в словаре «цифра-символ». Если любое из этих условий истинно, биекция невозможна. В противном случае добавьте пару символ-цифра в словари.
Проверьте, является ли сопоставление «один к одному». После заполнения словарей проверьте, равна ли длина словаря «символ-цифра» длине словаря «цифра-символ». Если они имеют разную длину, биекция невозможна, поскольку это будет означать, что один или несколько символов или цифр имеют несколько отображений.
Повторите процесс обратного сопоставления. Если предыдущий шаг пройден, т. Е. Отображение является взаимно однозначным, мы можем дополнительно повторить процесс обратного сопоставления цифр в символы, чтобы гарантировать, что биекция действительна в обоих направлениях.
Пример
Теперь давайте посмотрим пример реализации вышеупомянутых шагов с использованием кода Python.
В этом примере функция check_bijection() принимает на вход две последовательности: «символы» и «цифры». Сначала он проверяет, имеют ли последовательности одинаковую длину. Затем он инициализирует пустые словари для сопоставления символов с цифрами и цифр с символами.
Затем функция перебирает «символы» и «цифры» с помощью «zip()», проверяет наличие дубликатов в словарях и заполняет словари, если дубликаты не найдены. Наконец, он проверяет, равна ли длина обоих словарей, что указывает на взаимно однозначное сопоставление.
def check_bijection(characters, digits):
if len(characters) != len(digits):
return False
char_to_digit = {}
digit_to_char = {}
for char, digit in zip(characters, digits):
if char in char_to_digit or digit in digit_to_char:
return False
char_to_digit[char] = digit
digit_to_char[digit] = char
return len(char_to_digit) == len(digit_to_char)
characters = ['a', 'b', 'c']
digits = [1, 2, 3]
print(check_bijection(characters, digits))
characters = ['a', 'b', 'c']
digits = [1, 2, 2]
print(check_bijection(characters, digits))
Выход
True
False
Пример
В этом примере функция is_bijection() создает два словаря: char_to_digit и digit_to_char, чтобы отслеживать сопоставление между символами и цифрами. Он перебирает символы последовательности и диапазон цифр (от 0 до 9), используя функцию zip().
Для каждой пары символ-цифра он проверяет, сопоставлен ли уже символ с другой цифрой или цифра уже сопоставлена с другим символом. Если любое из условий выполняется, возвращается False. Если сопоставление действительно для всех пар, оно возвращает True.
def is_bijection(sequence):
char_to_digit = {}
digit_to_char = {}
for char, digit in zip(sequence, range(10)):
if char in char_to_digit and char_to_digit[char] != digit:
return False
if digit in digit_to_char and digit_to_char[digit] != char:
return False
char_to_digit[char] = digit
digit_to_char[digit] = char
return True
print(is_bijection("abc123"))
print(is_bijection("abc122"))
Выход
True
False