Wählen Sie k Zahlen Summe von paarweise xor

Question

ein Bereich maximiert [l, r] (wo l < r), und eine Reihe k (wo k <= r - l), möchte ich einen Satz S von k verschiedene Zahlen in [l, r] auszuwählen, die die Summe von paarweise XORs maximiert. Wenn beispielsweise [l, r] = [2, 10] und k = 3 und wir S = {4, 5, 6} wählen, ist die Summe der XORs d(4, 5) + d(4, 6) + d(5, 6) = 1 + 1 + 2 = 4.

Hier ist mein Denken so weit: in [l, r], für jedes Bit-Index i kleiner oder gleich dem Index des höchsten gesetzte Bit in r, die Anzahl der Elemente in S^S mit dem i th Bit gesetzt ist gleich j * (k-j), Dabei ist die Anzahl der Elemente in S mit dem i Bit gesetzt. Um dies zu optimieren, wollen wir S so auswählen, dass für jedes Bit i, Sk/2 Elemente mit dem i Bit gesetzt werden. Dies ist einfach für k = 2, aber ich bin auf Verallgemeinerung dieses für k > 2 fest.

Answer 1

Auf den ersten Blick scheint es keine algebraische Lösung für dieses Problem zu geben. Ich meine, das scheint wie ein NP-schweres Problem (ein Optimierungsproblem), das in polynomieller Zeit nicht lösbar ist.

Wie fast immer möglich kann man Brute-Force durch den machbaren Raum.

Intuitiv kann ich vorschlagen, in Locality Sensitive Hashing zu suchen. In LSH versucht man normalerweise, Ähnlichkeiten zwischen zwei Sätzen zu finden. Aber in Ihrem Fall können Sie diesen Algorithmus im folgenden Sinne missbrauchen.

• Die Domain ist in wenige Buckets unterteilt.
• Sie Stichprobe zufällig im Raum [l,r].
• Hohe wahrscheinliche Punkte (große Hamming-Distanz) sind in den Eimern platziert.
• Am Ende Sie Brute Force im wahrscheinlichsten Eimer.

Am Ende ein, dass die Punkte mit großen Hammingdistanzen erwarten kann, in der gleichen Nachbarschaft sein sollten (deshalb der Name Ort Sensitive Hashing). Es ist jedoch nur eine Idee.