Generierende Sequenz von binären Strings mit k Einsen, wobei der nächste String sich in zwei Ziffern unterscheidet

Sie sollten meinen Blogbeitrag zu dieser Art von Permutation lesen (unter andere Dinge), um mehr Hintergrundwissen zu bekommen - und folgen Sie den Links dort.

Hier ist eine Version meines lexikographischen Permutationsgenerators, die nach der Generierungssequenz von Steinhaus-Johnson-Trotter Permutationsgeneratoren erstellt wurde, die wie gewünscht funktioniert:

Die Ausgabe von dem obigen Programm ist zum Beispiel die folgende:

Ich denke, Sie können dies mit Rekursion einrichten.

Ich wurde von der folgenden Identität inspiriert:

Wir definieren also eine Funktion F (n, k), die die angeforderte Sequenz erzeugt (d. h. eine Sequenz von binären Strings der Länge n mit exakt gesetzten k Bits, so dass aufeinanderfolgende Strings um zwei Bits abweichen).

Man beachte zunächst, dass wir die Spalten von F (n, k) nach Belieben neu anordnen können und ein anderes, gleichgültiges F (n, k) erzeugen können.

Die obige Identität legt nahe, dass wir F (n, k) mit F (n-1, k-1) und F (n-1, k) aufbauen. Sei A Strings, die durch Umordnen der Spalten von F (n-1, k-1) erhalten werden, so dass die letzte Zeichenfolge in k-1 1 s endet, und dann jeweils 1 addiert wird. Sei B die Zeichenkette, die man erhält, indem man die Spalten von F (n-1, k) neu anordnet, so dass die erste Zeichenkette in k 1 s endet und dann jeweils 0 addiert. Dann ist F (n, k) nur die Verkettung von A und B. Das Ergebnis ist ein gültiges F (n, k), da sich die Strings intern um A und B um zwei Bits und um die letzte Kette von A und dem ersten unterscheiden String von B unterscheiden sich um zwei Bits (das k + 1 bis zum letzten Bit und das letzte Bit).

Ich werde ein Beispiel mit n = 5, k = 2 zeigen. Wir erhalten durch Rekursion die folgenden zwei F-Sequenzen:

um A zu machen, vertausche die erste und letzte Spalte von F (4,1) und füge 1 zu jedem hinzu:

Um B zu machen, sind keine Spalten-Swaps notwendig, daher fügen wir einfach eine 0 zu jeder Zeile von F (4,2) hinzu:

Dann ist F (5,2) nur die Verkettung von A und B.

1. Nehmen Sie einen Gray-Code (Reihenfolge, in der sich jede fortlaufende Nummer um ein Bit unterscheidet) .
2. Ein weiteres Bit voranstellen und zwischen 0 und 1 .
umkehren

Dies erzeugt genau die Hälfte der n-Bit-Strings. Das ist das Maximum, das du bekommen kannst - die andere Hälfte kann nicht erzeugt werden, weil zum Beispiel beginnend mit einer Kette aller 0 's und zwei Bits gleichzeitig ändern, wird immer eine gerade Anzahl von 1 ' sein s.