algorithm - segun - Entrevista de Google: organización de bloques

meme y memetica

Question

Se te dan N bloques de altura 1 ... N. ¿De cuántas maneras puede organizar estos bloques en una fila de manera que cuando se ve desde la izquierda solo vea L bloques (el resto esté oculto por bloques más altos) y cuando se ve desde la derecha solo vea R blocks? Ejemplo dado N=3, L=2, R=1 solo hay una disposición {2, 1, 3} mientras que para N=3, L=2, R=2 hay dos formas {1, 3, 2} y {2, 3, 1} .

¿Cómo deberíamos resolver este problema mediante la programación? ¿Alguna forma eficiente?

Answer 1

Aquí está mi solución de construcción inspirada en las ideas de @ PengOne.

import itertools
def f(blocks, m):
n = len(blocks)
if m > n:
return []
if m < 0:
return []
if n == m:
return [sorted(blocks)]
maximum = max(blocks)
blocks = list(set(blocks) - set([maximum]))
results = []
for k in range(0, n):
for left_set in itertools.combinations(blocks, k):
for left in f(left_set, m - 1):
rights = itertools.permutations(list(set(blocks) - set(left)))
for right in rights:
results.append(list(left) + [maximum] + list(right))
return results
def b(n, l, r):
blocks = range(1, n + 1)
results = []
maximum = max(blocks)
blocks = list(set(blocks) - set([maximum]))
for k in range(0, n):
for left_set in itertools.combinations(blocks, k):
for left in f(left_set, l - 1):
other = list(set(blocks) - set(left))
rights = f(other, r - 1)
for right in rights:
results.append(list(left) + [maximum] + list(right))
return results
# Sample
print b(4, 3, 2) # -> [[1, 2, 4, 3], [1, 3, 4, 2], [2, 3, 4, 1]]

Answer 2

Basado en la respuesta de @PengOne, aquí está mi implementación de Javascript :

function g(N, L, R) {
var acc = 0;
for (var k=1; k<=N; k++) {
acc += comb(N-1, k-1) * f(k-1, L-1) * f(N-k, R-1);
}
return acc;
}
function f(N, L) {
if (N==L) return 1;
else if (N<L) return 0;
else {
var acc = 0;
for (var k=1; k<=N; k++) {
acc += comb(N-1, k-1) * f(k-1, L-1) * fact(N-k);
}
return acc;
}
}
function comb(n, k) {
return fact(n) / (fact(k) * fact(n-k));
}
function fact(n) {
var acc = 1;
for (var i=2; i<=n; i++) {
acc *= i;
}
return acc;
}
$("#go").click(function () {
alert(g($("#N").val(), $("#L").val(), $("#R").val()));
});

Answer 3

Derivamos una solución general F(N, L, R) al examinar un caso de prueba específico: F(10, 4, 3) .

1. Primero consideramos 10 en la posición más a la izquierda posible, el 4 ( _ _ _ 10 _ _ _ _ _ _ ) .
2. Luego, encontramos el producto del número de secuencias válidas a la izquierda y a la derecha de 10.
3. A continuación, consideraremos 10 en la quinta ranura, calcularemos otro producto y lo agregaremos al anterior.
4. Este proceso continuará hasta que 10 esté en la última ranura posible, el 8vo.
5. Usaremos la variable llamada pos para hacer un seguimiento de la posición de N.
6. Ahora suponga pos = 6 ( _ _ _ _ _ 10 _ _ _ _ ) . A la izquierda de 10, hay 9C5 = (N-1)C(pos-1) conjuntos de números para organizar.
7. Como solo importa el orden de estos números, podríamos ver 1, 2, 3, 4, 5.
8. Para construir una secuencia con estos números para que 3 = L-1 de ellos sea visible desde la izquierda, podemos comenzar colocando 5 en la ranura posible más a la izquierda ( _ _ 5 _ _ ) y seguir pasos similares a los que hicimos antes.
9. Entonces, si F se definió recursivamente, podría usarse aquí.
10. La única diferencia ahora es que el orden de los números a la derecha de 5 es inmaterial.
11. Para resolver este problema, usaremos una señal, INF (infinito), para que R indique su falta de importancia.
12. Girando a la derecha de 10, quedarán 4 números de N-pos.
13. Primero consideramos 4 en la última ranura posible, posición 2 = R-1 desde la derecha ( _ _ 4 _ ) .
14. Aquí lo que aparece a la izquierda de 4 es inmaterial.
15. Pero contar arreglos de 4 bloques con la mera condición de que 2 de ellos sean visibles desde la derecha no es diferente a los arreglos de conteo de los mismos bloques con la mera condición de que 2 de ellos sean visibles desde la izquierda.
    • es decir. en lugar de contar secuencias como 3 1 4 2 , se pueden contar secuencias como 2 4 1 3
16. Entonces, el número de arreglos válidos a la derecha de 10 es F(4, 2, INF) .
17. Por lo tanto, el número de disposiciones cuando pos == 6 es 9C5 * F(5, 3, INF) * F(4, 2, INF) = (N-1)C(pos-1) * F(pos-1, L-1, INF)* F(N-pos, R-1, INF) .
18. De forma similar, en F(5, 3, INF) , 5 se considerarán en una sucesión de ranuras con L = 2 y así sucesivamente.
19. Como la función se llama con L o R reducida, debe devolver un valor cuando L = 1 , es decir, F(N, 1, INF) debe ser un caso base.
20. Ahora considere la disposición _ _ _ _ _ 6 7 10 _ _ .
    • La única ranura que 5 puede tomar es la primera, y las siguientes 4 ranuras pueden llenarse de cualquier manera; por lo tanto F(5, 1, INF) = 4! .
    • Entonces claramente F(N, 1, INF) = (N-1)! .
    • Se pueden ver otros casos y detalles de base (triviales) en la implementación de C a continuación.

Here hay un enlace para probar el código

#define INF UINT_MAX
long long unsigned fact(unsigned n) { return n ? n * fact(n-1) : 1; }
unsigned C(unsigned n, unsigned k) { return fact(n) / (fact(k) * fact(n-k)); }
unsigned F(unsigned N, unsigned L, unsigned R)
{
unsigned pos, sum = 0;
if(R != INF)
{
if(L == 0 || R == 0 || N < L || N < R) return 0;
if(L == 1) return F(N-1, R-1, INF);
if(R == 1) return F(N-1, L-1, INF);
for(pos = L; pos <= N-R+1; ++pos)
sum += C(N-1, pos-1) * F(pos-1, L-1, INF) * F(N-pos, R-1, INF);
}
else
{
if(L == 1) return fact(N-1);
for(pos = L; pos <= N; ++pos)
sum += C(N-1, pos-1) * F(pos-1, L-1, INF) * fact(N-pos);
}
return sum;
}

Answer 4

Este es un problema de conteo, no de construcción, por lo que podemos abordarlo recurriendo a la recursividad. Como el problema tiene dos partes naturales, mirando desde la izquierda y mirando desde la derecha, divídalo y resuelva solo una parte.

Sea b(N, L, R) el número de soluciones, y sea f(N, L) el número de disposiciones de N bloques para que L sea ​​visible desde la izquierda. Primero piense en f porque es más fácil.

ENFOQUE 1

Vamos a obtener las condiciones iniciales y luego ir a la recursividad. Si todos van a ser visibles, entonces deben ordenarse cada vez más, por lo que

f(N, N) = 1

Si se supone que hay bloques más visibles que bloques disponibles, entonces no podemos hacer nada, entonces

f(N, M) = 0 if N < M

Si solo un bloque debe ser visible, coloque primero el más grande y luego los demás en cualquier orden, por lo que

f(N,1) = (N-1)!

Finalmente, para la recursión, piense en la posición del bloque más alto, digamos que N está en el punto k de la izquierda. A continuación, elija los bloques que se le presentarán en las formas (N-1 choose k-1) , organice esos bloques para que sea exactamente L-1 visible desde la izquierda y ordene los bloques Nk detrás de N en el que desee, dando:

f(N, L) = sum_{1<=k<=N} (N-1 choose k-1) * f(k-1, L-1) * (N-k)!

De hecho, dado que f(x-1,L-1) = 0 para x<L , también podemos comenzar k en L lugar de 1 :

f(N, L) = sum_{L<=k<=N} (N-1 choose k-1) * f(k-1, L-1) * (N-k)!

Correcto, entonces ahora que se entiende el bit más fácil, usemos f para resolver el bit más difícil b . Nuevamente, use recursión basada en la posición del bloque más alto, de nuevo digamos que N está en la posición k desde la izquierda. Al igual que antes, elija los bloques antes de que en N-1 choose k-1 formas, pero ahora piense en cada lado de ese bloque por separado. Para los bloques k-1 quedan de N , asegúrese de que sean exactamente L-1 de ellos visibles. Para los bloques Nk derecha de N , asegúrese de que R-1 esté visible y luego invierta el orden que obtendría de f . Por lo tanto, la respuesta es:

b(N,L,R) = sum_{1<=k<=N} (N-1 choose k-1) * f(k-1, L-1) * f(N-k, R-1)

donde f está completamente resuelto arriba. Nuevamente, muchos términos serán cero, entonces solo queremos tomar k tal que k-1 >= L-1 y Nk >= R-1 para obtener

b(N,L,R) = sum_{L <= k <= N-R+1} (N-1 choose k-1) * f(k-1, L-1) * f(N-k, R-1)

ENFOQUE 2

Pensé en este problema de nuevo y encontré un enfoque un tanto más agradable que evita la suma.

Si trabajas el problema de la manera opuesta, eso es pensar en agregar el bloque más pequeño en lugar del bloque más grande, entonces la recurrencia para f vuelve mucho más simple. En este caso, con las mismas condiciones iniciales, la recurrencia es

f(N,L) = f(N-1,L-1) + (N-1) * f(N-1,L)

donde el primer término, f(N-1,L-1) , proviene de colocar el bloque más pequeño en la posición más a la izquierda, agregando así un bloque visible más (de ahí que L disminuya a L-1 ), y el segundo término, (N-1) * f(N-1,L) , representa la colocación del bloque más pequeño en cualquiera de las posiciones N-1 no frontales, en cuyo caso no es visible (por lo tanto, L permanece fijo).

Esta recursividad tiene la ventaja de siempre disminuir N , aunque hace que sea más difícil ver algunas fórmulas, por ejemplo f(N,N-1) = (N choose 2) . Esta fórmula es bastante fácil de mostrar a partir de la fórmula anterior, aunque no estoy seguro de cómo derivarla de esta recurrencia más simple.

Ahora, para volver al problema original y resolver para b , también podemos tomar un enfoque diferente. En lugar de la suma anterior, piense que los bloques visibles vienen en paquetes, de modo que si un bloque es visible desde la izquierda, entonces su paquete consta de todos los bloques a la derecha y delante del siguiente bloque visible desde la izquierda, y de manera similar, si un bloque es visible desde la derecha, entonces su paquete contiene todos los bloques que quedan de él hasta el próximo bloque visible desde la derecha. Haz esto para todos menos el bloque más alto. Esto hace que los paquetes L+R Dados los paquetes, puede mover uno desde el lado izquierdo al lado derecho simplemente invirtiendo el orden de los bloques. Por lo tanto, el caso general b(N,L,R) reduce a resolver el caso b(N,L,1) = f(N,L) y luego elegir cuál de los paquetes poner a la izquierda y cuál a la derecha . Por lo tanto, tenemos

b(N,L,R) = (L+R choose L) * f(N,L+R)

Nuevamente, esta reformulación tiene algunas ventajas sobre la versión anterior. Al unir estas dos últimas fórmulas, es mucho más fácil ver la complejidad del problema general. Sin embargo, aún prefiero el primer enfoque para construir soluciones, aunque quizás otros estarán en desacuerdo. En general, solo muestra que hay más de una buena manera de abordar el problema.

¿Qué pasa con los números de Stirling?

Como señala Jason, los números f(N,L) son precisamente los números Stirling (sin signo) del primer tipo . Uno puede ver esto inmediatamente de las fórmulas recursivas para cada uno. Sin embargo, siempre es bueno poder verlo directamente, así que aquí va.

Los números (no firmados) de Stirling del Primer Tipo, denotados S(N,L) cuentan el número de permutaciones de N en L ciclos. Dada una permutación escrita en notación cíclica, escribimos la permutación en forma canónica comenzando el ciclo con el número más grande en ese ciclo y ordenando los ciclos cada vez más en el primer número del ciclo. Por ejemplo, la permutación

(2 6) (5 1 4) (3 7)

sería escrito en forma canónica como

(5 1 4) (6 2) (7 3)

Ahora suelte los paréntesis y observe que si estas son las alturas de los bloques, ¡la cantidad de bloques visibles desde la izquierda es exactamente la cantidad de ciclos! Esto se debe a que el primer número de cada ciclo bloquea todos los demás números en el ciclo, y el primer número de cada ciclo sucesivo es visible detrás del ciclo anterior. Por lo tanto, este problema es solo una forma furtiva de pedirle que encuentre una fórmula para los números de Stirling.

Answer 5

bueno, solo como una solución empírica para N pequeña:

blocks.py:

import itertools
from collections import defaultdict
def countPermutation(p):
n = 0
max = 0
for block in p:
if block > max:
n += 1
max = block
return n
def countBlocks(n):
count = defaultdict(int)
for p in itertools.permutations(range(1,n+1)):
fwd = countPermutation(p)
rev = countPermutation(reversed(p))
count[(fwd,rev)] += 1
return count
def printCount(count, n, places):
for i in range(1,n+1):
for j in range(1,n+1):
c = count[(i,j)]
if c > 0:
print "%*d" % (places, count[(i,j)]),
else:
print " " * places ,
print
def countAndPrint(nmax, places):
for n in range(1,nmax+1):
printCount(countBlocks(n), n, places)
print

y muestra de salida:

blocks.countAndPrint(10)
1
1
1
1 1
1 2
1
2 3 1
2 6 3
3 3
1
6 11 6 1
6 22 18 4
11 18 6
6 4
1
24 50 35 10 1
24 100 105 40 5
50 105 60 10
35 40 10
10 5
1
120 274 225 85 15 1
120 548 675 340 75 6
274 675 510 150 15
225 340 150 20
85 75 15
15 6
1
720 1764 1624 735 175 21 1
720 3528 4872 2940 875 126 7
1764 4872 4410 1750 315 21
1624 2940 1750 420 35
735 875 315 35
175 126 21
21 7
1
5040 13068 13132 6769 1960 322 28 1
5040 26136 39396 27076 9800 1932 196 8
13068 39396 40614 19600 4830 588 28
13132 27076 19600 6440 980 56
6769 9800 4830 980 70
1960 1932 588 56
322 196 28
28 8
1
40320 109584 118124 67284 22449 4536 546 36 1
40320 219168 354372 269136 112245 27216 3822 288 9
109584 354372 403704 224490 68040 11466 1008 36
118124 269136 224490 90720 19110 2016 84
67284 112245 68040 19110 2520 126
22449 27216 11466 2016 126
4536 3822 1008 84
546 288 36
36 9
1

Notará algunas cosas obvias (bueno, en su mayoría obvias) del enunciado del problema:

• el número total de permutaciones es siempre N!
• con la excepción de N = 1, no hay solución para L, R = (1,1): si un conteo en una dirección es 1, entonces implica que el bloque más alto está en ese extremo de la pila, por lo que el recuento en la otra dirección tiene que ser> = 2
• la situación es simétrica (invertir cada permutación e invertir el recuento de L, R)
• si p es una permutación de bloques N-1 y tiene conteo (Lp, Rp), entonces las permutaciones N del bloque N insertadas en cada punto posible pueden tener un recuento que va de L = 1 a Lp + 1, y R = 1 a Rp + 1.

Del resultado empírico:

• la columna más a la izquierda o la fila más alta (donde L = 1 o R = 1) con N bloques es la suma de las filas / columnas con N-1 bloques: es decir, en la notación de @ PengOne,

  b(N,1,R) = sum(b(N-1,k,R-1) for k = 1 to N-R+1

• Cada diagonal es una fila del triángulo de Pascal, multiplicado por un factor constante K para esa diagonal; no puedo probarlo, pero estoy seguro de que alguien puede: es decir:

  b(N,L,R) = K * (L+R-2 choose L-1) donde K = b(N,1,L+R-1)

Entonces, la complejidad computacional de la computación b (N, L, R) es la misma que la complejidad computacional de la computación b (N, 1, L + R-1) que es la primera columna (o fila) en cada triángulo.

Esta observación es probablemente el 95% del camino hacia una solución explícita (el otro 5% estoy seguro involucra identidades combinatorias estándar, no estoy muy familiarizado con eso).

Una comprobación rápida con la Enciclopedia en línea de las secuencias de números enteros muestra que b (N, 1, R) parece ser la secuencia OEIS A094638 :

A094638 Triángulo leído por filas: T (n, k) = | s (n, n + 1-k) |, donde s (n, k) son los números de Stirling con signo del primer tipo (1 <= k <= n en otras palabras, los números de Stirling sin signo del primer tipo en orden inverso). 1, 1, 1, 1, 3, 2, 1, 6, 11, 6, 1, 10, 35, 50, 24, 1, 15, 85, 225, 274, 120, 1, 21, 175, 735, 1624, 1764, 720, 1, 28, 322, 1960, 6769, 13132, 13068, 5040, 1, 36, 546, 4536, 22449, 67284, 118124, 109584, 40320, 1, 45, 870, 9450, 63273, 269325, 723680, 1172700

En cuanto a cómo calcular de manera eficiente los números de Stirling del primer tipo , no estoy seguro; Wikipedia da una fórmula explícita, pero parece una suma desagradable. Esta pregunta (calculando Stirling #s del primer tipo) aparece en MathOverflow y se ve como O (n ^ 2), como lo plantea PengOne.