Générer toutes les chaînes binaires de longueur n avec k bits définis

https://stackoverflow.com/questions/1851134

13-09-2019
|

Question

Quel est le meilleur algorithme pour trouver toutes les chaînes binaires de longueur n contenant k bits fixés? Par exemple, si n = 4 et k = 3, il y a ...

Je besoin d'un bon moyen de générer ces données tout n et tout k donc je préfère que cela se fasse avec des chaînes.

La solution

Cette méthode va générer tous les nombres entiers avec exactement N bits '1'.

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

Calculer la permutation de bits lexicographique suivant

Supposons que nous ayons un motif de N bits mis à 1 dans un nombre entier et nous voulons   la prochaine permutation de N 1 bits en un sens lexicographique. Pour   Par exemple, si N est égal à 3 et le motif de bits est 00010011, les motifs suivants   serait 00010101, 00010110, 00011001, 00011010, 00011100, 00100011,   et ainsi de suite. Ce qui suit est un moyen rapide de calculer la prochaine   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));
Le compilateur GNU C __builtin_ctz(v) intrinsèque pour les x86 renvoie le nombre de zéros à droite. Si vous utilisez Microsoft compilateurs pour x86, le intrinsèque est _BitScanForward. Ces deux émettent un bsf instruction, mais les équivalents peuvent être disponibles pour d'autres architectures. Sinon, envisagez d'utiliser l'une des méthodes de comptage du les bits zéro consécutifs mentionné précédemment. Voici une autre version a tendance à être plus lent en raison de son opérateur de division, mais il ne besoin de compter les zéros de fin.
unsigned int t = (v | (v - 1)) + 1;
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);
Merci à Dario Sneidermanis de l'Argentine, qui a fourni ce le 28 Novembre 2009.

Autres conseils

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

Explication:

Pour l'essentiel, nous devons choisir les positions des bits 1. Il y a des façons de choisir n k de choisir k bits parmi n bits au total. itertools est un module agréable qui fait cela pour nous. itertools.combinations (plage (n), k) choisiront k bits de [0, 1, 2 ... n-1] et il est juste une question de la construction de la chaîne donnée ces indices de bits.

Puisque vous n'utilisez pas Python, regardez le pseudo-code pour itertools.combinations ici:

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

doit être facile à mettre en œuvre dans toutes les langues.

Oublier la mise en œuvre ( "soit fait avec des cordes" est évidemment un la mise en œuvre question!) - pensez à la, pour l'amour de Pete algorithme ... comme , votre premier TAG, l'homme!

Qu'est-ce que vous cherchez est toutes les combinaisons d'éléments K sur un ensemble de N (les indices, 0 à N-1, des bits de réglage). C'est évidemment plus simple d'exprimer récursive, par exemple, pseudocode:

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)

i.e., le premier élément est présent ou absent. Le cas échéant, vous avez K-1 à gauche pour aller (de la queue aka tous mais Sapins), en cas d'absence, encore K à gauche pour aller

langages fonctionnels pattern-matching comme SML ou Haskell peut être préférable d'exprimer ce pseudo-code (ones de procédure, comme mon grand Python d'amour, peut en fait masquer le problème trop profondément en incluant des fonctionnalités trop riches, comme itertools.combinations, qui fait tout le travail dur pour vous et CACHE donc de vous!).

Qu'est-ce qui vous le plus familier, à cet effet - Scheme, SML, Haskell, ...? Je serai heureux de traduire le pseudocode ci-dessus pour vous. Je peux le faire dans des langages tels que Python aussi, bien sûr - mais depuis le point est vous amener à comprendre les mécanismes de cette mission de devoirs, je ne vais pas utiliser la fonctionnalité trop riche, comme itertools.combinations, mais plutôt récursion (et récursion -élimination, si nécessaire) sur des primitives plus évidentes (telles que la tête, la queue, et la concaténation). Mais s'il vous plaît ne laissez-nous savoir quelle langue comme pseudocode vous êtes le plus familier avec! (Vous ne comprenez que le problème est identique, vous déclarez equipotent pour « obtenir toutes les combinaisons d'éléments de K sur ou plage (N) », non?).

Cette méthode C # retourne un recenseur qui crée toutes les combinaisons. Comme il crée les combinaisons que vous les énumérer, il utilise seulement l'espace de la pile, il est donc pas limité par l'espace mémoire dans le nombre de combinaisons qu'il peut créer.

Ceci est la première version que je suis venu avec. Il est limité par l'espace de pile à une longueur d'environ 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;
      }
    }
  }
}

Ceci est la deuxième version, qui utilise une scission binaire plutôt que scission du premier caractère, il utilise la pile beaucoup plus efficace. Il est seulement limité par l'espace mémoire pour la chaîne qu'il crée à chaque itération, et je l'ai testé jusqu'à une longueur de 10.000.000:

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

Un problème avec la plupart des solutions standard à ce problème est que l'ensemble des chaînes est généré, puis ceux-ci sont itérés, qui peut épuiser la pile. Il devient rapidement difficile à manier pour tout mais les plus petits ensembles. De plus, dans bien des cas, seul un échantillonnage partiel est nécessaire, mais la norme des solutions (récursives) hachez généralement le problème en morceaux qui sont fortement biaisées dans une direction (par exemple. Envisager toutes les solutions avec un bit de départ à zéro, puis tous les solutions avec un bit de départ).

Dans de nombreux cas, il serait plus souhaitable de pouvoir passer une chaîne de bits (en spécifiant de sélection d'éléments) à une fonction et faites-le revenir la prochaine chaîne de bits de telle manière à avoir un changement minime (ce qui est connu comme un code de Gray) et d'avoir une représentation de tous les éléments.

Donald Knuth couvre toute une série d'algorithmes pour cela dans son 3A Fascicule, section 7.2.1.3. Génération toutes les combinaisons

Il y a une approche pour aborder l'algorithme itératif Gray Code pour toutes les façons de choisir k éléments de n http://answers.yahoo.com/question/index?qid=20081208224633AA0gdMl avec un lien vers le code PHP Listed dans le commentaire (cliquez pour développer) au bas de la page.

Un algorithme qui devrait fonctionner:

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)

Bonne chance!

D'une certaine manière, plus générique la fonction ci-dessous vous donnera toutes les combinaisons possibles d'index pour un N choisir problème K que vous pouvez ensuite appliquer à une chaîne ou tout autre chose:

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

Un possible 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')])

.. où k est le nombre de 1s dans "0111".

Le module itertools explique équivalents pour ses méthodes; voir l'équivalent pour la .

Je voudrais essayer récursivité.

Il y a des chiffres n avec k d'entre eux 1s. Une autre façon de voir cela est la séquence de k + 1 emplacements avec 0s n-k répartis entre eux. Cela est, (une série de 0s suivie d'un 1) k fois, puis suivi par une autre série de 0s. Chacune de ces pistes peut être de longueur nulle, mais la longueur totale doit être n-k.

représenter cela comme une matrice de k + 1 nombres entiers. Convertir en une chaîne au bas de la récursion.

appeler récursivement à la profondeur n-k, un procédé qui incrémente un élément de la matrice avant qu'un appel récursif et décrémente ensuite, k + 1 fois.

A la profondeur de n-k, la sortie de la chaîne.

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

Il a été un moment que je l'ai fait Java, donc il y a probablement quelques erreurs dans ce code, mais l'idée devrait fonctionner.

sont des chaînes plus rapide qu'un tableau de ints? Toutes les solutions pour les chaînes Préfixer résultent probablement d'une copie de la chaîne à chaque itération.

Alors sans doute la façon la plus efficace serait un tableau de int ou char que vous ajoutez à. Java a des conteneurs efficaces cultivables, non? Utilisez que, si elle est plus rapide que la chaîne. Ou si BigInteger est efficace, il est certainement compact, puisque chaque bit ne prend que peu, pas un octet tout ou int. Mais à itérer sur les bits dont vous avez besoin pour un peu et le masque, et BitShift le masque à la position suivante bits. Donc, probablement plus lente, à moins compilateurs JIT sont bons que ces jours-ci.

Je poste ce commentaire sur un un à la question initiale, mais mon karma est pas assez élevé. Désolé.

Python (style fonctionnel)

En utilisant la python de itertools.combinations vous pouvez générer tous les choix de notre k de n et cartographier ces choix à un tableau binaire avec 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)]

Exemple d'utilisation:

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

cette question (où vous devez itérer sur tous les submasks dans l'ordre croissant de leur nombre de bits de set), qui a été marqué comme un double de cela.

Nous pouvons simplement itérer sur tous les submasks les ajouter à un vecteur et le tri en fonction du nombre de bits de réglage.

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

Une autre façon serait de parcourir tous les temps submasks N et ajoutez un numéro au vecteur si le nombre de bits défini est égal à i dans la ième itération.

Les deux méthodes ont la complexité de O (n * 2 ^ n)

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow