Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Python задача .

Soul Leveling Ученик (70), на голосовании 2 дня назад
Нужно написать функцию на Python, которая принимает на вход список из N кортежей, где каждый кортеж содержит M целых чисел. Функция должна найти все уникальные комбинации чисел, которые встречаются во всех кортежах хотя бы один раз, с учетом их порядка внутри кортежа. При этом, комбинация может быть любой длины от 1 до M, но должна состоять из последовательных элементов кортежа. Важно, чтобы функция была максимально эффективной по времени и памяти, так как N и M могут быть очень большими (допустим, N = 10000, M = 100). Оптимизация критически важна. Кроме того, функция должна корректно обрабатывать случаи, когда входные данные содержат дубликаты кортежей или пустые кортежи

Тестовые данные

[(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)] - Этот набор данных для проверки производительности.

Учтите, что порядок элементов в возвращаемом списке не важен. Главное, чтобы все уникальные комбинации, удовлетворяющие условию, были найдены. Нужно подумать как можно использовать структуры данных для оптимизации поиска и хранения комбинаций. Например, можно ли использовать префиксы для эффективного поиска совпадений? Как вы справитесь с потенциально огромным количеством комбинаций в памяти? Задача — найти баланс между эффективностью и потреблением памяти.
Голосование за лучший ответ
wrg ergrge Знаток (355) 1 месяц назад
 def find_unique_combinations(tuples): 
if not tuples or any(not t for t in tuples):
return []

seen = set()
result = set()

for tup in tuples:
for i in range(len(tup)):
for j in range(i + 1, len(tup) + 1):
comb = tup[i:j]
if comb in seen:
result.add(comb)
seen.add(comb)

return sorted(result, key=lambda x: (-len(x), x))
Ингерманландец Мастер (2273) 1 месяц назад
 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}")
Лев Михайлов Мыслитель (6898) 1 месяц назад
Функция должна найти все уникальные комбинации чисел, которые встречаются
во всех кортежах хотя бы один раз
[(1, 2, 3), (4, 2, 3), (1, 2, 5)] - ожидаемый результат: [(2, 3), (2), (3)]
Но ведь 3 нет в 3 кортеже (1, 2, 5), тогда почему она попала в ответ?
Soul LevelingУченик (70) 1 месяц назад
Да, неточность. На самом деле, исходя из примеров, логика должна быть такой:

Найти все возможные последовательные комбинации чисел в каждом кортеже. Например, для кортежа (1, 2, 3) это будут (1), (2), (3), (1, 2), (2, 3), (1, 2, 3).
Из всех найденных комбинаций оставить только те, которые встречаются хотя бы в одном кортеже. Тут важно уточнение: комбинация считается одинаковой, если она состоит из одинаковых чисел и идет в том же порядке.
Из оставшихся комбинаций выбрать те, которые присутствуют во всех кортежах. То есть, если комбинация (2, 3) есть в первом и втором кортеже, но нет в третьем, то она не входит в итоговый результат.
Soul Leveling, проектируете задачи для собеседований? В какую компанию? Очень сырые формулировки, очень. Если это ВК, то не удивлюсь от слова "совсем".
Похожие вопросы