mersenneforum.org Stacking boxes - combinatorics?
 Register FAQ Search Today's Posts Mark Forums Read

 2010-08-04, 16:47 #1 Ken_g6     Jan 2005 Caught in a sieve 2×197 Posts Stacking boxes - combinatorics? Here's a puzzle I'm working on right now. I promise it's not a homework problem. It's a problem for a program I'm considering. And I'm not sure if there's any easy solution without writing a program to solve it. It seems like combinatorics to me; but I never really studied combinatorics, so I'm hoping someone here knows an easy answer. Suppose you have 16 cubic boxes and 16 different places to stack them. They can be in any arrangement - for example they can be laid out one in each place, or all 16 can be stacked in one place. Order doesn't matter, and orientation doesn't matter. Now define the "maximum height" of any arrangement to be the height of the tallest stack in that arrangement. Question: What is the average "maximum height" for all possible arrangements of these boxes? Question 2: Can you guess what problem I'm trying to solve here?
 2010-08-04, 17:14 #2 CRGreathouse     Aug 2006 11·13·41 Posts For 1, I get 19/3. I'm using inefficient code based on Sloane's A008284 (my code has trouble even getting to n = 60). For 2, I have no idea.
 2010-08-04, 17:17 #3 Wacky     Jun 2003 The Texas Hill Country 32×112 Posts Question: When you take an "average", it matters how many times you count each possible combination of stack sizes. So, do you consider 8-7-1 and 8-1-7 to be the same? Or are you trying to determine the expected value of the maximum number of objects that would fall in the same hash bucket - given that there is a total of 16 objects and the hash function provides a perfectly uniform hash into 16 buckets?
2010-08-04, 17:22   #4
CRGreathouse

Aug 2006

11×13×41 Posts

Quote:
 Originally Posted by Wacky Question: When you take an "average", it matters how many times you count each possible combination of stack sizes.
The OP said that orientation and order don't matter, so that's what I assumed in my answer. Obviously if a different weighting was intended then the answer will be different.

 2010-08-04, 17:42 #5 Ken_g6     Jan 2005 Caught in a sieve 18A16 Posts That's a good question. I'm not quite sure what terminology to use. Let me give an example where N=2, not 16. There are three possibilities: X X_ _X _X and just XX Technically, the boxes do have numbers, but I imagine what their number is doesn't matter. Let me explain #2: In nVIDIA's CUDA system, there's a user-managed cache of memory called "shared memory". Threads access it 16 at a time. nVIDIA rather assumed that the user would access it linearly, so they set up 16 banks of memory, where the bank accessed is the address mod 16. If two threads access the same bank, it takes two accesses instead of one; three takes three accesses and so on. Well, for my application, I would need a random-access lookup table. If CRGreathouse is correct, that's over 6 accesses on average - not good. But thanks for solving that for me; it would have taken me hours writing an optimized recursive program.
2010-08-04, 17:58   #6
jyb

Aug 2005
Seattle, WA

32·173 Posts

Quote:
 Originally Posted by Ken_g6 Question 2: Can you guess what problem I'm trying to solve here?
I'd guess you're trying to solve problem 12-3 in CLR (though that only gives you an upper bound on the expected maximum, not an exact value).

2010-08-04, 18:05   #7
CRGreathouse

Aug 2006

133478 Posts

Quote:
 Originally Posted by Ken_g6 If CRGreathouse is correct, that's over 6 accesses on average - not good.
You described a different weighting scheme in your last post than I used, so my result (while correct for what it was) does not directly apply to you.

 2010-08-04, 18:25 #8 Ken_g6     Jan 2005 Caught in a sieve 2×197 Posts What's CLR? Common Language Runtime? My Google-fu is weak. Edit: Found it. I may have that book; let me look. Edit2: Hm, hash chains, that's a good way to look at it, where n=m. Last fiddled with by Ken_g6 on 2010-08-04 at 18:29
 2010-08-04, 19:03 #9 Ken_g6     Jan 2005 Caught in a sieve 2×197 Posts OK, having looked over 12-3, that seems like the right problem, but I don't believe the solution (M=lg(16)/lg(lg(16) == 2 in this case). It seems to me that there's only one way to get M=1, and several ways to get M>=3. Edit: Oh, I see, there's a constant. Anyone know what the constant is? Last fiddled with by Ken_g6 on 2010-08-04 at 19:04
 2010-08-04, 19:21 #10 CRGreathouse     Aug 2006 11×13×41 Posts Maybe what you want is Sloane's A019575? Look at that and tell me what you think.
 2010-08-04, 20:26 #11 Ken_g6     Jan 2005 Caught in a sieve 2·197 Posts That's darn close. What I'm looking for is based on that: sum(k=1 to n, T(n,k)*k)/sum(k=1 to n, T(n,k)) Now how's that T(n,k) calculated? The "Formula" section is unclear to me. Edit: I'm also confused; shouldn't T(n,n) = 1 or n or something? But maybe I'm wrong about that? Last fiddled with by Ken_g6 on 2010-08-04 at 20:28

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Combinatorics & Combinatorial Number Theory 7 2019-12-14 15:25 goatboy Math 1 2007-12-07 12:30 victor Puzzles 1 2007-06-04 16:26 Kees Puzzles 6 2006-05-13 06:58 Numbers Hardware 7 2005-09-12 19:10

All times are UTC. The time now is 00:40.

Fri Aug 7 00:40:07 UTC 2020 up 20 days, 20:26, 1 user, load averages: 1.50, 1.56, 1.47