Какой более быстрый способ найти все уникальные перегородки целого числа и их веса? ⇐ Python

[Anonymous]

Я видел множество сообщений по этой теме, но ни один из них не является именно тем, что я ищу.

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

[(1, 1, 1, 1, 1, 1),
(1, 1, 1, 1, 2),
(1, 1, 1, 2, 1),
(1, 1, 1, 3),
(1, 1, 2, 1, 1),
(1, 1, 2, 2),
(1, 1, 3, 1),
(1, 1, 4),
(1, 2, 1, 1, 1),
(1, 2, 1, 2),
(1, 2, 2, 1),
(1, 2, 3),
(1, 3, 1, 1),
(1, 3, 2),
(1, 4, 1),
(1, 5),
(2, 1, 1, 1, 1),
(2, 1, 1, 2),
(2, 1, 2, 1),
(2, 1, 3),
(2, 2, 1, 1),
(2, 2, 2),
(2, 3, 1),
(2, 4),
(3, 1, 1, 1),
(3, 1, 2),
(3, 2, 1),
(3, 3),
(4, 1, 1),
(4, 2),
(5, 1),
(6,)]
< /code>
Теперь нотация очень низкая энтропия, во-первых, каждое появление числа увеличивает размер конкретного разделения, это неэффективно, и трудно подсчитать входы чисел, когда они повторяются много раз. Я хочу заменить все входы числа на двухэлементный кортеж, в котором первым элементом является число, а второе-это количество, например (1, 1, 1, 1, 1, 1) 

эквивалентно (1, 6) , они оба содержат одну и ту же информацию, но одна из них явно более кратков. Пять разделов, которые содержат четыре 1 и один 2, они считаются пятью отдельными элементами. Это также неэффективно, поскольку добавление является коммутативным, изменение порядка чисел не изменяет результат, поэтому все они эквивалентны, все они являются одним и тем же элементом. < /P>
Однако, если мы заменим все пять только одним элементом, мы теряем информацию.

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

Counter({((1, 2), (2, 2)): 6,
((1, 1), (2, 1), (3, 1)): 6,
((1, 4), (2, 1)): 5,
((1, 3), (3, 1)): 4,
((1, 2), (4, 1)): 3,
((1, 1), (5, 1)): 2,
((2, 1), (4, 1)): 2,
((1, 6),): 1,
((2, 3),): 1,
((3, 2),): 1,
((6, 1),): 1})

Поэтому я хочу, чтобы результат был счетчиком , в котором ключи-это уникальные разделы, а значения-то, сколько способов можно было организовать числа. Оказывается, довольно эффективно. < /P>
Сначала это реализация, которая выводит в стандартном формате, я публикую ее здесь для сравнения: < /p>
def partitions(number: int) -> list[tuple[int, ...]]:
result = []
stack = [(number, ())]

while stack:
remaining, path = stack.pop()
if not remaining:
result.append(path)
else:
stack.extend((remaining - i, path + (i,)) for i in range(remaining, 0, -1))

return result
< /code>
Требуется 582 миллисекунд, чтобы найти все разделы 20 в Cpython и 200 миллисекунд в Pypy3: < /p>
cpython < /p>
In [22]: %timeit partitions(20)
582 ms ± 4.22 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
< /code>
pypy3 < /p>
In [36]: %timeit partitions(20)
199 ms ± 3.17 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
< /code>
Теперь подход Bruteforce с меморизацией, который выводит в предполагаемом формате: < /p>
PARTITION_COUNTERS = {}

def partition_counter(number: int) -> Counter:
if result := PARTITION_COUNTERS.get(number):
return result

result = Counter()
for i in range(1, number):
for run, count in partition_counter(number - i).items():
new_run = []
added = False
for a, b in run:
if a == i:
new_run.append((a, b + 1))
added = True
else:
new_run.append((a, b))

if not added:
new_run.append((i, 1))

result[tuple(sorted(new_run))] += count

result[((number, 1),)] = 1
PARTITION_COUNTERS[number] = result
return result
< /code>
cpython < /p>
In [23]: %timeit PARTITION_COUNTERS.clear(); partition_counter(20)
10.4 ms ± 72.1 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
< /code>
pypy3 < /p>
In [37]: %timeit PARTITION_COUNTERS.clear(); partition_counter(20)
9.75 ms ± 58.3 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
< /code>
Требуется всего 10 миллисекунд, чтобы найти все разделы 20, намного, намного быстрее, чем первая функция, а Pypy3 не делает его быстрее. < /p>
Но как мы можем добиться большего? В конце концов, я просто использую грубую силу, я знаю, что есть много интеллектуальных алгоритмов для целочисленного разделения, но ни один из них не генерирует выходы в предполагаемом формате.

Подробнее здесь: https://stackoverflow.com/questions/795 ... heir-weigh