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 n^3/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.