Jaki jest najszybszy algorytm komputerowy dla wszystkich permutacji liczby binarnej o tej samej wadze hammingowej?

Question

Potrzebuję algorytmu do obliczenia wszystkich permutacji o stałej wielkości liczby binarnej o danej wadze hammingowej. Na przykład, jeśli masa jest Hamminga 2 i wielkość binarnego 4 I są te wyjścia:

0011 
0110 
0101 
1100 
1010 
1001 

Liczba takich kombinacjach oblicza się jako C(n,r) w tym przykładzie C(4,2) która 6.

Uwaga możesz to rozwiązać, zwiększając liczbę od 0 do 2^n i sprawdzając, czy liczba jest poprawna. Jednak nie jest to szybkie rozwiązanie. Rozważam rozwiązanie problemu za pomocą klasy bitset w C++, i muszę zwiększyć N.

Chcę dodać, że istnieje oczywisty algorytm rekursywny dla tego problemu. Ze względu na przepełnienie stosu, nie jest to dobra odpowiedź. Otrzymałem dobrą odpowiedź od włamań Gospera. Chociaż muszę skalować dane wejściowe i może później użyć do tego implementacji MPI, potrzebuję skalowalnej biblioteki. Niepodpisany int nie jest wystarczająco duży i wolałbym skalowalną i szybką bibliotekę jak bitset. Rozwiązanie nie ma tutaj zastosowania, gdy nie ma żadnych dodatków w bibliotece bitsetów. jakiekolwiek inne rozwiązanie?

Answer 1

można wdrożyć "leksykograficznie następny bit-permutacji" używając Gosper's Hack:

unsigned int v; // current permutation of bits 
unsigned int w; // next permutation of bits 

unsigned int t = v | (v - 1); // t gets v's least significant 0 bits set to 1 
// Next set to 1 the most significant bit to change, 
// set to 0 the least significant ones, and add the necessary 1 bits. 
w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1)); 

Lub jeśli nie masz ctz (_BitScanForward na MSVC),

unsigned int t = (v | (v - 1)) + 1; 
w = t | ((((t & -t)/(v & -v)) >> 1) - 1); 

Answer 2

może generować je w następujący sposób:

1. Początkowo aby wektora z N - zera R na początku i r te w końcu (0011 dla n = 4 i R = 2) .

2. Następnie powtórz następującą procedurę:

   1. Znajdź na prawo tak, że zerowy znajduje się na lewo od niego. Jeśli takiego nie ma, skończyliśmy.
   2. Przesunąć w lewo (o jedną pozycję, czyli zamienić na zero).
   3. Przenieś wszystkie znajdujące się po prawej stronie na sam koniec wektora.
      Na przykład, jeśli mamy 0110, najpierw przesuniemy prawą, która może być przesunięta w lewo i otrzymamy 1010, następnie przesuwamy wszystkie z prawej strony na koniec wektora i otrzymujemy 1001.

To rozwiązanie ma O(C(n, r) * n) czasowej złożoności. Jeszcze jedna cecha tego rozwiązania: generuje elementy w porządku leksykograficznym.