Was ist ein schnellerer Weg, um alle einzigartigen Partitionen einer Ganzzahl und ihrer Gewichte zu finden? ⇐ Python

[Anonymous]

Ich habe viele Beiträge zu diesem Thema gesehen, aber keiner ist genau das, wonach ich suche.

Code: Select all

[(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>
Jetzt ist die Notation sehr niedrig entropt. Erstens erhöht jedes Auftreten der Anzahl die Größe einer bestimmten Partition, dies ist ineffizient und es ist schwierig, das Auftreten der Zahlen zu zählen, wenn sie sich um ein Vielfaches wiederholen. [url=viewtopic.php?t=14917]Ich möchte[/url] alle Vorkommen einer Zahl durch ein Zweielement-Tupel ersetzen, in dem das erste Element die Zahl ist und die zweite die Anzahl ist, beispielsweise (1, 1, 1, 1, 1, 1) 

entspricht (1, 6) , beide enthalten dieselben Informationen. Fünf Partitionen, die vier 1s und ein 2 enthalten, werden als fünf getrennte Elemente gezählt. Dies ist auch ineffizient, da die Addition kommutativ ist und die Reihenfolge der Zahlen das Ergebnis nicht ändert. Sie sind daher alle äquivalent. Sie sind alle gleich Element.

Code: Select all

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})

Ich möchte, dass das Ergebnis ein Zähler ist, in dem die Schlüssel die eindeutigen Partitionen und die Werte sind, wie viele Möglichkeiten die Zahlen angeordnet werden können. Es stellt sich heraus, dass es ziemlich effizient ist.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>
Es dauert 582 Millisekunden, um alle Partitionen von 20 in CPython und 200 Millisekunden in PYPY3 zu finden: < /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>
Jetzt der Bruteforce -Ansatz mit Memoisierung, der im beabsichtigten Format ausgeht: < /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>
Es dauert nur 10 Millisekunden, um alle Partitionen von 20, viel, viel schneller als die erste Funktion zu finden, und Pypy3 macht es nicht schneller. < /p>
Aber wie können wir es besser machen? Schließlich verwende ich nur Brute-Force, ich weiß, dass es viele intelligente Algorithmen für eine ganzzahlige Partition gibt, aber keiner von ihnen generiert Ausgaben im beabsichtigten Format.