Generare tutte le stringhe binarie di lunghezza n con k bit impostati

Question

Qual è il miglior algoritmo per trovare tutte le stringhe binarie di lunghezza n che contiene k bit set? Ad esempio, se n = 4 e K = 3, ci sono ...

0111
1011
1101
1110

Ho bisogno di un buon modo per generare questi dati ogni n e ogni k quindi preferisco che sia fatto con le stringhe.

Answer 1

Questo metodo genererà tutti i numeri interi con esattamente N '1' bit.

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

  

Calcolare il lessicografico bit successivo permutazione

     

Supponiamo di avere un modello di N bit impostato a 1 in un intero e vogliamo   la successiva permutazione di N 1 bit in un senso lessicografico. Per   esempio, se N è 3 e la sequenza di bit è 00010011, i modelli successivi   sarebbe 00010101, 00010110, 00011001, 00011010, 00011100, 00100011,   e così via. Quanto segue è un modo veloce per calcolare il prossimo   permutazione.

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

     

Il __builtin_ctz(v) GNU C compilatore intrinseca per CPU x86 restituisce il numero di zeri finali. Se si utilizza compilatori Microsoft per   86, l'intrinseca è _BitScanForward. Questi emettono sia bsf   istruzione, ma equivalenti possono essere disponibili per altre architetture.   Se no, allora considerare l'utilizzo di uno dei metodi per il conteggio del   consecutivi bit zero menzionato in precedenza. Ecco un'altra versione che   tende ad essere più lento a causa del suo operatore divisione, ma non è così   richiedere contare gli zeri.

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

     

Grazie a Dario Sneidermanis dell'Argentina, che ha fornito il 28 novembre, 2009.

Answer 2

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']

Spiegazione:

In sostanza abbiamo bisogno di scegliere le posizioni dei 1-bit. Ci sono n scelgono modi di scegliere k k bit tra i bit n totali. itertools è un modulo bello che fa per noi. itertools.combinations (range (n), k) sceglieranno k bit da [0, 1, 2 ... n-1] e poi è solo una questione di costruzione della stringa data tali indici bit.

Dal momento che non si sta utilizzando Python, guardare la pseudo-codice per itertools.combinations qui:

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

Dovrebbe essere facile da implementare in qualsiasi lingua.

Answer 3

Dimenticatevi di implementazione ( "sia fatto con le stringhe" è ovviamente un applicazione problema!) - pensare alla algoritmo , per l'amor di Dio ... proprio come in, il tuo primo TAG, l'uomo!

Quello che stai cercando è tutte le combinazioni di K elementi su un insieme di N (indici, da 0 a N-1, dei bit set). Questo è ovviamente più semplice per esprimere in modo ricorsivo, per esempio, pseudocodice:

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)

.

vale a dire, il primo elemento è presente o assente:. Se presente, si dispone di K-1 a sinistra per andare (dalla coda alias tutti-ma-abeti), se assente, ancora K a sinistra per andare

pattern-matching linguaggi funzionali come SML o Haskell può essere migliore per esprimere questo pseudocodice (quelli procedurali, come il mio grande Python amore, potrebbe in realtà mascherare il problema troppo profondamente includendo troppo ricchi di funzionalità, come ad esempio itertools.combinations, che fa tutto il lavoro duro per voi e quindi nasconde da voi!).

Che cosa siete più familiari, per questo scopo - Scheme, SML, Haskell, ...? Sarò felice di tradurre lo pseudocodice sopra per voi. Posso farlo in linguaggi come Python anche, naturalmente - ma dal momento che il punto è sempre a capire la meccanica di questo compito a casa, non userò troppo ricco di funzionalità come itertools.combinations, ma piuttosto ricorsione (e ricorsione -eliminazione, se necessario) su più evidenti primitive (quali la testa, coda e concatenazione). Ma per favore fateci sapere cosa pseudocodice-come il linguaggio si è più familiarità con! (Tu capisci che il problema si Stato è identico equipotente di "ottenere tutte le combinazioni di articoli K fuori o gamma (N)", giusto?).

Answer 4

Questo metodo C # restituisce un enumeratore che crea tutte le combinazioni. In quanto crea le combinazioni come li si enumera utilizza solo lo spazio di stack, quindi non è limitato dalla memoria del numero di combinazioni che si può creare.

Questa è la prima versione che mi è venuta. E 'limitata dalla spazio di stack ad una lunghezza di circa 2700:

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

Questa è la seconda versione, che utilizza una scissione binaria piuttosto che dividere fuori il primo carattere, in modo che utilizza lo stack molto più efficiente. E 'limitato solo dallo spazio di memoria per la stringa che si crea in ogni iterazione, e ho provato fino ad una lunghezza di 10000000:

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

Answer 5

Un problema con molte delle soluzioni standard a questo problema è che l'intero insieme di stringhe viene generato e quindi questi sono iterati, che possono esaurire la pila. Diventa rapidamente ingombrante per qualsiasi, ma i più piccoli set. Inoltre, in molti casi, è necessaria solo una campionatura parziale, ma lo standard (ricorsivo) soluzioni generalmente tritare il problema in pezzi che sono fortemente polarizzate ad una direzione (ad es. In considerazione tutte le soluzioni con un po 'di zero iniziale e quindi tutti le soluzioni con un po 'uno di partenza).

In molti casi, sarebbe più desiderabile essere in grado di passare una stringa di bit (specifica selezione di elementi) a una funzione e farlo restituire la stringa di bit successivo in modo da avere un minimo cambiamento (questo è noto come codice Gray) e di avere una rappresentazione di tutti gli elementi.

Donald Knuth copre tutta una serie di algoritmi per questo nel suo Fascicle 3A, sezione 7.2.1.3:. Generazione di tutte le combinazioni

C'è un approccio per affrontare l'algoritmo iterativo Codice Gray per tutti i modi di scegliere k elementi da n all'indirizzo http://answers.yahoo.com/question/index?qid=20081208224633AA0gdMl con un link al codice PHP finale elencato nel commento (click per espanderla) nella parte inferiore della pagina.

Answer 6

Un algoritmo che dovrebbe funzionare:

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)

In bocca al lupo!

Answer 7

In un certo senso più generico, la funzione qui sotto vi darà tutte le possibili combinazioni di indice per un problema di N scegliere K, che si può quindi applicare ad una stringa o qualsiasi altra cosa:

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

Answer 8

Una possibile 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')])

.. dove k è il numero di 1s in "0111".

Il modulo itertools spiega equivalenti per i suoi metodi; vedere l'equivalente per il metodo di permutazione .

Answer 9

Vorrei provare ricorsione.

Non ci sono n cifre con k di loro 1s. Un altro modo per visualizzare questo è sequenza di k + 1 slot con 0s n-k distribuiti tra loro. Cioè, (una corsa di 0s seguito da un 1) k volte, poi seguita da un'altra corsa di 0s. Qualsiasi di queste prove possono essere di lunghezza zero, ma la lunghezza totale deve essere n-k.

Rappresenti questo come un array di k + 1 interi. Convertire una stringa alla parte inferiore della ricorsione.

ricorsivamente chiamare alla profondità n-k, un metodo che incrementa un elemento della matrice prima di una chiamata ricorsiva e quindi decrementa, k + 1 volte.

Alla profondità di n-k, uscita la stringa.

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

E 'stato un po' che ho fatto Java, quindi ci sono probabilmente alcuni errori in questo codice, ma l'idea dovrebbe funzionare.

Answer 10

sono stringhe più veloce di un array di int? Tutte le soluzioni Anteporre in stringhe probabilmente ad una copia della stringa ad ogni iterazione.

Quindi, probabilmente il modo più efficiente sarebbe un array di int o char che si accoda a. Java ha contenitori growable efficienti, giusto? Utilizzare che, se è più veloce di stringa. O se BigInteger è efficiente, è certamente compatto, dal momento che ogni bit richiede solo un po ', non un intero byte o int. Ma poi per scorrere i bit necessari per & mascherare un po ', e Bitshift la maschera per la posizione del bit successivo. Quindi probabilmente più lento, a meno che i compilatori JIT sono bravi a che in questi giorni.

Vorrei questo post un commento sulla questione originale, ma il mio karma non è abbastanza alta. Siamo spiacenti.

Answer 11

Python (stile funzionale)

Utilizzando python di itertools.combinations è possibile generare tutte le scelte della nostra k di n e mappare quelle scelte ad una matrice binaria con reduce

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

Esempio di utilizzo:

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

Answer 12

questo domanda (in cui è necessario iterare su tutti i submasks in ordine crescente del loro numero di bit set), che è stato contrassegnato come un duplicato di questo.

Possiamo semplicemente iterare su tutte le submasks aggiungerli ad un vettore e ordinare secondo il numero di bit impostati.

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

Un altro modo sarebbe quello di iterare su tutte le volte submasks N e aggiungere un numero al vettore se il numero di bit impostati è pari ai nell'iterazione esima.

Entrambi i metodi hanno complessità O (n * 2 ^ n)