subconjuntos - teoria de conjuntos pdf

Encontrar los conjuntos binarios de subsecuencia máxima que tienen un número igual de 1s y 0s

Question

Encontré el siguiente problema en Internet y me gustaría saber cómo lo solucionaría:

Te dan una matriz que contiene 0s y 1s. Encuentre el tiempo O (n) y el algoritmo de espacio O (1) para encontrar la secuencia secundaria máxima que tiene igual número de 1s y 0s.

Ejemplos:

1. 10101010 - La 10101010 más larga que satisface el problema es la entrada en sí misma
2. 1101000 - La sub secuencia más larga que satisface el problema es 110100

Answer 1

Como lo señaló el usuario "R ..", no hay ninguna solución, estrictamente hablando, a menos que ignore la complejidad del espacio "log n". A continuación, consideraré que la longitud de la matriz se ajusta a un registro de máquina (por ejemplo, una palabra de 64 bits) y que un registro de máquina tiene un tamaño O (1).

El punto importante a tener en cuenta es que si hay más 1 que 0, entonces la subsecuencia máxima que está buscando incluye necesariamente todos los 0, y esa cantidad de 1. Así que aquí el algoritmo:

Notaciones: la matriz tiene longitud n , los índices se cuentan de 0 a n-1 .

1. Primera pasada: contar el número de 1 ( c1 ) y 0 ( c0 ). Si c1 = c0 , su subsecuencia máxima es la matriz completa (final del algoritmo). De lo contrario, sea d el dígito que aparece con menos frecuencia ( d = 0 si c0 <c1 , de lo contrario d = 1 ).
2. Calcular m = min (c0, c1) * 2 . Este es el tamaño de la subsecuencia que está buscando.
3. Segundo paso: escanee la matriz para encontrar el índice j de la primera aparición de d .
4. Calcular k = max (j, n - m) . La subsecuencia comienza en el índice k y tiene una longitud m .

Tenga en cuenta que podría haber varias soluciones (varias subsecuencias de longitud máxima que coincidan con el criterio).

En palabras simples: asumiendo que hay más 1''s que 0''s, entonces considero la subsecuencia más pequeña que contiene todos los 0''s. Por definición, esa subsecuencia está rodeada por grupos de 1. Así que solo tomo 1 suficiente de los lados.

Edit: como se señaló, esto no funciona ... El "punto importante" es realmente incorrecto.

Answer 2

En este hilo ( http://discuss.techinterview.org/default.asp?interview.11.792102.31 ), AF de póster ha dado un algoritmo que se ejecuta en tiempo O (n) y usa O (sqrt (n log n)) pedacitos

Answer 3

Hablando estrictamente, la respuesta es que no existe tal algoritmo porque el lenguaje de las cadenas que consta de un número igual de ceros y unos no es regular.

Por supuesto, todos ignoran el hecho de que almacenar un número entero de magnitud n es O(log n) en el espacio y lo trata como O(1) en el espacio. :-) Casi todas las grandes O, incluidas las de tiempo, están llenas de (o más bien están vacías) de factores faltantes de log n , o de manera equivalente, asumen que n está delimitada por el tamaño de una palabra de máquina, lo que significa que realmente viendo un problema finito y todo es O(1) .

Answer 4

Intenta algo como esto:

/* bit(n) is a macro that returns the nth bit, 0 or 1. len is number of bits */
int c[2] = {0,0};
int d, i, a, b, p;
for(i=0; i<len; i++) c[bit(i)]++;
d = c[1] < c[0];
if (c[d] == 0) return; /* all bits identical; fail */
for(i=0; bit(i)!=d; i++);
a = b = i;
for(p=0; i<len; i++) {
p += 2*bit(i)-1;
if (!p) b = i;
}
if (a == b) { /* account for case where we need bits before the first d */
b = len - 1;
a -= abs(p);
}
printf("maximal subsequence consists of bits %d through %d/n", a, b);

Completamente sin probar pero modulo errores estúpidos debería funcionar. Basado en mi respuesta a la respuesta de Thomas que falló en ciertos casos.

Answer 5

No estoy seguro de si la matriz a la que se refiere es int matriz de 0 y 1 o bitarray?

Si se trata de bitarray, aquí está mi enfoque:

int isEvenBitCount(int n)
{
//n ... //Decimal equivalent of the input binary sequence
int cnt1 = 0, cnt0 = 0;
while(n){
if(n&0x01) { printf("1 "); cnt1++;}
else { printf("0 "); cnt0++; }
n = n>>1;
}
printf("/n");
return cnt0 == cnt1;
}
int main()
{
int i = 40, j = 25, k = 35;
isEvenBitCount(i)?printf("-->Yes/n"):printf("-->No/n");
isEvenBitCount(j)?printf("-->Yes/n"):printf("-->No/n");
isEvenBitCount(k)?printf("-->Yes/n"):printf("-->No/n");
}

con el uso de operaciones bitwise la complejidad del tiempo es casi O (1) también.

Answer 6

fuerza bruta: comience con la longitud máxima de la matriz para contar las o''s y las l''s. Si o eqals l, has terminado. de lo contrario, reduzca la longitud de búsqueda en 1 y realice el algoritmo para todas las subsecuencias de la longitud reducida (es decir, la longitud máxima menos la longitud reducida) y así sucesivamente. detente cuando la resta es 0.

Answer 7

Actualizar

Tengo que reformular completamente mi respuesta. (Si has votado anteriormente la versión anterior, bueno, ¡te engañaron!)

Resumamos el caso fácil otra vez, para sacarlo del camino:

Encuentre el prefijo más largo de la cadena de bits que contiene un número igual de 1s y 0s de la matriz.

Esto es trivial: se necesita un contador simple, contando cuántos más 1s tenemos que 0s, y repitiendo la cadena de bits mientras se mantiene esto. La posición donde este contador se convierte en cero por última vez es el final del prefijo más largo buscado. O (N) tiempo, O (1) espacio. (Ahora estoy completamente convencido de que esto es lo que pidió el problema original).

Ahora pasemos a la versión más difícil del problema: ya no requerimos que las subsecuencias sean prefijos, pueden comenzar en cualquier lugar.

Después de algunos pensamientos de ida y vuelta, pensé que podría no haber un algoritmo lineal para esto. Por ejemplo, considere el prefijo "111111111111111111 ...". Cada uno de ellos puede ser el comienzo de la subsecuencia más larga, no hay una posición de inicio de subsecuencia candidata que domine (es decir, siempre dé mejores soluciones que) cualquier otra posición, por lo que no podemos eliminar ninguna de ellas (O (N) espacio) y en cualquier paso, debemos ser capaces de seleccionar el mejor inicio (que tiene un número igual de 1s y 0s a la posición actual) de muchos candidatos linealmente, en tiempo O (1). Resulta que esto es factible , y también fácil de hacer, ya que podemos seleccionar al candidato en función de la suma acumulada de 1s (+1) y 0s (-1), esto tiene un tamaño máximo de N, y podemos almacenar la primera posición alcanzamos cada suma en celdas 2N: vea la respuesta de pmod a continuación (también los comentarios de Yellowfog y la perspectiva geométrica).

Al no encontrar este truco, había reemplazado un algoritmo rápido pero incorrecto con un algoritmo lento pero seguro (¡ya que los algoritmos correctos son preferibles a los incorrectos!):

• Cree una matriz A con el número acumulado de 1s desde el inicio hasta esa posición, por ejemplo, si la cadena de bits es "001001001", entonces la matriz sería [0, 0, 1, 1, 1, 2, 2, 2, 3] . Usando esto, podemos probar en O (1) si la subsecuencia (i, j), inclusive, es válida: isValid(i, j) = (j - i + 1 == 2 * (A[j] - A[i - 1]) , es decir, es válido si su longitud es el doble de la cantidad de 1 en él. Por ejemplo, la subsecuencia (3,6) es válida porque 6 - 3 + 1 == 2 * A [6] - A [2] = 4.

• Bucle doble viejo llano:

  maxSubsLength = 0 para i = 1 a N - 1 para j = i + 1 a N si isValid (i, j) ... #maintain maxSubsLength end end

Esto se puede acelerar un poco utilizando algunas derivaciones y saltos salteando las secuencias i / j que son más cortas que el maxSubsLength actual, pero asintóticamente todavía es O (n ^ 2). Lento, pero con una gran ventaja: ¡correcto!

Answer 8

Nueva solución: complejidad de espacio de O (1) y complejidad de tiempo O (n ^ 2)

 int iStart = 0, iEnd = 0;
int[] arrInput = { 1, 0, 1, 1, 1,0,0,1,0,1,0,0 };
for (int i = 0; i < arrInput.Length; i++)
{
int iCurrEndIndex = i;
int iSum = 0;
for (int j = i; j < arrInput.Length; j++)
{
iSum = (arrInput[j] == 1) ? iSum+1 : iSum-1;
if (iSum == 0)
{
iCurrEndIndex = j;
}
}
if ((iEnd - iStart) < (iCurrEndIndex - i))
{
iEnd = iCurrEndIndex;
iStart = i;
}
}

Answer 9

Nueva solución: supongamos que tenemos para la matriz de bits de entrada de n bits 2 * matriz de tamaño n para mantener la posición del bit. Por lo tanto, el tamaño del elemento de la matriz debe tener el tamaño suficiente para mantener el número máximo de posición. Para la matriz de 256 bits de entrada, se necesita una matriz de bytes de 256x2 (el byte es suficiente para mantener 255 - la posición máxima).

Moviéndonos desde la primera posición de la matriz de bits, colocamos la posición en la matriz comenzando desde la mitad de la matriz (el índice es n) usando una regla:

1. Incrementar la posición si pasamos el bit "1" y disminuir cuando se pasa el bit "0"

2. Cuando se encuentre con el elemento de matriz ya inicializado, no lo cambie y recuerde la diferencia entre las posiciones (el menos actual tomado del elemento de matriz): este es un tamaño de secuencia máxima local.

3. Cada vez que alcancemos el máximo local, compárelo con el máximo global y actualícelo si este último es menor.

Por ejemplo: la secuencia de bits es 0,0,0,1,0,1

 initial array index is n
set arr[n] = 0 (position)
bit 0 -> index--
set arr[n-1] = 1
bit 0 -> index--
set arr[n-2] = 2
bit 0 -> index--
set arr[n-3] = 3
bit 1 -> index++
arr[n-2] already contains 2 -> thus, local max seq is [3,2] becomes abs. maximum
will not overwrite arr[n-2]
bit 0 -> index--
arr[n-3] already contains 3 -> thus, local max seq is [4,3] is not abs. maximum
bit 1 -> index++
arr[n-2] already contains 2 -> thus, local max seq is [5,2] is abs. max

Por lo tanto, pasamos a través de toda la matriz de bits una sola vez. ¿Resuelve esto la tarea?

input:
n - number of bits
a[n] - input bit-array
track_pos[2*n] = {0,};
ind = n;
/* start from position 1 since zero has
meaning track_pos[x] is not initialized */
for (i = 1; i < n+1; i++) {
if (track_pos[ind]) {
seq_size = i - track_pos[ind];
if (glob_seq_size < seq_size) {
/* store as interm. result */
glob_seq_size = seq_size;
glob_pos_from = track_pos[ind];
glob_pos_to = i;
}
} else {
track_pos[ind] = i;
}
if (a[i-1])
ind++;
else
ind--;
}
output:
glob_seq_size - length of maximum sequence
glob_pos_from - start position of max sequence
glob_pos_to - end position of max sequence