from collections import defaultdict
def find_unique_combinations(tuples):
"""
Находит все уникальные комбинации чисел, которые встречаются во всех кортежах хотя бы один раз, с учетом их порядка внутри кортежа.
Args:
tuples (list of tuples): Список кортежей с целыми числами.
Returns:
list of tuples: Список уникальных комбинаций.
"""
combinations = set()
prefixes = defaultdict(set)
# Обработка пустых кортежей
if not tuples:
return []
# Перебираем каждый кортеж
for tup in tuples:
# Пропускаем пустой кортеж
if not tup:
continue
# Сохраняем префиксы каждого кортежа
for i in range(len(tup)):
prefix = tuple(tup[:i+1])
prefixes[prefix].add(tup)
# Ищем уникальные комбинации, которые встречаются во всех кортежах хотя бы один раз
for prefix in prefixes:
if len(prefixes[prefix]) == len(tuples):
combinations.add(prefix)
return list(combinations)
# Тестовые примеры
test_cases = [
[(1, 2, 3), (4, 2, 3), (1, 2, 5)],
[(1, 1, 1), (1, 1, 1), (1, 1, 1)],
[],
[(1, 2, 3), (), (4, 5, 6)],
[(1, 2, 3), (1, 2, 3), (1, 2, 3), (1, 2, 4)],
[(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) for _ in range(10000)],
]
for case in test_cases:
result = find_unique_combinations(case)
print(f"Input: {case}\nOutput: {result}")
Тестовые данные
[(1, 2, 3), (4, 2, 3), (1, 2, 5)] - ожидаемый результат: [(2, 3), (2), (3)]
[(1, 1, 1), (1, 1, 1), (1, 1, 1)] - ожидаемый результат: [(1, 1, 1), (1, 1), (1)]
[] - ожидаемый результат: []
[(1, 2, 3), (), (4, 5, 6)] - ожидаемый результат: []
[(1, 2, 3), (1, 2, 3), (1, 2, 3), (1, 2, 4)] - ожидаемый результат: [(1, 2), (1), (2)]
[(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) for _ in range(10000)] - Этот набор данных для проверки производительности.
Учтите, что порядок элементов в возвращаемом списке не важен. Главное, чтобы все уникальные комбинации, удовлетворяющие условию, были найдены. Нужно подумать как можно использовать структуры данных для оптимизации поиска и хранения комбинаций. Например, можно ли использовать префиксы для эффективного поиска совпадений? Как вы справитесь с потенциально огромным количеством комбинаций в памяти? Задача — найти баланс между эффективностью и потреблением памяти.