Generar todas las cadenas binarias de longitud N con el conjunto de k bits

Question

¿Cuál es el mejor algoritmo para encontrar todas las cadenas binarias de longitud n que contiene k bits set? Por ejemplo, si n = 4 y k = 3, hay ...

0111
1011
1101
1110

Necesito una buena manera de generar estos dados N y cualquier k de modo que prefiero que se haga con cuerdas.

Answer 1

Este método va a generar todos los números enteros con n '1' bits de exactamente.

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

  

Calcule el siguiente orden lexicográfico permutación de bits

     

Supongamos que tenemos un patrón de N bits se establece en 1 en un número entero y queremos   la siguiente permutación de N bits 1 en un sentido lexicográfico. por   ejemplo, si N es 3 y el patrón de bits es 00010011, los próximos patrones   se 00010101, 00010110, 00011001, 00011010, 00011100, 00100011,   Etcétera. La siguiente es una forma rápida de calcular la siguiente   permutación.

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

     

El __builtin_ctz(v) GNU C compilador intrínseco para CPUs x86 devuelve el número de ceros a la derecha. Si está utilizando compiladores de Microsoft para   x86, la intrínseca es _BitScanForward. Estos emiten tanto un bsf   instrucción, sino equivalentes pueden estar disponibles para otras arquitecturas.   Si no, entonces considerar el uso de uno de los métodos para contar el   bits consecutivos cero se mencionó anteriormente. Aquí hay otra versión que   tiende a ser más lenta debido a su operador de división, pero no lo hace   requerir contar los ceros de salida.

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

     

Gracias a Darío Sneidermanis de Argentina, que proporcionó este el 28 de noviembre de 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']

Explicación:

En esencia tenemos que elegir las posiciones de los bits 1. Hay n eligen k formas de elegir k bits entre los bits de n totales. itertools es un módulo agradable que lo hace por nosotros. itertools.combinations (intervalo (n), k) elegirán k bits de [0, 1, 2 ... n-1] y entonces es sólo una cuestión de la construcción de la cadena dada esos índices de bits.

Dado que no está utilizando Python, mira el pseudo-código para itertools.combinations aquí:

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

En caso de ser fácil de implementar en cualquier lenguaje.

Answer 3

Olvídate de aplicación ( "sea hecho con cuerdas" es, obviamente, un aplicación tema!) - pensar en el algoritmo , por amor de Dios ... tan en, su primer TAG, hombre!

Lo que estamos buscando es todas las combinaciones de K artículos fuera de un conjunto de N (los índices, 0 a N-1, de los bits set). Eso es obviamente más simple de expresar de forma recursiva, por ejemplo, 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)

.

es decir, el primer elemento está presente o ausente:. Si está presente, tiene K-1 dejó ir (de la cola aka todos-pero-abetos), en su ausencia, siendo K la izquierda para ir

coincidencia de patrones lenguajes funcionales como LME o Haskell puede ser la mejor manera de expresar este pseudocódigo (procedimentales, como mi gran pitón amor, en realidad puede enmascarar el problema demasiado profundamente mediante la inclusión de la funcionalidad demasiado rica, como itertools.combinations, que hace todo el trabajo duro por usted y por lo tanto lo esconde de usted!).

¿Qué es lo que más familiarizado, para este propósito - Esquema, SML, Haskell, ...? Voy a estar dispuestos a traducir el pseudocódigo anterior para usted. Puedo hacerlo en lenguajes como Python también, por supuesto - pero desde el punto es conseguir a entender la mecánica de esta tarea, no voy a utilizar la funcionalidad demasiado rica como itertools.combinations, sino más bien la recursividad (y recursividad -Eliminación, si es necesario) en primitivas más evidentes (tales como la cabeza, cola, y la concatenación). Pero, por favor, háganos saber lo pseudocódigo-como el lenguaje que está más familiarizado con! (Te entienden que el problema que el estado es idéntica equipotentes a "obtener todas las combinaciones de artículos K o fuera de alcance (n)", ¿verdad?).

Answer 4

Este método C # devuelve un enumerador que crea todas las combinaciones. Ya que crea las combinaciones a medida que los enumerar sólo se utiliza el espacio de pila, por lo que no está limitado por el espacio de memoria en el número de combinaciones que puede crear.

Esta es la primera versión que se me ocurrió. Está limitado por el espacio de pila para una longitud de aproximadamente 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 es la segunda versión, que utiliza una división binaria en lugar de disociación del primer carácter, por lo que utiliza la pila de manera mucho más eficiente. Es sólo limitado por el espacio de memoria para la cadena que se crea en cada iteración, y he probado hasta una longitud de 10 millones:

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 muchas de las soluciones estándar a este problema es que se genera todo el conjunto de cadenas y luego aquellos se itera a través, que puede agotar la pila. Rápidamente se convierte en difícil de manejar para cualquier pero los conjuntos más pequeños. Además, en muchos casos, sólo es necesario un muestreo parcial, pero el estándar soluciones (recursivas) generalmente Picar el problema en piezas que son muy sesgada a una dirección (por ejemplo. Considerar todas las soluciones con un bit cero de partida, y entonces todo las soluciones con un poco uno de partida).

En muchos casos, sería más deseable ser capaz de pasar una cadena de bits (especificando la selección de elementos) a una función y lo han devolver la siguiente cadena de bits de una manera tal como para tener un cambio mínimo (esto se conoce como un código Gray) y tener una representación de todos los elementos.

Donald Knuth abarca toda una serie de algoritmos para esto en su fascículo 3A, sección 7.2.1.3:. Generación de todas las combinaciones

No es un enfoque para abordar el algoritmo de código Gray iterativo para todas las formas de escoger k elementos de n http://answers.yahoo.com/question/index?qid=20081208224633AA0gdMl con un enlace al código PHP última cotización en el comentario (haga clic para ampliarlo) en la parte inferior de la página.

Answer 6

Un algoritmo que debería 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)

Buena suerte!

Answer 7

De forma más genérica, la función de abajo le dará todas las posibles combinaciones de índice para un problema de elegir N K que luego se puede aplicar a una cadena o cualquier otra 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 posible 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')])

.. donde k es el número de 1s en "0111".

El módulo itertools explica equivalentes por sus métodos; ver el equivalente para el método de permutación .

Answer 9

Me gustaría probar la recursividad.

Hay n dígitos con k de ellos 1s. Otra forma de ver esto es la secuencia de k + 1 ranuras con n-k 0s distribuidos entre ellos. Es decir, (una racha de 0s seguidos por un 1) k veces, y luego seguido de otra carrera de 0s. Cualquiera de estas carreras pueden ser de longitud cero, pero la longitud total tiene que ser n-k.

Representa a este como un conjunto de k + 1 números enteros. Convertir a una cadena en la parte inferior de la recursividad.

recursivamente llamar a la profundidad n-k, un método que incrementos de un elemento de la matriz antes de que una llamada recursiva y continuación, se reduce, k + 1 veces.

A la profundidad de n-k, salida de la cadena.

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

Ha sido un tiempo desde que he hecho en Java, por lo que es probable que haya algunos errores en el código, pero la idea debería funcionar.

Answer 10

son cadenas más rápidas que una matriz de enteros? Todas las soluciones prepending a cadenas son probablemente el resultado de una copia de la cadena en cada iteración.

Así que probablemente la manera más eficiente sería una matriz de int o carbón que usted adiciona. Java tiene contenedores cultivable eficientes, ¿verdad? Utilizar eso, si es más rápido que la cadena. O si BigInteger es eficiente, es sin duda compacta, ya que cada bit sólo tarda un poco, no un byte o int. Pero entonces iterar sobre los bits que necesita y máscara un poco, y BitShift la máscara a la siguiente posición de bit. Así que probablemente más lento, a menos compiladores JIT son buenos en eso en estos días.

que iba a publicar esto un comentario sobre la pregunta original, pero mi karma no es lo suficientemente alta. Lo sentimos.

Answer 11

Python (estilo funcional)

El uso de python itertools.combinations puede generar todas las opciones de nuestra k de n y mapear esas opciones a una matriz 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)]

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

Answer 12

este pregunta (donde tiene que iterar sobre todos los submasks en orden creciente de su número de bits set), que se ha caracterizado como un duplicado de éste.

Podemos simplemente iterar sobre todos los submasks ellos se suman a un vector y ordenarla de acuerdo con el número de bits establecidos.

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

Otra forma sería iterar sobre todas las veces submasks N y añadir un número para el vector de si el número de bits puestos es igual a i en la iteración i-ésimo.

Ambas formas tienen complejidad de O (n * 2 ^ n)