StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>well, just as an empirical solution for small N:</p> <p>blocks.py:</p> <pre><code>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 </code></pre> <p>and sample output:</p> <pre><code>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 </code></pre> <p>You'll note a few obvious (well, mostly obvious) things from the problem statement:</p> <ul> <li>the total # of permutations is always N!</li> <li>with the exception of N=1, there is no solution for L,R = (1,1): if a count in one direction is 1, then it implies the tallest block is on that end of the stack, so the count in the other direction has to be >= 2</li> <li>the situation is symmetric (reverse each permutation and you reverse the L,R count)</li> <li>if <code>p</code> is a permutation of N-1 blocks and has count (Lp,Rp), then the N permutations of block N inserted in each possible spot can have a count ranging from L = 1 to Lp+1, and R = 1 to Rp + 1.</li> </ul> <p>From the empirical output:</p> <ul> <li><p>the leftmost column or topmost row (where L = 1 or R = 1) with N blocks is the sum of the rows/columns with N-1 blocks: i.e. in @PengOne's notation,</p> <p><code>b(N,1,R) = sum(b(N-1,k,R-1) for k = 1 to N-R+1</code></p></li> <li><p>Each diagonal is a row of Pascal's triangle, times a constant factor K for that diagonal -- I can't prove this, but I'm sure someone can -- i.e.:</p> <p><code>b(N,L,R) = K * (L+R-2 choose L-1)</code> where <code>K = b(N,1,L+R-1)</code> </p></li> </ul> <p>So the computational complexity of computing b(N,L,R) is the same as the computational complexity of computing b(N,1,L+R-1) which is the first column (or row) in each triangle.</p> <p>This observation is probably 95% of the way towards an explicit solution (the other 5% I'm sure involves standard combinatoric identities, I'm not too familiar with those).</p> <hr> <p>A quick check with the <a href="http://oeis.org/" rel="nofollow noreferrer">Online Encyclopedia of Integer Sequences</a> shows that b(N,1,R) appears to be <a href="http://oeis.org/A094638" rel="nofollow noreferrer">OEIS sequence A094638</a>:</p> <blockquote> <p>A094638 Triangle read by rows: T(n,k) =|s(n,n+1-k)|, where s(n,k) are the signed Stirling numbers of the first kind (1<=k<=n; in other words, the unsigned Stirling numbers of the first kind in reverse order). 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</p> </blockquote> <p>As far as how to efficiently compute the <a href="http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind#Explicit_formula" rel="nofollow noreferrer">Stirling numbers of the first kind</a>, I'm not sure; Wikipedia gives an explicit formula but it looks like a nasty sum. This question (computing Stirling #s of the first kind) <a href="https://mathoverflow.net/questions/34151/simple-efficient-representation-of-stirling-numbers-of-the-first-kind">shows up on MathOverflow</a> and it looks like O(n^2), as PengOne hypothesizes.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload