Einen besseren Weg zum Zählen von Matrizen finden

Berechnet in ungefähr einer Minute auf meinem Rechner mit CPython 3.3:

Code, basierend auf Memo-Inclusion-Exclusion:

Sie können diesen unter "besser als nichts" ablegen ;-) Hier ist einfacher Python3-Code, der das Problem ein wenig umdenkt. Vielleicht könnten nackte Tricks es wesentlich beschleunigen, aber schwer zu sehen, wie.

1. "Eine Zeile" ist hier eine Ganzzahl in range(2**n) . Also das Array ist nur ein Tupel von ganzen Zahlen.
2. Aus diesem Grund ist es einfach, alle Arrays zu generieren, die in der Zeilenpermutation über combinations_with_replacement() eindeutig sind. Dies reduziert die Anzahl der Fahrten auf der äußeren Schleife von 2**(n**2) auf (2**n+n-1)-choose-n) . Eine enorme Reduktion, aber immer noch ...
3. Ein vorberechnetes Diktat bildet Paare von Zeilen (die Paare von ganzen Zahlen hier bedeuten!) mit ihrer Vektorsumme als Tupel ab. Daher sind beim Testen keine Array-Operationen erforderlich, außer um die Tupel auf Gleichheit zu testen. Mit etwas mehr Tricks könnten die Tupel als (etwa) base-3-Integer codiert werden, wodurch der Inner-Loop-Test auf den Vergleich zweier Integer reduziert wird, die aus einem Paar von Dict-Lookups abgerufen werden.
4. Die Zeit und der Platz, die für dieses vorberechnete Diktat benötigt werden, sind relativ trivial. Daher wurde kein Versuch unternommen, diesen Teil zu beschleunigen.
5. Die innere Schleife wählt die Zeilenindizes 4 zu einem Zeitpunkt aus, anstatt dass ihr Schleifenpaar jeweils zwei Indizes gleichzeitig auswählt. Es ist schneller, alle 4 in einem Zug zu machen, zum großen Teil, weil es keine Notwendigkeit gibt, Paare mit einem doppelten Index auszusondern.

Hier ist der Code:

Das reichte aus, um Ergebnisse über n = 6 zu finden, obwohl es lange gedauert hat, das letzte zu beenden (wie lange? weiß nicht - habe es nicht - in der Größenordnung von einer Stunde - "long") Zeit "ist relativ ;-)):

BEARBEITEN - Entfernen einer unnötigen Indizierung

Eine schöne Beschleunigung durch Ändern der Hauptfunktion zu diesem:

BEARBEITEN - beschleunigt den Summentest

Das ist unbedeutend, aber da dies der bisher beste Ansatz auf dem Tisch zu sein scheint, könnte es auch etwas mehr aus ihm herausquetschen. Wie zuvor bemerkt, kann, da jede Summe in range(3) ist, jedes Tupel von Summen durch eine ganze Zahl ersetzt werden (Betrachten des Tupels als Geben der Ziffern einer Basis-3-Ganzzahl). Ersetzen Sie calc_row_pairs() like so:

Ich bin sicher, dass numpy einen viel schnelleren Weg hat, aber die von calc_row_pairs() benötigte Zeit ist unbedeutend, also warum? Übrigens, der Vorteil dabei ist, dass die Inner-Loop == -Tests von dem Vergleich von Tupeln mit dem Vergleich von kleinen ganzen Zahlen abweichen. Plain Python profitiert davon, aber ich wette, Pypy könnte noch mehr davon profitieren.

Keine direkte Antwort auf Ihre Frage, aber wie gesagt, ich glaube, Sie können sicher vergessen, alle Matrizen für jedes signifikante n erschöpfend zu testen. Das Problem eignet sich jedoch gut für eine stochastische Charakterisierung. Interessanterweise sind Tripelsummen unter bestimmten Bedingungen häufiger als Doppelsummen! Die Wahrscheinlichkeit, einen Treffer zu bekommen, scheint eine ziemlich einfache (monotone) Funktion von sowohl n als auch m zu sein, aber keine Überraschungen.