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

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

J'ai besoin d'un bon moyen pour générer ces donné tout n et tout k donc je préfère qu'on le fasse avec des chaînes.

Pour la recherche. Faire une analyse sur la mise en correspondance d'exclusion certain nombre de graphiques et j'ai besoin d'un moyen de tester tous les possible de bord de suppressions de k arêtes.
Si vous êtes inquiet au sujet de la performance (c'est à dire un grand n et k), vous voudrez sans doute envisager une programmation dynamique de l'approche.
... surtout si c'est faisable de faire, et de mettre en cache (memoise) les résultats de l', une partie du bord de suppression sur un sous-ensemble de votre graphique, plutôt que la première génération de toutes les chaînes et ensuite de faire des choses avec eux. Cela permettrait de booster vos performances considérablement.
double possible de Création de plusieurs numéros avec un certain nombre de bits set
en.wikipedia.org/wiki/Combinatorial_number_system

InformationsquelleAutor kevmo314 | 2009-12-05

35

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

De https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
Calculer la lexicographiquement à côté peu de permutation

Supposons que nous avons un modèle de N bits mis à 1 un entier et nous voulons
la prochaine permutation de N bits à 1 dans un sens lexicographique. Pour
exemple, si N est de 3 et le modèle de bits est 00010011, la prochaine modèles
serait 00010101, 00010110, 00011001, 00011010, 00011100, 00100011,
et ainsi de suite. Le suivant est un moyen rapide de calculer la suivante
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));
```
La __builtin_ctz(v) compilateur C de GNU intrinsèque pour les Processeurs x86 retourne le nombre de zéros à droite. Si vous utilisez les compilateurs Microsoft pour
x86, la valeur intrinsèque est _BitScanForward. Ces deux émettent un bsf
l'instruction, mais les équivalents peuvent être disponibles pour d'autres architectures.
Si non, puis utilisez l'une des méthodes de comptage de l'
consécutives à zéro les bits mentionné plus tôt. Voici une autre version que
a tendance à être plus lent en raison de son opérateur de division, mais il n'a pas
exigent de compter les zéros de fin.
```
unsigned int t = (v | (v - 1)) + 1;
w = t | ((((t & -t) /(v & -v)) >> 1) - 1);
```
Grâce à Dario Sneidermanis de l'Argentine, qui a fourni ce 28 novembre 2009.
- w = v==0 ? 0 : t | ((((t & -t) / (v & -v)) >> 1) - 1); empêche la division par zéro exception!
InformationsquelleAutor finnw
17

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:

Essentiellement, nous devons choisir les positions de l'1-bits. Il y a n façons de choisir k de choisir les k bits de n nombre total de bits. itertools est une belle module qui fait ça pour nous. itertools.combinaisons(range(n), k) feront le choix de k bits de [0, 1, 2 ... n-1] et puis c'est juste une question de construction de la chaîne de caractères donnée ces bits d'index.

Puisque vous n'êtes pas à l'aide de Python, regardez le pseudo-code pour itertools.combinaisons ici:

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

Devrait être facile à mettre en œuvre dans n'importe quelle langue.
- Avez-vous connaissance d'un langage indépendant de la solution? Cela dépend de python itertools mais mon programme n'est pas écrit en python.
- Voir mon edit. Les documents montrent comment itertools.combinaisons est mis en œuvre. Vous pouvez facilement le porter quelle que soit la langue que vous utilisez.
- J'ai ajouté un lien vers un Java combinaison générateur.
- Java combinaison générateur de lien n'est pas valide
InformationsquelleAutor FogleBird
9

Oublier de mise en œuvre ("être fait avec des cordes" est évidemment un mise en œuvre question!) - pensez-l' algorithme, bon sang... tout comme dans, votre première BALISE, homme!

Ce que vous cherchez est toutes les combinaisons de K éléments d'un ensemble de N (les indices de 0 à N-1 , de l'ensemble de bits). C'est évidemment plus simple d'exprimer de manière récursive, par exemple, de pseudo:
```
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)
```
c'est à dire, le premier élément est soit présente, soit absente: si présent, vous avez K-1 à gauche pour aller (à partir de la queue aka tout-mais-sapins), en cas d'absence, encore K laissée aller.

Pattern-matching langages fonctionnels comme SML ou Haskell peut être le meilleur pour exprimer ce pseudo-code (procédurales, comme mon grand amour Python, peut masquer le problème trop profondément en incluant trop riche en fonctionnalités, telles que la itertools.combinations, qui fait tout le travail dur pour vous et, par conséquent, se CACHE de vous!).

De quoi êtes-vous le plus familier, pour cette raison-Régime, SML, Haskell, ...? Je serai heureux de traduire le pseudo-code ci-dessus pour vous. Je peux le faire dans des langages tels que Python aussi, bien sûr-mais puisque le but est de vous amener à comprendre la mécanique de ce devoir, je ne les utilise pas trop riche en fonctionnalités telles que la itertools.combinations, mais plutôt la récursivité (et récursivité-élimination, si nécessaire) sur plus évident primitives (comme la tête, la queue, et la concaténation). Mais s'il vous plaît laissez-nous savoir ce pseudo-comme la langue que vous êtes plus familier avec le! (Vous FAIRE comprendre que le problème de l'état est identique équipotent à "obtenir toutes les combinaisons de K éléments ou de la plage(N)", non?).
- Vous n'avez pas vu nuttin' encore -- rappelez-vous, j'ai commencé la conception (numérique) jetons, donc ce genre de problèmes que suscite mon sang italien!-)
- Vous aimez itertools et vous le savez.
- Euh, tout d'abord, ce n'est pas un devoir à la maison. Deuxièmement, je suis en utilisant Java, mais qui ne devrais vraiment pas d'importance. Alors que itertools.la combinaison est un python solution spécifique, je suppose que je peux la mettre en œuvre en Java, mais c'est une autre source potentielle de redondance dans un programme qui s'exécute déjà plus lent que ce que j'avais prévu. Le temps d'exécution du programme est déjà dans la gamme des jours mais je suis en mesure de trouver la puissance de calcul de la force brutale comme c'est un problème NP-complet de problème. Je n'ai pas besoin de plus.
- Le problème que je me réfère comme NP-complet n'est-ce pas une chaîne binaire problème, mais plutôt la correspondance de forclusion problème que j'essaie de résoudre que nécessite cet algorithme. Désolé.
InformationsquelleAutor Alex Martelli

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

C'est la première version que j'ai trouvé. Il est limité par l'espace de pile pour 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;
      }
    }
  }
}

C'est la deuxième version, qui utilise un binaire diviser plutôt que de diviser le premier caractère, de sorte qu'il utilise la pile de manière beaucoup plus efficace. C'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 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;
        }
      }
    }
  }
}

InformationsquelleAutor Guffa

4

Un problème avec beaucoup de standard de solutions à ce problème, c'est que l'ensemble des chaînes est généré et puis ceux-ci sont répétées à travers, ce qui peut épuiser la pile. Il devient vite encombrant pour tous, mais les plus petits ensembles. En outre, dans de nombreux cas, seule une partie de l'échantillonnage est nécessaire, mais la norme (récursif) des solutions généralement hacher le problème en morceaux qui sont fortement biaisée à une direction (par exemple. envisager toutes les solutions avec un zéro bit de début, puis toutes les solutions avec un bit de début).

Dans de nombreux cas, il serait plus souhaitable d'être en mesure de passer à une chaîne de bits (en spécifiant l'élément de sélection) à une fonction et revenir le lendemain chaîne de bits de manière à avoir un changement minime (ce qui est connu comme un Gris Code) et de disposer d'une représentation de tous les éléments.

Donald Knuth couvre une multitude d'algorithmes dans son Fascicule 3 BIS, l'article 7.2.1.3: Générer toutes les Combinaisons.

Il s'agit d'une approche pour la lutte contre l'itératif Gris algorithme de Code pour toutes les façons de choisir k éléments parmi n à http://answers.yahoo.com/question/index?qid=20081208224633AA0gdMl
avec un lien pour la finale de PHP code répertorié dans le commentaire (cliquez pour agrandir) au bas de la page.

InformationsquelleAutor Csaba Gabor
1

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!
- Ah, avec un peu de modification, de cet algorithme fonctionne. Merci! Je vais poster une modification à la question d'origine.
- Si, après examen, ce ne produisent beaucoup de branches mortes de l'arbre. Je vais tester avec un plus grand de n valeurs.
- Ah, ouais, ça ressemble à l'exécution de cet algorithme prend trop de temps pour les séries de données j'ai besoin de tester. Je suis à la recherche de n=32 et k=7, mais j'ai besoin de la flexibilité de l'échelle pour de futurs essais.
- FWIW, mon algorithme s'exécute en environ 5 secondes (32, 7)... de 3,3 millions de combinaisons. Et c'est Python, Java sera plus rapide.
InformationsquelleAutor Chip Uni

En plus de façon générique, ci-dessous la fonction va vous donner tous les possibles de l'indice de combinaisons de N de choisir K un problème auquel vous pouvez ensuite appliquer à une chaîne ou de 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

InformationsquelleAutor Scott Lobdell

Python (style fonctionnel)

À l'aide de python's itertools.combinations vous pouvez générer tous les choix de k notre de n et de 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)]

est-il un numpy équivalent?

InformationsquelleAutor Uri Goren

0

Possible de 1,5-doublure:
```
$ 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 le permutation de la méthode.
- Sympa, mais qui ne sont pas à l'échelle, en particulier lorsque n est grand et k est petit-ish.
- Il est extrêmement inefficace, pensez à utiliser itertools.combinations au lieu
InformationsquelleAutor miku
0

Je voudrais essayer de récursivité.

Il y a des chiffres n avec k d'entre eux 1s. Une autre façon de voir cela est de la séquence de k+1 slots avec la n-k 0 réparti entre eux. Qui est, (une course de 0 suivi par un 1) k fois, puis une autre course de 0s. Aucun de ces essais peut être de longueur nulle, mais la longueur totale doit être n-k.

La représenter comme un ensemble de k+1 entiers. Convertir une chaîne de caractères au bas de la récursivité.

De manière récursive appel à la profondeur n-k, une méthode qui incrémente un élément de la matrice avant un appel récursif et puis décrémente, k+1 fois.

À la profondeur de la n-k, la chaîne de sortie.
```
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 depuis que j'ai fait en Java, donc il y a probablement quelques erreurs dans ce code, mais l'idée devrait fonctionner.

InformationsquelleAutor UncleO
0

Sont des chaînes de caractères plus rapide qu'un tableau d'entiers? Toutes les solutions ajoutant à cordes probablement une copie de la chaîne à chaque itération.

Donc probablement le moyen le plus efficace serait un tableau de int ou char que vous ajoutez à. Java est efficace cultivables conteneurs, droit? Utilisez-le, si c'est plus rapide que string. Ou si BigInteger est efficace, c'est certainement compact, puisque chaque bit prend seulement un peu, pas tout un octet ou entier. Mais puis d'itérer sur les éléments dont vous avez besoin pour & masque un peu, et bitshift le masque à la prochaine position du bit. De manière sans doute plus lent, à moins que les compilateurs JIT sont bonnes à ces jours-ci.

Je post ce un un commentaire sur la question d'origine, mais mon karma n'est pas assez haut. Désolé.

InformationsquelleAutor Peter Cordes

Vous devez vous connecter pour publier un commentaire.

Calculer la lexicographiquement à côté peu de permutation

Python (style fonctionnel)