Gere todas as strings binárias de comprimento n com k bits definidos

Qual é o melhor algoritmo para encontrar todas as cadeias binárias de comprimento n que contenham k bits definidos? Por exemplo, se n = 4 e k = 3, existem …

0111 1011 1101 1110 

Eu preciso de uma boa maneira de gerar estes n e qualquer k, então eu prefiro que seja feito com strings.

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

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

Calcule a permutação do próximo bit lexicograficamente

Suponha que tenhamos um padrão de N bits definido como 1 em um inteiro e queremos a próxima permutação de N 1 bits em um sentido lexicográfico. Por exemplo, se N for 3 e o padrão de bits for 00010011 , os próximos padrões serão 00010101 , 00010110 , 00011001 , 00011010 , 00011100 , 00100011 e assim por diante. A seguir, uma maneira rápida de 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 compilador __builtin_ctz(v) GNU C intrínseco para CPUs x86 retorna o número de zeros à direita. Se você estiver usando compiladores da Microsoft para x86, o intrínseco será _BitScanForward . Ambos emitem uma instrução bsf , mas equivalentes podem estar disponíveis para outras arquiteturas. Se não, considere usar um dos methods para contar os bits zero consecutivos mencionados anteriormente. Aqui está outra versão que tende a ser mais lenta por causa de seu operador de divisão, mas não requer a contagem dos zeros à direita.

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

Obrigado a Dario Sneidermanis da Argentina, que forneceu isso em 28 de novembro de 2009.

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, precisamos escolher as posições dos 1 bits. Existem n maneiras de escolher k bits entre n bits totais. itertools é um bom módulo que faz isso para nós. itertools.combinations (range (n), k) escolherá k bits de [0, 1, 2 … n-1] e, em seguida, é apenas uma questão de construir a string de acordo com esses índices de bits.

Como você não está usando o Python, veja 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.

Aqui está um gerador de combinação Java:

http://www.merriampark.com/comb.htm

Esqueça a implementação (“seja feito com strings” é obviamente uma questão de implementação !) – pense no algoritmo , pelo amor de Deus … assim como no 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 recursivamente, 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) 

isto é, o primeiro item está presente ou ausente: se estiver presente, você tem K-1 para ir (da cauda também conhecido como all-but-firs), se estiver ausente, ainda K vai embora.

As linguagens funcionais de correspondência de padrões como SML ou Haskell podem ser as melhores para expressar esse pseudocódigo (os procedurais, como meu grande amor Python, podem realmente mascarar o problema muito profundamente incluindo funcionalidades muito ricas, como itertools.combinations , que faz todo o trabalho duro para você e, portanto, esconde de você!).

Com o que você está mais familiarizado, para esse propósito – Scheme, SML, Haskell, …? Ficarei feliz em traduzir o pseudocódigo acima para você. Eu posso fazê-lo em linguagens como o Python também, é claro – mas como o ponto é fazer com que você entenda a mecânica dessa lição de casa, não usarei funcionalidades muito ricas como itertools.combinations , mas sim recursion ( e recursion-eliminação, se necessário) em primitivos mais óbvios (como cabeça, cauda e concatenação). Mas por favor, deixe-nos saber o idioma que você está mais familiarizado com o pseudocódigo! (Você entende que o problema que você declara é identicamente equipotente para “obter todas as combinações de K itens fora ou alcance (N)”, certo?).

Este método C # retorna um enumerador que cria todas as combinações. Como ele cria as combinações conforme você as enumera, ele usa apenas o espaço da pilha, portanto, não é limitado pelo espaço de memory no número de combinações que ele pode criar.

Esta é a primeira versão que eu criei. É limitado pelo espaço de pilha para um comprimento de cerca de 2700:

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

Essa é a segunda versão, que usa uma divisão binária em vez de dividir o primeiro caractere, portanto, usa a pilha de maneira muito mais eficiente. Ele é limitado apenas pelo espaço de memory para a string que ele cria em cada iteração, e eu testei até um comprimento de 10000000:

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

Um problema com muitas das soluções padrão para esse problema é que todo o conjunto de strings é gerado e, em seguida, são iterados, o que pode esgotar a pilha. Ele rapidamente se torna difícil para qualquer um, exceto os conjuntos menores. Além disso, em muitos casos, apenas uma amostragem parcial é necessária, mas as soluções padrão (recursivas) geralmente dividem o problema em partes fortemente enviesadas em uma direção (por exemplo, considerar todas as soluções com um zero de bit inicial e, em seguida, todas as soluções com um bit de partida).

Em muitos casos, seria mais desejável poder passar uma cadeia de bits (especificando a seleção de elementos) para uma function e fazer com que ela retornasse a próxima cadeia de bits de tal forma que tivesse uma alteração mínima (isto é conhecido como um Gray). Código) e ter uma representação de todos os elementos.

Donald Knuth cobre uma série de algoritmos para isso em seu Fascicle 3A, seção 7.2.1.3: Gerando todas as combinações.

Existe uma abordagem para lidar com o algoritmo de Gray Code iterativo 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 expandi-lo) na parte inferior da página.

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!

De uma maneira mais genérica, a function abaixo dará a você todas as possíveis combinações de índice para um problema N escolha K, que você pode aplicar a uma string 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 

Python (estilo funcional)

Usando python ‘s itertools.combinations você pode gerar todas as opções de k de n e mapear essas opções para um array binário 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 uso:

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

Um 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 1 s em "0111" .

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

Eu tentaria recursion.

Existem n dígitos com k deles 1s. Outra maneira de ver isso é a sequência de k + 1 slots com nk 0s distribuídos entre eles. Ou seja, (uma sequência de 0s seguida por 1) k vezes, seguida por outra sequência de 0s. Qualquer uma dessas execuções pode ser de comprimento zero, mas o comprimento total precisa ser nk.

Represente isso como uma matriz de inteiros k + 1. Converta em uma string na parte inferior da recursion.

Chame recursivamente a profundidade nk, um método que incrementa um elemento da matriz antes de uma chamada recursiva e depois a decrementa, k + 1 vezes.

Na profundidade de nk, imprima a string.

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

Já faz um tempo desde que eu fiz o Java, então provavelmente há alguns erros neste código, mas a ideia deve funcionar.

As strings são mais rápidas que uma matriz de ints? Todas as soluções prepending para seqüências de caracteres provavelmente resultam em uma cópia da seqüência de caracteres em cada iteração.

Então, provavelmente, a maneira mais eficiente seria uma matriz de int ou char que você anexa. Java tem recipientes crescentes eficientes, certo? Use isso, se for mais rápido que string. Ou se o BigInteger é eficiente, certamente é compacto, já que cada bit leva apenas um pouco, não um byte inteiro ou int. Mas, então, para iterar os bits que você precisa e mascarar um pouco, e bitshift a máscara para a próxima posição de bit. Então, provavelmente, mais lento, a menos que os compiladores JIT sejam bons nisso hoje em dia.

Eu colocaria este comentário sobre a questão original, mas meu carma não é alto o suficiente. Desculpa.