Interview de Google : Disposition des blocs

Question

Vous êtes donné des N blocs de hauteur 1...N. de combien De façons pouvez-vous organiser ces blocs dans une rangée, tels que, vu de gauche, vous voyez uniquement L de blocs de repos sont cachés par les plus grands blocs) et quand il est vu de droite, vous voyez seulement la R des blocs? Exemple N=3, L=2, R=1 il y a seulement un arrangement {2, 1, 3} tandis que pour d' N=3, L=2, R=2 il y a deux façons {1, 3, 2} et {2, 3, 1}.

Comment devrions-nous résoudre ce problème par la programmation? De toute façons efficaces?

Answer 1

C'est un problème de comptage, pas un problème de construction, de sorte que nous pouvons nous approcher en utilisant la récursivité. Depuis le problème a deux parties, à la recherche de la gauche et de la recherche à partir de la droite, de le diviser et de le résoudre pour une première partie.

Laissez - b(N, L, R) le nombre de solutions, et laissez - f(N, L) le nombre d'arrangements de N blocs de sorte qu' L sont visibles à partir de la gauche. D'abord pensez - f parce que c'est plus facile.

APPROCHE 1

Commençons par les conditions initiales et puis aller pour la récursivité. Si tout le monde doit être visible, ils doivent être commandés de plus en plus, de sorte

f(N, N) = 1

Si il y a supposer pour être plus visible blocs de blocs disponibles, alors nous ne pouvons rien faire, donc

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

Si seulement un pâté de maisons devraient être visibles, puis de les mettre le plus en premier, puis les autres peuvent suivre dans n'importe quel ordre, afin de

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

Enfin, pour la récursivité, pensez à la position de la plus haute bloc, dire N est le kème place à partir de la gauche. Ensuite, choisissez les blocs à venir avant elle, en (N-1 choose k-1) façons, organiser les blocs de sorte que exactement L-1 sont visibles à partir de la gauche, et de l'ordre de l' N-k blocs derrière N dans tout ce que vous souhaitez, donner:

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

En fait, depuis f(x-1,L-1) = 0 pour x<L, on peut aussi bien le début k à L au lieu de 1:

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

Bon, alors maintenant que le plus facile est peu compris, nous allons utiliser f à régler pour le plus difficile bits b. Encore une fois, utiliser la récursivité en fonction de la position de la plus haute bloc, encore une fois dire N est en position k à partir de la gauche. Comme avant, choisir les blocs avant de en N-1 choose k-1 façons, mais maintenant, pensez à chaque côté de ce bloc séparément. Pour l' k-1 blocs de gauche de N, assurez-vous que L-1 d'entre eux sont visibles. Pour l' N-k blocs de droit de l' N, assurez-vous que R-1 sont visibles et ensuite inverser l'ordre de f. Donc la réponse est:

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

où f est entièrement travaillé ci-dessus. Encore une fois, de nombreux termes sera de zéro, de sorte que nous ne voulons prendre en k tels que k-1 >= L-1 et N-k >= R-1 pour obtenir

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)

---

APPROCHE 2

J'ai pensé à ce problème et a trouvé un peu plus agréable qui évite la sommation.

Si vous travaillez le problème le chemin inverse, c'est penser à ajouter le plus petit bloc au lieu de la plus grande à bloc, puis la récurrence pour f devient beaucoup plus simple. Dans ce cas, avec les mêmes conditions initiales, de la récurrence

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

où le premier terme, f(N-1,L-1), vient de placer le plus petit bloc dans la position la plus à gauche, ce qui ajoute un plus visibles bloc (d'où l' L diminue d' L-1), et le deuxième terme, (N-1) * f(N-1,L), les comptes pour mettre le plus petit bloc en une de la N-1 non avant postes, dans ce cas il n'est pas visible (d'où l' L reste fixe).

Cette récursivité a l'avantage de toujours diminuant N, si elle rend plus difficile de voir certaines formules, par exemple f(N,N-1) = (N choose 2). Cette formule est assez facile de montrer à partir de la formule précédente, bien que je ne suis pas sûr de la façon de dériver gentiment, à partir de ce simple récurrence.

Maintenant, pour revenir à l'origine du problème et résoudre b, nous pouvons également prendre une approche différente. Au lieu de la somme avant, pensez à les blocs visibles comme venant de paquets, de sorte que si un bloc est visible à partir de la gauche, puis son paquet se compose de tous les blocs de droite et en face du bloc suivant, visible à partir de la gauche, et de même, si un bloc est visible à partir de la droite alors son paquet contient tous les blocs à gauche jusqu'au prochain bloc visible à partir de la droite. Faites cela pour tous, mais le plus grand bloc. Ce qui rend pour l' L+R des paquets. Compte tenu de la forme de paquets, vous pouvez déplacer l'un du côté gauche au côté droit, simplement en inversant l'ordre des blocs. Donc le cas général, b(N,L,R) réduit en réalité à la résolution du cas b(N,L,1) = f(N,L) , puis de choisir les paquets à mettre sur la gauche et qui, sur la droite. Par conséquent, nous avons

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

Encore une fois, cette reformulation a certains avantages par rapport à la version précédente. Mettre ces deux dernières formules, il est beaucoup plus facile de voir la complexité de l'ensemble du problème. Cependant, je préfère encore la première approche pour construire des solutions, mais peut-être que d'autres personnes ne seront pas d'accord. Dans l'ensemble, il va juste pour montrer il y a plus d'une bonne façon d'aborder le problème.

---

Ce qui est avec les nombres de Stirling?

Comme Jason points, l' f(N,L) numéros sont précisément les (non signé) nombres de Stirling de première espèce. On peut le voir immédiatement à partir de la récursivité des formules pour chacun. Cependant, il est toujours agréable d'être en mesure de voir directement, donc voilà.

La (non signé) nombres de Stirling de Première Espèce, notée S(N,L) de compter le nombre de permutations de l' N en L des cycles. Compte tenu d'une permutation écrit dans le cycle de la notation, nous écrivons la permutation dans la forme canonique en début du cycle avec le plus grand nombre dans ce cycle et puis, ordonnant que les cycles de plus en plus par le premier numéro du cycle. Par exemple, la permutation

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

serait écrite dans la forme canonique comme

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

Maintenant déposer les parenthèses et les avis que si ce sont les hauteurs des blocs, puis le nombre de blocs visibles à partir de la gauche est exactement le nombre de cycles! C'est parce que le premier nombre de chaque cycle de blocs de tous les autres numéros dans le cycle, et le premier numéro de chaque cycle est visible derrière le cycle précédent. D'où ce problème est vraiment juste une façon détournée de vous demander de trouver une formule pour les nombres de Stirling.

Answer 2

eh bien, tout comme une analyse empirique de solution pour les petits N:

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

et un exemple de résultat:

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

Vous remarquerez quelques évident (bien, surtout évidente) des choses à partir de l'énoncé du problème:

• le nombre total de permutations est toujours N!
• à l'exception de N=1, il n'y a pas de solution pour L,R = (1,1): si un nombre dans une direction est 1, alors il implique le plus grand bloc est sur que la fin de la pile, de sorte que le comte dans l'autre sens doit être >= 2
• la situation est symétrique (reverse chaque permutation et vous inverser la L,R le comte)
• si p est une permutation de N-1 blocs et a count (Lp,Rp), puis le N permutations de bloc N insérée dans chaque spot peut avoir un nombre allant de L = 1 Lp+1 et R = 1 bi + 1.

À partir de l'empirique de sortie:

• le plus à gauche de la colonne ou de la ligne supérieure (où L = 1 ou R = 1) avec des blocs de N est la somme de la les lignes/colonnes à N-1 blocs: c'est à dire dans @PengOne de notation,

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

• Chaque diagonale est une ligne du triangle de Pascal, fois une constante K pour que la diagonale -- je ne peux pas le prouver, mais je suis sûr que quelqu'un le peut, c'est à dire:

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

Donc, la complexité de calcul de calcul de b(N,L,R) est la même que la complexité de calcul de calcul de b(N,1,L+R-1) qui est la première colonne (ou une ligne) dans chaque triangle.

Cette observation est probablement 95% du chemin vers une solution explicite (les 5 autres% je suis sûr que comporte la norme identités combinatoires, je ne suis pas trop familier avec ceux-ci).

---

Une vérification rapide avec le Online Encyclopedia of Integer sequences montre que b(N,1,R) semble être OEIS séquence A094638:

A094638 Triangle de lecture par lignes: T(n,k) =|s(n,n+1-k)|, où s(n,k) sont signés, les nombres de Stirling de première espèce (1<=k<=n; en d'autres termes, la non signé nombres de Stirling de première espèce dans l'ordre inverse). 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

Aussi loin que la façon la plus efficace de calculer les nombres de Stirling de première espèce, je ne suis pas sûr; Wikipédia donne une formule explicite, mais il ressemble à un méchant somme. Cette question (le calcul de Stirling #s de première espèce) s'affiche sur MathOverflow et il semble que O(n^2), comme PengOne émet l'hypothèse.

Answer 3

Basée sur la réponse de @PengOne, voici mon implémentation de Javascript:

Answer 4

Nous tirons une solution de F(N, L, R) l'examen de F(10, 4, 3). Nous examinons d'abord 10 dans le plus à gauche possible, la position, la 4ème ( _ _ _ 10 _ _ _ _ _ _ ). Ensuite, nous trouvons le produit du nombre de séquences dans la gauche et dans la droite de 10. Ensuite, nous allons envisager de 10 dans le 5ème slot, calculer un autre produit et l'ajouter à la précédente. Ce processus va se poursuivre jusqu'à 10 dans le dernier emplacement possible de, le 8e. Nous allons utiliser une variable "pos" pour garder une trace de la N de la position. Supposons maintenant que pos = 6 ( _ _ _ _ _ 10 _ _ _ _ ). Dans la gauche de 10, il y a 9C5 = (N-1)C(pos-1) ensembles de nombres à être organisées. Depuis que l'ordre de ces numéros de questions, nous pourrions regarder l'1, 2, 3, 4, 5. Pour construire une séquence avec ces chiffres, alors que 3 = L-1 d'entre eux sont visibles à partir de la gauche, nous pouvons commencer par placer 5 dans le plus à gauche possible fente ( _ _ 5 _ _ ) et suivez les étapes similaires à ce que nous avons fait avant. Donc, si F ont été définies de manière récursive, il pourrait être utilisé ici. Maintenant la seule différence est que l'ordre des nombres dans le bon de 5 est sans importance. Pour résoudre ce problème, nous allons utiliser un signal, INF (infini), pour R pour indiquer son importance. En tournant à droite, de 10, il y aura 4 = N-pos les valeurs de gauche. Nous examinons d'abord 4 dans le dernier emplacement possible, la position 2 = R-1 à partir de la droite ( _ _ 4 _ ). Voici ce qui s'affiche dans la partie gauche de la 4 est sans importance. Mais en comptant les arrangements de 4 blocs avec la simple condition que 2 d'entre eux devrait être visible à partir de la droite n'est pas différent que de compter les dispositions des mêmes blocs avec la simple condition que 2 d'entre eux devrait être visible à partir de la gauche. (En d'autres termes, au lieu de compter les séquences comme 3 1 4 2, on peut compter les séquences comme 2 4 1 3.) Ainsi, le nombre de dispositions dans le droit de la 10 est F(4, 2, INF). Ainsi, le nombre de dispositifs lors de la pos=6 est 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). De même, F(5, 3, INF), 5 sera examiné lors d'une succession de créneaux avec L = 2 et ainsi de suite. Étant donné que la fonction s'appelle elle-même avec L ou R réduite, elle doit retourner une valeur lorsque L = 1, soit F(N, 1, INF) doit être un cas de base. Considérons maintenant l'arrangement _ _ _ _ _ 6 7 10 _ _. La seule fente 5 est le premier, et à la suite de 4 fentes peuvent être remplis de toute autre manière; donc F(5, 1, INF) = 4!. Il est clair que F(N, 1, INF) = (N-1)!. D'autres (trivial) de la base de cas et les détails peuvent être vu dans le C mise en œuvre ci-dessous. Voici un lien pour tester le code.

#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 5

Une façon de résoudre ce pourrait être comme suit:

compte tenu des piliers de hauteur {1,2,3,...,N}, et L,R > 0.s.t. L+R-1 <= N, procédez de la manière suivante:

prendre la L plus grand nombre de {1,2,3,...,N}, soit {N-L+1,N-L+2,...,N} et de les garder dans cet ordre. Maintenant passer à la prochaine R-1 plus grand nombre d'autres chiffres et de les trier dans l'ordre décroissant, c'est à dire : {N-L,N-L-1,...,N-L-R+2}.

Maintenant ajouter cette séquence à la fin de la longueur L de la séquence construit plus tôt, et de mettre tous les numéros restants entre deux éléments de cette plus grande séquence(dire le 1er et le 2ème), pour obtenir:

N-L+1, 1, 2, 3,..., N-L-R+3, N-L+2, N-L+3,..., N, N-L, N-L-1,..., N-L-R+1, N-L-R+2. 

Cette séquence satisfait les propriétés requises.