Permutation für meist ausgeglichene Bipartitionen

Ich arbeite an einem Baumsuchalgorithmus, wo ich Bipartitionen von Elementen verwenden, die über ein Bitset dargestellt werden, d.h. das Bitset 1000101 repräsentiert die Bipartition {0,2,6} {1,3,4,5}.Permutation für meist ausgeglichene Bipartitionen

Im Moment ich durchlaufen alle Zweitheilungen einfach durch eine bitset Inkrementieren, dh durch alle Zweitheilungen des Satzes {0,1,2,3}, die ich von 0001 (einschließlich) bis 1000 (exklusiv)

Da mein Algorithmus gehen zu iterieren manchmal erlaubt mir, schnell zu versagen, wenn ich eine passende Zweiteilung gefunden habe, ich möchte sie so umordnen, dass ich zuerst ausgeglichenere Zweiteilungen ansehe.

So wollte ich fragen, ob jemand eine Permutation der Zahlen von 1 bis 2^k weiß, wo min (#set Bits, #unset Bits) mehr oder weniger nur abnimmt, die noch effizient berechnet werden kann .

Da dies eine Heuristik ist, suche ich nicht nach genauen Ergebnissen, nur um meinen Algorithmus etwas zu beschleunigen.

Quelle

2017-06-27 Tobias Ribizel

Gibt es eine bestimmte Geschwindigkeit, die Sie suchen? Das Finden der nächsten Partition mit der gleichen Anzahl von gesetzten Bits ist eine Operation der Ordnung "k". Sie könnten das verwenden, um alle 'k // 2'-Partitionen zu durchlaufen, dann' k // 2-1' usw. Ist das schnell genug? –

Je nachdem, was Sie versuchen, kann ein * Gray-Code * hilfreich sein (https://en.wikipedia.org/wiki/Gray_code). Der Abschnitt über * monotone Gray-Codes * scheint relevant zu sein. –

@RoryDaulton Vielen Dank, Ihr Kommentar hat mich definitiv in die richtige Richtung geführt. –

Rorys Kommentar hat mich in der richtigen Richtung:

Wenn wir mit einer festen Anzahl von Einsen in der bitset starten, können wir einfach durchlaufen alle von ihnen einig Bit-twiddling Hacks verwenden.

Starten von 0...01...1 zuerst mit k/2 diejenigen, dann mit k/2 - 1, k/2 - 2 und so weiter.
Für jeden Anfangswert, durchlaufen Sie alle möglichen Permutationen des Bitsets mit , bis wir die Grenze unseres Bitsets erreichen.

Eine einfache Implementierung könnte wie folgt aussehen (für k <= 63)

for (int i = k/2; i > 0; --i) { 
    // start with 0 ... 0 1 ... 1 (i times) 
    unsigned int v = (1 << i) - 1; 
    // first bitset that doesn't represent a valid bipartition 
    unsigned int end = 1 << k; 
    // without this, we would count some bipartitions twice for k even 
    if (k % 2 == 0 && i == k/2) end >>= 1; 
    while(v < end) { 
     // do something with v... 
     // iterate to the lexicographically next permutation 
     unsigned int t = v | (v - 1); 
     v = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1)); 
    } 
}

Quelle

2017-06-27 14:57:43

Permutation für meist ausgeglichene Bipartitionen

Antwort

Verwandte Themen