Под вложенными 2-кортежами я имею в виду что-то вроде этого: ((a,b),(c,(d,e)))
где все кортежи состоят из двух элементов. Мне не нужны разные порядки элементов, просто разные способы их заключения в круглые скобки. Для items = [a, b, c, d]
есть 5 уникальных пар, а именно:
(((a,b),c),d)
((a,(b,c)),d)
(a,((b,c),d))
(a,(b,(c,d)))
((a,b),(c,d))
В идеальном мире я также хотел бы контролировать максимальную глубину возвращаемых кортежей, чтобы, если бы я сгенерировал все пары items = [a, b, c, d]
с max_depth=2
, он вернул бы только ((a,b),(c,d))
.
Эта проблема возникла, потому что я хотел найти способ генерировать результаты сложения некоммутативных, неассоциативных чисел. Если a+b
не равно b+a
, а a+(b+c)
не равно (a+b)+c
, каковы все возможные суммы a, b и c?
Я сделал функцию, которая генерирует все пары, но также возвращает дубликаты.
import itertools
def all_pairings(items):
if len(items) == 2:
yield (*items,)
else:
for i, pair in enumerate(itertools.pairwise(items)):
for pairing in all_pairings(items[:i] + [pair] + items[i+2:]):
yield pairing
Например, он дважды возвращает ((a,b),(c,d))
для items=[a, b, c, d]
, так как в одном случае он сначала объединяет (a,b)
, а во втором — (c,d)
.
Возврат дубликатов становится все большей и большей проблемой для большего количества элементов. С дубликатами количество пар растет факторно, а без дубликатов — экспоненциально, согласно каталонским числам (https://oeis.org/A000108).
Из-за этого я пытался придумать алгоритм, который не должен перебирать все возможности, а только уникальные. Опять же, было бы неплохо иметь контроль над максимальной глубиной, но это, вероятно, можно было бы добавить к существующему алгоритму. До сих пор мне не удалось найти подход, и я также не нашел никаких ресурсов, посвященных этой конкретной проблеме. Буду признателен за любую помощь или ссылки на полезные ресурсы.
Использование рекурсивного генератора:
items = ['a', 'b', 'c', 'd']
def split(l):
if len(l) == 1:
yield l[0]
for i in range(1, len(l)):
for a in split(l[:i]):
for b in split(l[i:]):
yield (a, b)
list(split(items))
Выход:
[('a', ('b', ('c', 'd'))),
('a', (('b', 'c'), 'd')),
(('a', 'b'), ('c', 'd')),
(('a', ('b', 'c')), 'd'),
((('a', 'b'), 'c'), 'd')]
Проверка уникальности:
assert len(list(split(list(range(10))))) == 4862
Обратный порядок элементов:
items = ['a', 'b', 'c', 'd']
def split(l):
if len(l) == 1:
yield l[0]
for i in range(len(l)-1, 0, -1):
for a in split(l[:i]):
for b in split(l[i:]):
yield (a, b)
list(split(items))
[((('a', 'b'), 'c'), 'd'),
(('a', ('b', 'c')), 'd'),
(('a', 'b'), ('c', 'd')),
('a', (('b', 'c'), 'd')),
('a', ('b', ('c', 'd')))]
С maxdepth
:
items = ['a', 'b', 'c', 'd']
def split(l, maxdepth=None):
if len(l) == 1:
yield l[0]
elif maxdepth is not None and maxdepth <= 0:
yield tuple(l)
else:
for i in range(1, len(l)):
for a in split(l[:i], maxdepth=maxdepth and maxdepth-1):
for b in split(l[i:], maxdepth=maxdepth and maxdepth-1):
yield (a, b)
list(split(items))
# or
list(split(items, maxdepth=3))
# or
list(split(items, maxdepth=2))
[('a', ('b', ('c', 'd'))),
('a', (('b', 'c'), 'd')),
(('a', 'b'), ('c', 'd')),
(('a', ('b', 'c')), 'd'),
((('a', 'b'), 'c'), 'd')]
list(split(items, maxdepth=1))
[('a', ('b', 'c', 'd')),
(('a', 'b'), ('c', 'd')),
(('a', 'b', 'c'), 'd')]
list(split(items, maxdepth=0))
[('a', 'b', 'c', 'd')]
Только что протестировано - это обеспечивает примерно 3-кратное ускорение. Если вы также кешируете результаты с помощью functools.cache
и возвращаете конкретные списки вместо создания генератора, вы получаете еще примерно 20-кратное ускорение. Увеличивается примерно с 6 секунд до 0,08 секунды для ввода размера 14.
На самом деле, я просто опубликую изменения, чтобы вы не реконструировали их из моих описаний.
@Dillon, ты абсолютно прав, я сначала думал об использовании itertools
, а потом решил использовать python без импорта;)
Полный кредит mozway для алгоритма - моя первоначальная идея состояла в том, чтобы представить спаривание в обратной польской нотации, которая не поддавалась бы следующим оптимизациям:
Во-первых, мы заменяем два вложенных цикла:
for a in split(l[:i]):
for b in split(l[i:]):
yield (a, b)
-с itertools.product, который сам будет кэшировать результаты внутреннего split(...)
вызова, а также производить сопряжение во внутреннем коде C, что будет работать намного быстрее.
yield from product(split(l[:i]), split(l[i:]))
Далее мы кэшируем результаты предыдущих вызовов split(...)
. Для этого мы должны пожертвовать ленивостью генераторов, а также обеспечить хэшируемость параметров нашей функции. В явном виде это означает создание оболочки, которая приводит входной список к кортежу, и изменение тела функции для возврата списков вместо получения.
def split(l):
return _split(tuple(l))
def _split(l):
if len(l) == 1:
return l[:1]
res = []
for i in range(1, len(l)):
res.extend(product(_split(l[:i]), _split(l[i:])))
return res
Затем мы украшаем функцию functools.cache, чтобы выполнить кеширование. Итак, собираем все вместе:
from itertools import product
from functools import cache
def split(l):
return _split(tuple(l))
@cache
def _split(l):
if len(l) == 1:
return l[:1]
res = []
for i in range(1, len(l)):
res.extend(product(_split(l[:i]), _split(l[i:])))
return res
Тестирование для следующего ввода-
test = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n']`
- выдает следующие тайминги:
Original: 5.922573089599609
Revised: 0.08888077735900879
Я также удостоверился, что результаты точно совпадают с оригиналом — порядок и все такое.
Опять же, полная заслуга mozway за алгоритм. Я только что применил несколько оптимизаций, чтобы немного ускорить его.
Только что проверила на себе, потрясающие результаты! Большое спасибо! Временная сложность просто исчезла - теперь он соединяет 15 элементов быстрее, чем раньше, чтобы соединить 5. Нужно изучить эту магию functools :D. Как бы вы разрешили контроль глубины? Если нет способа заставить это все еще работать быстро, это нормально. Это все еще очень быстро.
Вернее, ложная тревога. Я использовал timeit('all_pairings(list(range(15)))', globals=globals())
, чтобы проверить скорость. Теперь я понимаю, что, вероятно, он просто использовал кешированные результаты, когда я рассчитал время для меньшего количества элементов, и поэтому ускорение было таким резким. При попытке timeit('all_pairings([random.random()] * 15)', globals=globals())
время было гораздо более реалистичным. Все еще большое ускорение!
Просто комментарий к производительности:
yield from itertools.product(split(l[:i]), split(l[i:]))
, вероятно, обеспечит значительное ускорение по сравнению с двумя вложенными циклами for, поскольку он кэширует возвращаемое значение, а также создает пары в коде C. Все та же асимптотическая временная сложность, только быстрее.