Estoy aprendiendo a imprimir todos los subconjuntos con la misma longitud en Javascript. Y vi esta solución en w3resource.com:
Función JavaScript: Ejercicio-21 con Solución
Escriba una función de JavaScript para obtener todas las combinaciones posibles de subconjuntos con una longitud fija (por ejemplo, 2) en una matriz.
Matriz de muestra:
[1, 2, 3]y la longitud del subconjunto es 2Salida esperada:
[[2, 1], [3, 1], [3, 2], [3, 2, 1]]Código JavaScript:
function subset(arra, arra_size) { var result_set = [], result; for(var x = 0; x < Math.pow(2, arra.length); x++) { result = []; i = arra.length - 1; do { if( (x & (1 << i)) !== 0) { result.push(arra[i]); } } while(i--); if( result.length >= arra_size) { result_set.push(result); } } return result_set; }
Sin embargo, no entiendo la lógica detrás del código, especialmente la línea con el operador bit a bit. ¿Alguien podría explicar por favor?
(x & (1 << i)) !== 0 significa "¿tiene x el i -ésimo bit establecido en 1?"
Un ejemplo:
Digamos que x en representación binaria es 1001101
Y voy a pasar de 6 a 0 ( i es lo que hace el ciclo do )
Entonces obtenemos:
i | 1 << i (binario) | x & (1 << i) (binario) |
|---|---|---|
| 6 | 1000000 | 1000000 |
| 5 | 100000 | 0 |
| 4 | 10000 | 0 |
| 3 | 1000 | 1000 |
| 2 | 100 | 100 |
| 1 | 10 | 0 |
| 0 | 1 | 1 |
El ciclo externo producirá todos los patrones de bits binarios posibles con tantos dígitos como valores haya en la matriz.
De esta manera, esos patrones de bits ( x ) en realidad describen todos los subconjuntos posibles de la matriz (un 1 bit significa: incluye el valor de la matriz correspondiente, un 0 significa: no lo incluye). El operador de desplazamiento de bits ayuda a aislar un bit en el patrón de bits, para decidir si incluir o no el valor de matriz correspondiente.
Ver MDN para la documentación sobre Bitwise AND ( & ) y desplazamiento a la izquierda ( << )