Получить все алгоритмы совпадений [закрыто] ⇐ Python

[Anonymous]

Чтобы определить полную гистограмму для всех совпадений заданного размера, нам необходимо сгенерировать каждое возможное совпадение уникальным способом. Именно здесь становится полезным индуктивное описание из введения, поскольку оно дает возможность сделать это рекурсивно: мы можем сгенерировать все дуговые диаграммы с 𝑛 дугами из всех дуговых диаграмм с (𝑛−1) дугами, добавив по одной дуге к каждой из них. ровно 2𝑛−1 способами. Для этого мы берем дуговую диаграмму с (𝑛−1) дугами, вставляем одну новую точку на левом конце и еще одну точку где-то справа от нее (варианты 2𝑛−1), а затем сопоставляем вновь вставленные точки с получить дополнительную дугу. Единственная «проблема» заключается в том, что при этом нам нужно переименовать некоторые точки.
Вставка точки слева подразумевает, что индексы всех других точек должны быть увеличены на единицу. Более того, если мы вставим еще одну точку в некоторую позицию 𝑚 , то все индексы со значениями 𝑚 и выше снова придется увеличить на единицу.
Например, если мы начнем с дуговой диаграммы ровно с одной дугой, {( 0,1)} , затем вставка точки слева дает этому индексу ноль и увеличивает другие индексы, что приводит к {(1,2),(0,⋅)} с ⋅, который еще предстоит вставить. Теперь мы можем вставить вторую точку в позиции 𝑚=1,2,3. Это означает, что все индексы со значениями 𝑚 и выше необходимо увеличить. Для 𝑚=1 это приводит к {(2,3),(0,1)} , для 𝑚=2 мы получаем {(1,3),(0,2)} и, наконец, для 𝑚=3 мы находим { (1,2),(0,3)} .
Используя этот подход, напишите функцию get_all_matchings, которая принимает в качестве аргумента неотрицательное целое число 𝑛 и возвращает список всех (2𝑛−1)!! сопоставления на 𝑛 дугах.
Вы можете делать это рекурсивно или итеративно.

Код: Выделить всё

def insert_point(matching, index):
"""
Function to insert a point into a matching
"""
new_matching = []
for arc in matching:
if arc[0] < index:
new_matching.append(arc)
elif arc[0] == index:
new_matching.append((arc[0] + 1, arc[1] + 1))  # Adjust indices of arcs starting from the same point
else:
new_matching.append((arc[0] + 1, arc[1] + 1))
new_matching.insert(index, (index, index + 1))
return new_matching

def get_all_matchings(n):
"""
Function to generate all matchings of n arcs
"""
if n == 0:
return [[]]
elif n == 1:
return [[(0, 1)]]
else:
previous_matchings = get_all_matchings(n-1)  # Get matchings with n-1 arcs
all_matchings = []
for matching in previous_matchings:
for index in range(2*len(matching) + 1):  # Insert a new point at each possible position
new_matching = insert_point(matching, index)
all_matchings.append(new_matching)
return all_matchings

Вот мой код, я не могу понять проблему, поскольку код создает такие совпадения, как [(0,1),(1,2)] или [(0,1 ),(0,2)] что неверно
print(get_all_matchings(2)) [[(0, 1), (1, 3)], [(0, 1), (1, 2)], [(0, 1), (2, 3)]], но правильный результат будет [(0,1), (2,3)], [(0,3 ), (1,2)], [(0,2),(1,3)]

Подробнее здесь: https://stackoverflow.com/questions/783 ... -algorithm