Gerar todas as cadeias binárias de comprimento n com k bits set

Question

O que é o melhor algoritmo para encontrar todas as strings binárias de comprimento n que contêm k bits set? Por exemplo, se n = 4 e K = 3, há ...

0111
1011
1101
1110

Eu preciso de uma boa maneira de gerar estes dado qualquer n e qualquer k então eu prefiro que ser feito com cordas.

Answer 1

Este método irá gerar todos os inteiros com exatamente '1' N bits.

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

Calcule o lexicographically próximo bit permutação

Suponha que temos um padrão de N bits definidos como 1 em um inteiro e queremos a próxima permutação de bits de N 1 num sentido léxicografica. Para exemplo, se n é 3 e o padrão de bit é 00010011, os seguintes padrões seria 00010101, 00010110, 00011001, 00011010, 00011100, 00100011, e assim por diante. O seguinte é uma maneira rápida para calcular a próxima permutação.

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

O __builtin_ctz(v) GNU C compilador intrínseca para CPUs x 86 devolve o número de zeros à direita. Se você estiver usando compiladores Microsoft para x 86, o intrínseca é _BitScanForward. Estes dois emitir um bsf instrução, mas equivalentes podem estar disponíveis para outras arquiteturas. Se não, então considerar o uso de um dos métodos para a contagem do consecutivos bits zero mencionado anteriormente. Aqui está outra versão que tende a ser mais lento por causa de seu operador de divisão, mas isso não acontece requerem contando os zeros finais.

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

Graças a Dario Sneidermanis da Argentina, que forneceu esta em 28 de Novembro, 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']

Explicação:

Essencialmente temos de escolher as posições dos bits 1. Há n escolha k formas de escolher k bits entre os n bits totais. itertools é um módulo agradável que faz isso para nós. itertools.combinations (intervalo (n), k) vai escolher k bits de [0, 1, 2 ... n-1] e, em seguida, é só uma questão de construir a string dada esses índices bit.

Uma vez que você não está usando Python, olhar para o pseudo-código para itertools.combinations aqui:

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

Deve ser fácil de implementar em qualquer idioma.

Answer 3

Esqueça implementação ( "seja feito com cordas" é obviamente um aplicação questão!) - pensar sobre o algoritmo , pelo amor de Deus ... assim como em, seu primeiro TAG, cara!

O que você está procurando todas as combinações de itens K fora de um conjunto de N (os índices, 0 a N-1, dos bits definidos). Isso é, obviamente, mais simples de expressar de forma recursiva, por exemplo, pseudocódigo:

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)

.

ou seja, o primeiro item é presente ou ausente:. Se presente, você tem K-1 deixou para ir (a partir da cauda aka todos-mas-abetos), se ausente, ainda K esquerda para ir

Padrão de correspondência de linguagens funcionais como SML ou Haskell pode ser melhor para expressar esse pseudocódigo (aqueles processuais, como o meu grande amor Python, pode realmente mascarar o problema muito profundamente, incluindo funcionalidade muito rico, como itertools.combinations, que faz tudo o trabalho duro para você e, portanto, se esconde de você!).

O que você está mais familiarizado, para este fim - Scheme, SML, Haskell, ...? Eu vou ser feliz para traduzir o pseudocódigo acima para você. Eu posso fazer isso em linguagens como Python também, é claro - mas desde que o ponto está levando você a entender a mecânica para esta tarefa de casa, não vou usar a funcionalidade muito-ricos, como itertools.combinations, mas sim recursão (e recursão -Eliminação, se necessário) em primitivas mais óbvias (tais como cabeça, cauda, ??e concatenação). Mas, por favor deixe-nos saber o que pseudocódigo-like linguagem que você está mais familiarizado com! (Você entende que o problema que estado é idêntica equipotente para "obter todas as combinações de itens K fora ou gama (N)", certo?).

Answer 4

Este método C # retorna um enumerador que cria todas as combinações. Pois cria as combinações como você enumerá-las ele só usa o espaço de pilha, por isso não é limitado pelo espaço de memória no número de combinações que ele pode criar.

Esta é a primeira versão que eu vim acima com. É limitado pelo espaço de pilha a um comprimento de cerca de 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;
      }
    }
  }
}

Esta é a segunda versão, que utiliza uma divisão binária em vez de cisão o primeiro personagem, então ele usa a pilha de forma muito mais eficiente. É limitada apenas pelo espaço de memória para a cadeia que ele cria em cada iteração, e eu testei até um comprimento 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;
        }
      }
    }
  }
}

Answer 5

Um problema com muitas das soluções convencionais para este problema é que todo o conjunto de cadeias é gerada e em seguida aqueles são iterados, que pode esgotar a pilha. Ele rapidamente torna-se difícil para qualquer mas os mais pequenos conjuntos. Além disso, em muitos casos, só é necessária uma amostragem parcial, mas o padrão de soluções (recursivo) geralmente cortar o problema em pedaços que são fortemente inclinado para uma direcção (por exemplo. Considerar todas as soluções com um pouco a partir de zero, e, em seguida, todos as soluções com um pouco de iniciar um).

Em muitos casos, seria mais desejável para ser capaz de passar uma cadeia de bits (especificando elemento de selecção) para uma função e tê-lo retornar a cadeia de bits próxima de tal forma a ter uma mudança mínima (isto é conhecido como um Código Gray) e ter uma representação de todos os elementos.

Donald Knuth abrange toda uma série de algoritmos para este em sua Fascicle 3A, secção 7.2.1.3:. Gerando todas as combinações

Não é uma abordagem para enfrentar o algoritmo iterativo código Gray para todas as formas de escolher k elementos de n em http://answers.yahoo.com/question/index?qid=20081208224633AA0gdMl com um link para o código PHP final listado no comentário (clique para expandir) na parte inferior da página.

Answer 6

Um algoritmo que deve funcionar:

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)

Boa sorte!

Answer 7

De um modo mais genérico, a seguir função irá dar-lhe todas as possíveis combinações de índice para uma N escolher problema K que você pode então aplicar-se a uma corda ou qualquer outra coisa:

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

Uma possível 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')])

.. onde k é o número de 1s em "0111".

O módulo itertools explica equivalentes para os seus métodos; veja o equivalente para o permutação método .

Answer 9

Gostaria de tentar a recursividade.

Existem n dígitos com k deles 1s. Outra maneira de visualizar este é uma sequência de k + 1 slots com 0s n-k distribuídos entre eles. Isto é, (a sequência de 0s seguido por 1) k vezes, seguida por outra série de 0s. Qualquer uma destas corridas podem ser de comprimento zero, mas as necessidades totais de comprimento a ser n-k.

Represente isto como uma série de k + 1 inteiros. Converter em uma corda na parte inferior da recursão.

recursivamente chamada a profundidade n-k, um método que incrementos de um elemento da matriz antes de uma chamada recursiva e, em seguida, diminui-lo, k + 1 vezes.

No profundidade de n-k, de saída da cadeia.

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

Tem sido um tempo desde que eu fiz Java, então provavelmente há alguns erros neste código, mas a idéia deve funcionar.

Answer 10

são strings mais rápido do que um array de inteiros? Todas as soluções Prepending para cordas provavelmente resultará em uma cópia da string a cada iteração.

Então, provavelmente a maneira mais eficiente seria uma matriz de int ou caractere que você anexar a. Java tem eficiente recipientes growable, certo? Use isso, se é mais rápido do que string. Ou se BigInteger é eficiente, é certamente compacto, uma vez que cada bit só leva um pouco, não um byte inteiro ou int. Mas, em seguida, iterar sobre os bits que você precisa e mascarar um pouco, e bitshift a máscara para a posição do bit seguinte. Então, provavelmente mais lento, a menos que compiladores JIT são bons em que estes dias.

Eu ia postar isso um um comentário sobre a questão original, mas meu karma não é alta o suficiente. Desculpe.

Answer 11

Python (estilo funcional)

Usando python de itertools.combinations você pode gerar todas as escolhas de k nosso de n e mapear essas escolhas para uma matriz binária com 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)]

Exemplo de utilização:

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

Bem para este questão (onde você precisa iterar sobre todos os submasks em ordem de número de bits definidos aumentando), que foi marcada como uma duplicata deste.

podemos simplesmente iterar sobre todos os submasks adicioná-los a um vector e classificá-lo de acordo com o número de bits definidos.

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

Outra forma seria para iterar sobre todos os submasks N vezes e adicionar um número para o vetor se o número de bits definidos é igual a i na iteração om.

Ambas as formas têm complexidade de O (n * 2 ^ n)