algorithm - guia - qgis manual

Generar todas las cadenas binarias de longitud n con k bits establecidos

Question

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

0111
1011
1101
1110

Necesito una buena manera de generar estos dado cualquier n y cualquier k, así que preferiría que se haga con cadenas.

Answer 1

Python (estilo funcional)

Usando python ''s itertools.combinations puedes generar todas las opciones de k de n y mapear esas elecciones 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 2

¿Son las cadenas más rápidas que una matriz de ints? Todas las soluciones que preceden a las cadenas probablemente den como resultado una copia de la cadena en cada iteración.

Entonces, probablemente la forma más eficiente sería una matriz de int o char a la que usted agregue. Java tiene contenedores rentables eficientes, ¿verdad? Úselo, si es más rápido que la cuerda. O si BigInteger es eficiente, es ciertamente compacto, ya que cada bit solo lleva un bit, no un byte completo o int. Pero luego para iterar sobre los bits que necesita y enmascarar un poco, y cambiar la máscara a la siguiente posición de bit. Probablemente sea más lento, a menos que los compiladores de JIT sean buenos en estos días.

Publicaría este un comentario sobre la pregunta original, pero mi karma no es lo suficientemente alto. Lo siento.

Answer 3

De manera más genérica, la función siguiente le dará todas las combinaciones de índices posibles para un problema de N elija K, que luego 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 4

Este método C # devuelve un enumerador que crea todas las combinaciones. Como crea las combinaciones a medida que las enumera, solo utiliza el espacio de pila, por lo que no está limitado por el espacio de memoria en la cantidad de combinaciones que puede crear.

Esta es la primera versión que se me ocurrió. Está limitado por el espacio de la pila a 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 dividir el primer carácter, por lo que utiliza la pila de manera mucho más eficiente. Solo está limitado por el espacio de memoria para la cadena que crea en cada iteración, y lo he probado hasta una longitud 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

Este método generará todos los enteros con exactamente N ''1'' bits.

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

Calcule lexicográficamente la siguiente permutación de bit

Supongamos que tenemos un patrón de N bits establecido en 1 en un entero y queremos la siguiente permutación de N 1 bits en un sentido lexicográfico. Por ejemplo, si N es 3 y el patrón de bits es 00010011 , los siguientes patrones serían 00010101 , 00010110 , 00011001 , 00011010 , 00011100 , 00100011 , y así sucesivamente. 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 intrínseco para CPU x86 devuelve el número de ceros finales. Si está utilizando compiladores de Microsoft para x86, el intrínseco es _BitScanForward . Ambos emiten una instrucción bsf , pero los equivalentes pueden estar disponibles para otras arquitecturas. De lo contrario, considere usar uno de los métodos para contar los bits cero consecutivos mencionados anteriormente. Aquí hay otra versión que tiende a ser más lenta debido a su operador de división, pero no requiere contar los ceros finales.

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

Gracias a Dario Sneidermanis de Argentina, quien brindó esto el 28 de noviembre de 2009.

Answer 6

Intentaría la recursión.

Hay n dígitos con k de ellos 1s. Otra forma de ver esto es la secuencia de k + 1 ranuras con nk 0s distribuidos entre ellas. Es decir, (una racha de 0 seguidos por un 1) k veces, seguida de otra racha de 0. Cualquiera de estas ejecuciones puede ser de longitud cero, pero la longitud total debe ser nk.

Represente esto como una matriz de enteros k + 1. Convierte a una cadena en la parte inferior de la recursión.

Llamar recursivamente a depth nk, un método que incrementa un elemento de la matriz antes de una llamada recursiva y luego la disminuye, k + 1 veces.

En la profundidad de nk, da salida a 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 pasado un tiempo desde que hice Java, por lo que es probable que haya algunos errores en este código, pero la idea debería funcionar.

Answer 7

Olvídate de la implementación ("¡ya sea con cuerdas" es obviamente un problema de implementación !) - piensa en el algoritmo , por el bien de Pete ... ¡igual que en, tu primer TAG, hombre!

Lo que está buscando son todas las combinaciones de K elementos de un conjunto de N (los índices, 0 a N-1, de los bits establecidos). Eso es obviamente más simple de expresar recursivamente, 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, le queda K-1 para ir (de la cola también conocido como todo-pero-primero), si está ausente, todavía falta K para ir.

Los lenguajes funcionales de coincidencia de patrones como SML o Haskell pueden ser mejores para expresar este pseudocódigo (los procedimientos, como mi gran amor Python, en realidad pueden enmascarar el problema demasiado profundamente al incluir una funcionalidad demasiado rica, como itertools.combinations , que hace todo el trabajo duro para ti y por lo tanto lo ESCONDES de ti!).

¿Con qué estás más familiarizado, para este propósito: Scheme, SML, Haskell, ...? Estaré encantado de traducir el pseudocódigo anterior para usted. Puedo hacerlo en lenguajes como Python también, por supuesto, pero como el punto es lograr que entiendas la mecánica de esta tarea, no utilizaré una funcionalidad demasiado rica como itertools.combinations , sino más bien recursividad ( y recursión-eliminación, si es necesario) en primitivas más obvias (como cabeza, cola y concatenación). ¡Pero por favor, háganos saber qué lenguaje parecido a un pseudocódigo está familiarizado con usted! (SÍ NO entiendes que el problema que dices es idénticamente equitativo para "sacar todas las combinaciones de K objetos o rango (N)", ¿no?).

Answer 8

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 9

Un 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 1 s en "0111" .

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

Answer 10

Un problema con muchas de las soluciones estándar para este problema es que todo el conjunto de cadenas se genera y luego se iteran, lo que puede agotar la pila. Rápidamente se vuelve difícil de manejar para cualquier juego menos el más pequeño. Además, en muchos casos, solo se necesita un muestreo parcial, pero las soluciones estándar (recursivas) generalmente cortan el problema en pedazos que están fuertemente sesgados en una dirección (por ejemplo, consideran todas las soluciones con un bit de inicio cero, y luego todas las soluciones con un bit de inicio).

En muchos casos, sería más conveniente poder pasar una cadena de bits (especificando la selección de elementos) a una función y hacer que devuelva la siguiente cadena de bits de manera que tenga un cambio mínimo (esto se conoce como gris Código) y tener una representación de todos los elementos.

Donald Knuth cubre una gran cantidad de algoritmos para esto en su Fascículo 3A, sección 7.2.1.3: Generación de todas las combinaciones.

Existe un enfoque para abordar el algoritmo iterativo de Gray Code para todas las formas de elegir k elementos de n en http://answers.yahoo.com/question/index?qid=20081208224633AA0gdMl con un enlace al código PHP final que figura en el comentario ( haga clic para expandirlo) en la parte inferior de la página.

Answer 11

Pitón

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:

Esencialmente tenemos que elegir las posiciones de los 1 bits. Hay n elegir k formas de elegir k bits entre n bits totales. itertools es un módulo agradable que hace esto por nosotros. itertools.combinations (range (n), k) elegirá k bits de [0, 1, 2 ... n-1] y luego solo se trata de construir la cadena dados esos índices de bit.

Como no está usando Python, mire el pseudocódigo para itertools.combinations aquí:

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

Debería ser fácil de implementar en cualquier idioma.

Aquí hay un generador de combinación de Java:

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