Ich habe ein etwas mathematisch orientiertes Problem. Ich habe eine Reihe von Bitfeldern und möchte berechnen, welche Teilmenge von ihnen zu xor zusammen, um ein bestimmtes anderes Bitfeld zu erreichen, oder wenn es keine Möglichkeit gibt, zu entdecken, dass keine solche Teilmenge existiert.
Ich würde das lieber mit einer freien Bibliothek als mit Originalcode machen, und ich bevorzuge etwas mit Python-Bindings (mit den integrierten Math-Bibliotheken von Python wäre das auch akzeptabel, aber ich möchte das portieren zu mehreren Sprachen schließlich). Es wäre auch gut, den Speicher nicht zu nehmen, wenn man jedes Bit auf sein eigenes Byte erweitern möchte.
Noch eine Klarstellung: Ich brauche nur eine einzige Lösung. Meine Matrizen sind das Gegenteil von spärlich. Ich bin sehr daran interessiert, die Laufzeit auf ein absolutes Minimum zu beschränken, daher ist die Verwendung algorithmisch anspruchsvoller Methoden zum Invertieren von Matrizen stark bevorzugt. Außerdem ist es sehr wichtig, dass das spezifizierte Bitfeld das ausgegebene ist, also eine Technik, die nur eine Untermenge findet, die xor bis 0 nicht ganz schneidet.
Und ich bin mir generell der Gauss'schen Eliminierung bewusst. Ich versuche, das von Grund auf zu vermeiden!
cross-posted zu mathoverflow, weil nicht klar ist, wo der richtige Ort für diese Frage ist - Ссылка
Mathematisch gesprochen kann XOR von zwei Bits als Addition in F_2-Feld behandelt werden.
Sie möchten einen Satz von Gleichungen in einem F_2-Feld lösen. Für vier Bitfelder mit Bits (a_0, a_1, ... a_n), (b_0, b_1, ..., b_n), (c_0, c_1, ..., c_n), (r_0, r_1, ..., r_n ), erhalten Sie Gleichungen:
%Vor%(wo Sie nach x, y, z suchen).
Sie könnten dies als ein einfaches ganzzahliges lineares Problem mit glpk , wahrscheinlich lp_solve programmieren (aber ich erinnere mich nicht, ob es passt). Diese können jedoch sehr langsam arbeiten, da sie versuchen, ein viel allgemeineres Problem zu lösen.
Nachdem Sie eine Weile gegoogelt haben, scheint diese Seite ein guter Anfang zu sein, um nach Code zu suchen . Von Beschreibungen scheint es, dass Dixon und LinBox gut passen könnten.
Wie auch immer, ich denke, bei mathoverflow zu fragen, könnte Ihnen genauere Antworten geben. Wenn ja, verlinke deine Frage hier.
Update: Sagemath verwendet M4RI zur Lösung dieses Problems. Dies macht es (für mich) eine sehr gute Empfehlung.
Bei kleinen Instanzen, die leicht in den Speicher passen, löst dies nur ein lineares System über F_2 aus, also versuchen Sie die Mod-2-Gaußsche Eliminierung. Für sehr große Sparse-Instanzen, wie sie in Factoring- (Sieb-) Algorithmen vorkommen, suchen Sie den Wiedemann-Algorithmus auf.
Es ist möglich, mehrere Untermengen xor auf denselben Wert zu setzen; interessiert es dich, alle Teilmengen zu finden?
Ein vielleicht schwerfälliger Ansatz wäre es, das Powerset von Bitfeldern zu filtern. In Haskell:
%Vor%Nicht sicher, ob es einen Weg gibt, dies zu tun, ohne das Powerset zu erzeugen. (Im schlimmsten Fall ist es möglich, dass die Lösung tatsächlich das gesamte Powerset ist).
Nach Liori's Antwort oben haben wir ein lineares Gleichungssystem (in Modulo 2):
%Vor%Gaußsche Eliminierung kann verwendet werden, um das System zu lösen. In Modulo 2 wird die Additionszeilenoperation zu einer XOR-Operation. Es ist viel einfacher, dies rechnerisch zu tun, als einen generischen linearen Systemlöser zu verwenden.
Also, wenn a0 gleich Null ist, tauschen wir eine Zeile mit einer 1 in der a-Position aus. Führen Sie dann ein XOR (mit der Zeile 0) für eine beliebige andere Zeile durch, bei der das "a" -Bit eine 1 ist. Wiederholen Sie dann die Verwendung von Zeile 1 und Spalte b, dann Zeile 2 Spalte c, etc.
Wenn Sie in der r-Spalte eine Reihe von Nullen mit einem Wert ungleich null erhalten, dann die Teilmenge DNE.
Tags und Links math