All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Skyscraper Counting (Posted on 2009-03-16)
Consider a skyscraper problem on a 9x9 board. When a number is visible on the edge there will be some number of possible arrangements of buildings that could achieve this.

Find the number of possible arrangements of building if the edge number is each of {1,2,3,4,5,6,7,8,9}

For example on a 3x3 board there are three possibilities if a 2 is visible on the end (viewing from the left): (1,3,2), (2,3,1), (2,1,3)

(1,3,2), (2,3,1), (2,1,3)
What you would see:

 No Solution Yet Submitted by Jer No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 analytic explanation of recursion formula Comment 3 of 3 |
(In reply to solution by Charlie)

The formula:

IF k = 0 THEN
t(n, k) = fact(n)
ELSE
t(n, k) = t(n - 1, k - 1) + n * t(n - 1, k)
END IF

is defined such that the n is 1 less than the number of buildings and k is 1 less than the number of visible buildings. Define a new function where n is the number of buildings and k is the number of visible buildings by substituting n-1 for n and k-1 for k, so that the formula is:

For k=1, W(n,k) = (n-1)!
otherwise W(n,k) = W(n-1,k-1) + (n-1)*W(n-1,k)

(note when a previous recursion is referenced, the n and k stay the same, as that definition has changed already)

Here's a derivation:

If only 1 building is to be visible, the tallest is in front and the remaining buildings can be arranged in (n-1)! ways.

If more than 1 building is visible, either the newly added (tallest) building is at the back or some other building is at the back.

If the tallest building is at the back, then each arrangement of n-1 buildings with k-1 visible becomes an arrangement with k visible, accounting for the first term in the formula for W(n,k).

If the tallest building is not at the back, then some other building is, and there are (n-1) such other buildings. Whichever that building is, it will not be visible as the tallest building comes before it. And the remaining buildings (including the tallest), become a set of n-1 buildings with k needed to be visible and the number of arrangements of that is W(n-1,k). Thus the remaining term is found.

The new recursion checks out:

DECLARE FUNCTION fact# (x#)
DEFDBL A-Z
FOR n = 1 TO 10
FOR k = 1 TO n
IF k = 1 THEN
W(n, k) = fact(n - 1)
ELSE
W(n, k) = W(n - 1, k - 1) + (n - 1) * W(n - 1, k)
END IF
PRINT W(n, k);
NEXT
PRINT
NEXT

FUNCTION fact (x)
f = 1
FOR i = 1 TO x
f = f * i
NEXT
fact = f
END FUNCTION

`11  12  3  16  11  6  124  50  35  10  1120  274  225  85  15  1720  1764  1624  735  175  21  15040  13068  13132  6769  1960  322  28  140320  109584  118124  67284  22449  4536  546  36  1362880  1026576  1172700  723680  269325  63273  9450  870  45  1`

Edited on March 16, 2009, 4:06 pm
 Posted by Charlie on 2009-03-16 16:04:41

 Search: Search body:
Forums (0)