wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Swapping 2n balls in n bins
        
(Message started by: Eigenray on Nov 24th, 2005, 4:30pm)
Title: Swapping 2n balls in n bins
Post by Eigenray on Nov 24th, 2005, 4:30pm
You are given n bins, labelled in order 1,2,...,n.  Bin 'k' contains two balls, both labelled 'n-k+1'.  If you can only swap balls between adjacent bins (one from each bin), what is the minimum number of swaps needed to get the balls in the right bins?

For example, when n=5, we wish to go from
(1,1)  (2,2)  (3,3)  (4,4)  (5,5)
to
(5,5)  (4,4)  (3,3)  (2,2)  (1,1).
Title: Re: Swapping 2n balls in n bins
Post by Icarus on Nov 24th, 2005, 7:37pm
If I am reading this correctly, what is the point of having two balls in each bin? If you can only swap pairs of balls, the two balls in each bin always stay together, and could be treated as a single ball.
Title: Re: Swapping 2n balls in n bins
Post by Eigenray on Nov 24th, 2005, 10:05pm
Okay that wasn't phrased well.  I mean you can only swap two balls at a time: one from bin k with one from bin k+1.
Title: Re: Swapping 2n balls in n bins
Post by JocK on Nov 26th, 2005, 1:55am

on 11/24/05 at 16:30:25, Eigenray wrote:
You are given n bins, labelled in order 1,2,...,n.  Bin 'k' contains two balls, both labelled 'n+k-1'.  


You mean bin 'k' contains two balls, each labelled 'n-k+1' ?

I guess an upper bound to S(n), the minimum number of swaps required, is S(n) <= n(n - 1).
Title: Re: Swapping 2n balls in n bins
Post by JocK on Nov 26th, 2005, 4:46am
Obviously, one can do better than the upper bound indicates. For n=3, a greedy algorithm (always swap two balls that are wrongly ordered and that carry labels with maximum difference) leads to a total of 5 swaps (one less than the upper bound):

3,3 / 2,2 / 1,1
3,3 / 1,2 / 1,2
1,3 / 3,2 / 1,2
1,3 / 1,2 / 3,2
1,1 / 3,2 / 3,2
1,1 / 2,2 / 3,3
Title: Re: Swapping 2n balls in n bins
Post by Eigenray on Nov 26th, 2005, 1:05pm
Yes.  In fact that is optimal for n=3.

It's a bit counter-intuitive.  My first impression was that it "obviously" takes twice as many swaps than the case of 1 ball in each bin.
Title: Re: Swapping 2n balls in n bins
Post by Deedlit on Nov 26th, 2005, 1:49pm
You can get a better lower bound by counting the number of pairs of balls that are misordered - that is, two balls are labelled m and n with m > n, but ball m is to the left of ball n.  At the start, there are 4 C(n, 2) = 2n (n - 1) misorderings.  Any swap can change remove at most 3 misorderings:  the two balls that are swapped, the ball on the left with the other ball on the right, and the ball on the right with the other ball on the left.  So to get the number of misorderings down to zero requires at lesast Ceil [2n (n - 1) / 3] swaps.

In addition, note that when the second ball labelled n is placed in its proper position, we don't get to reduce by 3;  the two balls labelled n were not considered misordred originally.  So we lose a reduction for each number 1 to n, and our lower bound increases to Ceil [(2n2 - n) / 3].

This bound is sharp for 2 <= n <= 5;  for these cases, a simple strategy is to move a ball labelled n and a ball labelled 1 next to each other near the center.  Then you just start shifting the balls to their correct places, starting from the extremes and working your way in, each time shifting with the more misplaced ball.  The first step takes n - 2 swaps, and these are 'bad swaps' according to Jock's [n2 / 2] formula;  they reduce one ball's misallocation by one, but increase the other by one, so the function stays the same.  Every swap after that is a 'good swap' - both balls have the misallocation reduced by one - so we reach the desired position in [n2 / 2] + n - 2 steps (which coincidentally, matches up with the previous formula for 2 <= n <= 6!)

For example, take n = 5:

5 4 3 2 1
5 4 3 2 1

The first step brings 5 and 1 together.

4 3 5 1 2
5 4 3 2 1

These are the three 'bad swaps'.  Next we move 5 all the way to the right; the 'most misallocated' balls to swap with are the two 1's, so those are swapped.

4 3 1 1 2
5 4 3 2 5

Next we move the 1's all the way to the left, this time choosing the largest number to swap from each time.

4 3 4 1 2
1 5 3 2 5

1 3 5 4 2
1 4 3 2 5

Next we swap the 5 and left 4 with the 2's and one more swap of 3 and 2 finishes it.  That's 15 swaps, 3 bad and 12 good, and that matches both formulas.

But it doesn't quite work for n = 6.  Using the strategy above, after first 1 and 6 are placed, we wind up needing to use one more bad swap to keep going, so we need to use 23 swaps rather than the 22 that both formulas give us.  (I haven't proven that 23 is required, though)  Perhaps the required number is asymptotic with n2 after all.
Title: Re: Swapping 2n balls in n bins
Post by JocK on Nov 26th, 2005, 3:13pm
Increasing the number of balls per bin from one to two, you need more swaps but in general not twice as many. For large number of bins you need about 50% more swaps.

However, I have not yet managed to figure out a general equation for the number of swaps required.
Title: Re: Swapping 2n balls in n bins
Post by Deedlit on Nov 26th, 2005, 3:18pm
Do you see a flaw with my lower bound?

EDIT: just realized that 50% more is more than my lower bound - got confused for a second.
Title: Re: Swapping 2n balls in n bins
Post by JocK on Nov 27th, 2005, 1:40am
Yes, so far all results are mutually compatible.

In fact, we can generalise to k times n balls in n bins. The required number of swaps S(k,n) is bounded by generalising my upper bound and your lower bound to arbitrary k>0:

Ceil((k2n(n-1)/2 + (k-1)n)/(2k-1))  <=  S(k,n)  <=  nk(n-1)/2

Obviously, for k=1 both bounds coincide, whilst for arbitrary n and k the ratio between the upper and the lower bound never exceeds (2k - 1)/k.

Asymptotically, S(n,k) = Ck n2 + O(n)  with:  k2/(4k-2)  <=  Ck  <=  k/2


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board