29 January 2008

Hoagies and permutations (yes, really!)

About once a week, I buy a hoagie from Wawa for lunch. (Apparently people not from the Philadelphia area think "Wawa" is a very funny word. Here's an explanation; basically Wawa the store is named after Wawa the town, which in turn is the name for the Canada Goose in the language of the people who lived there before Europeans did.) Today was such a day.

Now, when you go in and buy a hoagie, you order on a touch screen, and the touch screen prints out a receipt with a number on it. These numbers are assigned sequentially -- but for various reasons, people's orders don't get filled in the same order that people put in their orders. This is immensely frustrating, and gives one a visceral sense of why permutations with a lot of inversions are kind of annoying. (A permutation is just a reordering of some totally ordered set, say {1, 2, ..., n}; an inversion, informally, is what we have when a larger number comes before a smaller number. For example, 1 5 3 2 4 is a permutation of {1, 2, 3, 4, 5}; it has four inversions, namely the pairs (5, 3), (5, 2), (5, 4), and (3, 2). I know that some people define inversions a bit differently, looking at the position in which the offending numbers appear instead of the offending numbers themselves.) The reasons why orders don't come out in the same order they come in have to do with the fact that there are multiple people preparing orders in parallel (at least during the lunch rush; the dinner rush is much less intense, both because there are less people buying dinner than lunch on a university campus and because the times at which peopel eat dinner are more spread out than the times at which they eat lunch) and that some orders take longer to prepare than others. To a first approximation, there seem to be three classes of order: food which is already prepared, cold made-to-order things, and hot made-to-order things.)

The wait was long today, so I got to thinking -- basically this procedure is generating a permutation of the integers. But it's a permutation of the integers with only Θ(1) inversions per element; that is, for any given customer, the number of people who came in after them and yet get served before them is on average some constant number. (I have no idea what this number is.) If we consider, say, the permutation that's generated in this way over the course of an hour during the lunch rush, it might be a permutation of [100] with a few hundred inversions. A "typical" permutation of 100 has about 2,500 inversions -- as n gets large, the number of inversions of a permutation of n selected uniformly at random is approximately normally distributed with mean n(n-1)/4 and standard deviation on the order of n3/2/6. Efficiently generating a random permutation with, say, less than 10n inversions (for large n) is not just a matter of generating random permutations (which is easy) and throwing out the ones which you don't like; there are sampling algorithms which work this way, to sample uniformly at random from some subset of a set which it's easy to sample u. a. r. from -- but as far as I know they don't throw away all but a vanishingly small proportion of all the elements in the large set! I don't know if anybody's thought about this problem.


Anonymous said...

Hoagies? Sub? nahhhhhhhh its a hero.

And there"s no permatations: meatballs perm and gravy.

Just like there is only the BROOKLYN Dodgers. The oether F******** team is LALALALALA.

Anonymous said...

I gotta admit though even a amateur geek such as me thinks about lines, service, walking like this; and its nifty to see real geeks do the same.

[I'm brown-nosing you.]

Anonymous said...

I wish I could edit these posts after I publish [for some reason preview doesn't help]: first 'oether' should be 'other' and to be front front and open I do think like that 'brown nosing' was only admitting it.

"Hoagies" though is not a word! Heros.