Generieren Sie alle binären Strings der Länge n mit k Bits

StackOverflow https://stackoverflow.com/questions/1851134

Frage

Was ist der beste Algorithmus alle binären Strings der Länge n zu finden, die k Bits enthalten? Wenn beispielsweise n = 4 und k = 3 gibt es ... 

0111
1011
1101
1110

Ich brauche eine gute Möglichkeit, diese alle n und all k gegeben zu erzeugen, so dass ich es würde es vorziehen, mit Streichern zu tun.

War es hilfreich?

Lösung

Diese Methode wird alle ganzen Zahlen mit genau N '1' Bits erzeugen.

https://graphics.stanford.edu/~seander/bithacks.html #NextBitPermutation

  

Berechnen Sie die lexikographisch nächsten Bitpermutation

     

Angenommen, wir ein Muster von N Bits auf 1 gesetzt, in einer ganzen Zahl haben, und wir wollen   die nächste Permutation von N 1 Bits in einem lexikographischen Sinne. Zum   Wenn beispielsweise N = 3 ist und das Bitmuster ist 00010011, die nächsten Muster   würde 00010101, 00010110, 00011001, 00011010, 00011100, 00100011,   und so weiter. Im Folgenden ist eine schnelle Möglichkeit, die nächste zu berechnen   Permutation. 

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));
     

Die __builtin_ctz(v) GNU C Compiler für intrinsische x86 CPUs gibt die Anzahl der Nullen. Wenn Sie mit Microsoft-Compiler für   x86, ist die intrinsische _BitScanForward. Diese emittieren sowohl ein bsf   Anweisung, aber Äquivalente für andere Architekturen zur Verfügung.   Wenn nicht, dann betrachten die Verwendung eines des Verfahrens zum Zählen   aufeinanderfolgende Null-Bits bereits erwähnt. Hier ist eine andere Version, die   neigt dazu, wegen seines Divisionsoperators langsamer zu sein, aber es funktioniert nicht   erfordern die nachfolgenden Nullen zu zählen. 

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

Dank Dario Sneidermanis von Argentinien, die diese am 28. November zur Verfügung gestellt 2009.

Andere Tipps

Python 

import itertools

def kbits(n, k):
    result = []
    for bits in itertools.combinations(range(n), k):
        s = ['0'] * n
        for bit in bits:
            s[bit] = '1'
        result.append(''.join(s))
    return result

print kbits(4, 3)

Output: ['1110', '1101', '1011', '0111']

Erklärung:

Im Grunde müssen wir die Positionen der 1-Bits wählen. Es gibt n k Wege der Wahl k Bits unter n gesamten Bits wählen. itertools ist ein schönes Modul, das das für uns tut. itertools.combinations (Bereich (n), k) k Bits von [0, 1, 2 ... n-1] wählen und dann ist es nur eine Frage der Zeichenfolge dieser Bit-Indizes gegeben zu bauen.

Da Sie nicht Python verwenden, sehen Sie die Pseudo-Code für itertools.combinations hier:

http://docs.python.org/library/itertools.html # itertools.combinations

Sollte einfach in jeder Sprache zu implementieren.

Vergessen Sie Implementierung ( "es mit Streichern getan wird" ist offensichtlich eine Implementierung Ausgabe!) - denken Sie an dem Algorithmus , für Pete willen ... genauso wie in, Ihrem ersten TAG, Mann!

Was Sie suchen ist alle Kombinationen von K Elemente aus einer Menge von N (die Indizes 0 bis N-1, der gesetzten Bits). Das ist offensichtlich einfachsten rekursiv auszudrücken, beispielsweise Pseudo-Code: 

combinations(K, setN):
  if k > length(setN): return "no combinations possible"
  if k == 0: return "empty combination"
  # combinations INcluding the first item:
  return (first-item-of setN) combined combinations(K-1, all-but-first-of setN)
   union combinations(K-1, all-but-first-of setN)
.

das heißt, das erste Element ist entweder vorhanden oder nicht vorhanden. Falls vorhanden, Sie haben K-1 (aus dem Schwanz aka all-but-Tannen) nach links zu gehen, wenn nicht vorhanden, noch K links gehen

Pattern-Matching-funktionale Sprachen wie SML oder Haskell kann am besten sein, diesen Pseudo-Code (Verfahren diejenigen zum Ausdruck bringen, wie mein großen Liebe Python, kann tatsächlich das Problem zu tief maskiert, indem zu reiche Funktionalität, wie itertools.combinations, die alle tut die harte Arbeit für Sie und deshalb versteckt es von Ihnen!).

Was sind Sie am besten kennen, zu diesem Zweck - Scheme, SML, Haskell, ...? Ich werde glücklich sein, die oben Pseudo-Code für Sie zu übersetzen. Ich kann es in Sprachen tun wie Python natürlich auch - aber da der Punkt wird immer Sie die Mechanik für diese Hausaufgabe zu verstehen, ich werde nicht allzu reiche Funktionalität wie itertools.combinations verwenden, sondern Rekursion (und Rekursion -Eliminierung, falls erforderlich) auf offensichtlicher Primitive (wie zum Beispiel Kopf, Schwanz und Verkettung). Aber bitte lassen Sie uns wissen, welche Pseudo-Code-ähnliche Sprache Sie am meisten vertraut mit! (Sie verstehen, dass das Problem, das Sie Zustand identisch äquipotente ist es, „alle Kombinationen von K Einzelteile zu erhalten oder Bereich (N)“, nicht wahr?).

Die C # Methode gibt einen Enumerator ab, alle Kombinationen erzeugt. Da es die Kombinationen erstellt, wie Sie sie aufzählen es verwendet nur Stack-Speicher, so ist es nicht von Speicherplatz in der Anzahl von Kombinationen beschränkt, die es schaffen kann.

Dies ist die erste Version, die ich kam mit. Es wird von dem Stapel Raum auf eine Länge von etwa 2700 begrenzt: 

static IEnumerable<string> BinStrings(int length, int bits) {
  if (length == 1) {
    yield return bits.ToString();
  } else {
    if (length > bits) {
      foreach (string s in BinStrings(length - 1, bits)) {
        yield return "0" + s;
      }
    }
    if (bits > 0) {
      foreach (string s in BinStrings(length - 1, bits - 1)) {
        yield return "1" + s;
      }
    }
  }
}

Dies ist die zweite Version, die eher eine binäre Spaltung nutzt als das erste Zeichen abspaltet, so verwendet er den Stapel wesentlich effizienter. Es ist nur durch den Speicherplatz für die Zeichenfolge begrenzt, dass es in jeder Iteration erzeugt, und ich habe es auf eine Länge von 10000000 getestet up: 

static IEnumerable<string> BinStrings(int length, int bits) {
  if (length == 1) {
    yield return bits.ToString();
  } else {
    int first = length / 2;
    int last = length - first;
    int low = Math.Max(0, bits - last);
    int high = Math.Min(bits, first);
    for (int i = low; i <= high; i++) {
      foreach (string f in BinStrings(first, i)) {
        foreach (string l in BinStrings(last, bits - i)) {
          yield return f + l;
        }
      }
    }
  }
}

Ein Problem bei vielen der Standardlösungen für dieses Problem besteht darin, dass der gesamte Satz von Saiten erzeugt wird und dann durch jene iteriert, die den Stapel erschöpfen können. Es wird schnell unhandlich für jeden, aber die kleinsten Mengen. Zusätzlich ist in vielen Fällen nur eine teilweise Abtastung benötigt wird, aber der Standard (rekursiv) Lösungen in der Regel das Problem in Stücke zerkleinern, die stark vorgespannt in eine Richtung (zB. Betrachten alle Lösungen mit einem Null-Startbit, und dann alle die Lösungen mit einem Startbit).

In vielen Fällen wäre es wünschenswert zu sein, um eine Bitkette (Angabe Elementauswahl) an eine Funktion zu übergeben und ihn zurückgeben die nächste Bit-String in einer solchen Art und Weise, wie eine minimale Änderung haben (dies ist bekannt als Gray-Code) und eine Darstellung aller Elemente haben.

Donald Knuth deckt eine ganze Reihe von Algorithmen für den in seinem Faszikel 3A, Abschnitt 7.2.1.3. Erzeugen alle Kombinationen

Es ist ein Ansatz, den iterativen Gray Code-Algorithmus für die Lösung für alle Arten der Wahl k Elemente von n http://answers.yahoo.com/question/index?qid=20081208224633AA0gdMl mit einem Link zum endgültigen PHP-Code im Kommentar aufgelistet (klicken Sie zum Vergrößern) am unteren Rand der Seite.

Ein Algorithmus, der sollte funktionieren: 

generate-strings(prefix, len, numBits) -> String:
    if (len == 0):
        print prefix
        return
    if (len == numBits):
        print prefix + (len x "1")
    generate-strings(prefix + "0", len-1, numBits)
    generate-strings(prefix + "1", len-1, numBits)

Viel Glück!

In einer allgemeineren Art und Weise, die unten Funktion gibt Ihnen alle möglichen Indexkombinationen für ein N wählen K Problem, das Sie dann auf einen String anwenden können, oder was auch immer: 

def generate_index_combinations(n, k):

    possible_combinations = []

    def walk(current_index, indexes_so_far=None):
        indexes_so_far = indexes_so_far or []
        if len(indexes_so_far) == k:
            indexes_so_far = tuple(indexes_so_far)
            possible_combinations.append(indexes_so_far)
            return
        if current_index == n:
            return
        walk(current_index + 1, indexes_so_far + [current_index])
        walk(current_index + 1, indexes_so_far)

    if k == 0:
        return []
    walk(0)
    return possible_combinations

Ein möglicher 1,5-Liner: 

$ python -c 'import itertools; \
             print set([ n for n in itertools.permutations("0111", 4)])'

set([('1', '1', '1', '0'), ('0', '1', '1', '1'), ..., ('1', '0', '1', '1')])

.. wo k ist die Anzahl der 1s in "0111".

Das itertools Modul erklärt Äquivalente für ihre Methoden; siehe das Äquivalent für die Permutation Methode rel="nofollow.

Ich würde versuchen, Rekursion.

Es gibt n Stellen mit k von ihnen 1s. Eine andere Möglichkeit, dies zu betrachten, ist Folge von k + 1 Schlitze mit n-k 0s unter ihnen verteilt werden. Das heißt, (ein Lauf von 0en, gefolgt durch eine 1) k-mal, dann durch einen anderen Lauf von 0en, gefolgt. Jede dieser Läufe kann seine Länge Null, aber die Gesamtlänge muss n-k sein.

Stellen Sie diese als eine Gruppe von k + 1 ganzen Zahlen. Konvertieren in einen String an der Unterseite der Rekursion.

Rekursiv ruft Tiefe n-k, ein Verfahren, das ein Element des Arrays vor dem rekursiven Aufruf inkrementiert und dann dekrementiert sie, k + 1 mal.

in der Tiefe von n-k, Ausgabe der Zeichenkette. 

int[] run = new int[k+1];

void recur(int depth) {
    if(depth == 0){
        output();
        return;
    }

    for(int i = 0; i < k + 1; ++i){
        ++run[i];
        recur(depth - 1);
        --run[i];
    }

public static void main(string[] arrrgghhs) {
    recur(n - k);
}

Es ist schon eine Weile her, seit ich Java getan haben, so gibt es wahrscheinlich einige Fehler in diesem Code, aber die Idee sollte funktionieren.

Sind Strings schneller als ein Array von ints? Alle Lösungen voranstellen, um Strings wahrscheinlich bei jeder Iteration in einer Kopie des Strings zur Folge hat.

So wohl die effizienteste Art und Weise würde ein Array von int oder char sein, die Sie anhängen. Java verfügt über effiziente Erweiterbare Container, nicht wahr? Verwenden Sie, dass, wenn es schneller als String. Oder wenn BigInteger effizient ist, dann ist es sicherlich kompakt, da jedes Bit nur ein bisschen dauert, nicht ein ganzes Byte oder int. Aber dann die Bits iterieren Sie auf & brauchen eine Bitmaske und Bitshift die Maske auf die nächste Bit-Position. So wahrscheinlich langsamer, es sei denn, JIT-Compiler sind gut, dass in diesen Tagen.

Ich würde schreiben diese einen Kommentar auf die ursprüngliche Frage, aber mein Karma ist nicht hoch genug. Es tut uns Leid.

Python (funktional)

python die itertools.combinations Verwenden Sie alle Möglichkeiten des k unserer von n generieren und diese Entscheidungen zu einem binären Array mit reduce Karte 

from itertools import combinations
from functools import reduce # not necessary in python 2.x

def k_bits_on(k,n):
       one_at = lambda v,i:v[:i]+[1]+v[i+1:]
       return [tuple(reduce(one_at,c,[0]*n)) for c in combinations(range(n),k)]

Beispiel Nutzung: 

In [4]: k_bits_on(2,5)
Out[4]:
[(0, 0, 0, 1, 1),
 (0, 0, 1, 0, 1),
 (0, 0, 1, 1, 0),
 (0, 1, 0, 0, 1),
 (0, 1, 0, 1, 0),
 (0, 1, 1, 0, 0),
 (1, 0, 0, 0, 1),
 (1, 0, 0, 1, 0),
 (1, 0, 1, 0, 0),
 (1, 1, 0, 0, 0)]

Nun für this Frage (wo Sie müssen alle Masken iterieren Reihenfolge ihrer Anzahl der gesetzten Bits in aufsteige), die als ein Duplikat dieser markiert wurde.

Wir können einfach durchlaufen alle Masken, sie zu einem Vektor hinzufügen und sortieren sie nach der Anzahl der gesetzten Bits. 

vector<int> v;
for(ll i=mask;i>0;i=(i-1)&mask)
    v.push_back(i);
auto cmp = [](const auto &a, const auto &b){
    return __builtin_popcountll(a) < __builtin_popcountll(b);
}
v.sort(v.begin(), v.end(), cmp);

Eine andere Möglichkeit, über alle Untermasken N-mal zu durchlaufen wäre und eine Nummer zu dem Vektor hinzuzufügen, wenn die Anzahl der gesetzten Bits gleich i in der i-ten Iteration.

Beide Wege haben Komplexität von O (n * 2 ^ n)

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top