Поиск по сайту:

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

Статьи по данной тематике: