Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In "Mathematics for the analysis of algorithms", I find the following problem.

How many permutations on $\{1 \dots n\}$ can be sorted by at most two bubble sort passes?

The book later goes on to say that it is $3^{n-2}\cdot 2$ which is the number of inversion tables $b_1 \dots b_n$ with all $b_j \leq 2$. I don't see how that works, as $4123$ is sorted in one pass and has $b_1 = 3$. Am I missing something?

I then tried to come up with a solution of my own by constructing and counting all such permutations. Say $B_k(n)$ is the number of permutations of $1 \dots n$, sorted in $k$ passes.

I found $B_1(n) = \sum \limits^{n-1}_{i=0} \binom{n-1}{i} = 2^{n-1}$ by assumption that every such permutation can be built by slicing $123\dots n$ into some chunks and moving the last number of each chunk to its front.

By a similar assumption it seems to me that $B_2(n) = \sum \limits ^n _{i=1} ~\sum \limits _{k_1 + k_2 + \cdots + k_i = n} ~\sum \limits^i _{j=1} B_1(k_j-1)$ with $k_j > 0$ and $B_1(0) = 1$. In words this is to slice $123 \dots n$ into $i$ chunks of size $k_i$ each and to move the largest number of each chunk as before, then to count $B_1$ of the length of the rest of the chunk.

I find myself unable to attack the above formula. If you could explain the answer my book gives, that would be lovely too.

share|improve this question
    
You need to explain what you mean by $b_j$, $d_i$, $k_j$, and so forth. Otherwise your question is not understandable. –  Henning Makholm Oct 25 '12 at 16:00
    
$b_k$ is properly introduced. $d_k$ appears to be used in the same way as in Wikipedia, but if so, there's a typo in the question and the first $b_j$ should be $d_j$? Also, if so, then $4123$ has $d_1=1$, since $1$ is the smaller element in one inversion, namely $41$, so everything seems to be OK there. You seem to be counting inversions involving $4$ as the larger element, but they don't matter. –  joriki Oct 25 '12 at 16:05
    
I infer from your edit that you're not using the same notation as the Wikipedia article after all. In that case you should indeed explain the notation. –  joriki Oct 25 '12 at 16:08
    
Sorry about the confusion. The book uses $b_k$ for the elements of the inversion table. –  Karolis Juodelė Oct 25 '12 at 16:15
    
You might be interested in this article. The last sentence gives (with a typo) the general formula that there are $(k+1)^{n-k}k!$ permutations of length $n\geqslant k$ sorted by $k$ bubble sort passes. –  David Bevan Oct 26 '12 at 9:13

1 Answer 1

up vote 1 down vote accepted

In each pass, an element can only be swapped once with an element greater than itself, since after that the pass moves on with the larger element and leaves the lesser one behind. Thus, a permutation cannot be swapped in two passes if there is an element that participates in more than two inversions as the lesser element. Conversely, if all elements are to the right of at most two greater elements, each pass is bound to sweep one of these past them, so the permutation can be sorted in two passes.

To find the number of permutations with each element participating in at most two inversions as the lesser element, place the elements in increasing order and note that for all elements up to $n-2$ you have three choices, then for $n-1$ you have two and for $n$ only one, yielding $2\cdot3^{n-2}$.

share|improve this answer
    
What is an inversion table? I found that the table of $x_1x_2 \dots x_n$ is $d_1 d_2 \dots d_n$ with $d_i = |\{x_j : i<j, x_i > x_j\}|$. This seems backwards from the way you are using it. –  Karolis Juodelė Oct 25 '12 at 16:24
    
@Karolis: I thought your book uses $b_k$? Anyway, I think if you understand the answer you should be able to apply it with whatever definition of an inversion table you find. –  joriki Oct 25 '12 at 16:32
    
This definition is from another book. Mine doesn't bother with definitions :). Regardless, I do understand now, thanks. I won't accept this for a few days though, as I'd like to hear about my own construction of $B_2$. –  Karolis Juodelė Oct 25 '12 at 16:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.