-----------------------------------

klopyrev

Wed Mar 07, 2007 5:59 pm


Sorting

-----------------------------------

Suppose you have a permutation of n elements. Here is an example of 7:

2 1 3 7 4 5 6

Here are two ways to sort it:

2 1 3 7 4 5 6
Swap 2 and 1

1 2 3 7 4 5 6
Swap 7 and 4

1 2 3 4 7 5 6
Swap 7 and 5

1 2 3 4 5 7 6
Swap 7 and 6

1 2 3 4 5 6 7

Second way:

2 1 3 7 4 5 6
Swap 2 and 1

1 2 3 7 4 5 6
Swap 6 and 7

1 2 3 6 4 5 7
Swap 4 and 5

1 2 3 6 5 4 7
Swap 4 and 6

1 2 3 4 5 6 7

In the first example, the element 7 is moved 3 times. In fact, 3 times is the maximum number of times any element is moved. In the second example, both 4 and 6 are moved 2 times. In fact, 2 times is the maximum number of times any element is moved. Provide an algorithm for minimizing the maximum of the number of times any element is moved. (0 < n < 5000)

KL


-----------------------------------

wtd

Wed Mar 07, 2007 7:39 pm


RE:Sorting

-----------------------------------

In anything other than very large cases, trying to deduce a better way to sort is probably going to be more resource intensive than just using quicksort.  :)


-----------------------------------

rdrake

Wed Mar 07, 2007 9:22 pm


RE:Sorting

-----------------------------------

Looks bubblesortyish to me.


-----------------------------------

Martin

Wed Mar 07, 2007 9:25 pm


RE:Sorting

-----------------------------------

Although in C++, the STL uses an introsort, which is a quicksort to a specific depth of recursion and then a merge sort for the rest.

That aside, I'm not really sure what you're asking klopyrev. Do they want you to derive the algorithm, or for this algorithm, prove what the minimum swaps are be in relation to n?


-----------------------------------

klopyrev

Wed Mar 07, 2007 9:31 pm


Re: Sorting

-----------------------------------

I need any algorithm to do that, because I ran out of ideas :P

KL


That aside, I'm not really sure what you're asking klopyrev. Do they want you to derive the algorithm, or for this algorithm, prove what the minimum swaps are be in relation to n?

Actually, the minimum number of swaps needed will always be the number of inverses there are in the sequence ( an inverse is ai > aj, i 1 2

3 --> 3

4 5 6 7 -> 7 4 5 6

the answer is ceil(n/2) where n is the longest cycle.  n/2 is a bit greedy, not entirely sure if it works.  if it doesnt some memo/dp approach is needed.


-----------------------------------

bugzpodder

Thu Mar 08, 2007 8:19 am


Re: Sorting

-----------------------------------

I think here is a very simple algorithm that realizes n/2 swaps where n is the longest cycle.  is your brother gonna use it as an interview question? :P  Havent tried to compile the code yet so no idea if it works or not.  



flag = true;
while (1) {
    flag = false;
    for (int i=0;i= 0 ; i--)
        {
            int s = days [i].size ();
            System.out.print (days [i].size ());
            ListIterator iter = days [i].listIterator ();
            while (iter.hasNext ())
                System.out.print (" " + iter.next ());
            System.out.println ();

        }
    }
}
class Swap
{
    int a;
    int b;
    public Swap (int a, int b)
    {
        if (a < b)
        {
            this.a = a;
            this.b = b;
        }
        else
        {
            this.b = a;
            this.a = b;
        }
    }


    public String toString ()
    {
        return a + "-" + b;
    }
}



-----------------------------------

Brightguy

Fri Mar 09, 2007 12:06 am


Re: RE:Sorting

-----------------------------------

In anything other than very large cases, trying to deduce a better way to sort is probably going to be more resource intensive than just using quicksort.  :)
Heh, you shamelessly open that can of worms!  Just don't say that in an algorithms class or you'll get kicked out on the spot. :P  However, it turns out this was a very bad problem for you to say that.  There is a simple algorithm that performs better than quicksort in every possible case, as well as being much easier to code.

It looks like bugz essentially has it, though I don't know where he got the n/2 thing from.  The minimum number transpositions needed to represent any permutation of n elements is n - r, where r is the number of distinct cycles.  Since there is always at least 1 cycle, in the worst case n-1 swaps will be the minimum number of swaps needed.


-----------------------------------

bugzpodder

Fri Mar 09, 2007 1:20 am


RE:Sorting

-----------------------------------

I can't find a bug in the code.  but something may be of interest to you, you could cut the length of your code by half by just printing the swaps in the middle of the loop instead of creating those linked lists and have a new swap class.  either attach them to a string or if its too slow, some kind of buffered writer.


Here are some theoretical proof that doesnt exactly proof my claims, but it does prove something.

1. every permutation can be divided into disjoint cycles.  By a bijection we can assume each cycle is in the form:

1 2 3 .. n-1 n
2 3 4 .. n    1

Thus let f(n) be the number of days needed to get the trades done in a cycle of length n.

Notice we can greedily only trade between members in the cycle, since there is no point in involving traders in another cycle.

Now I show my algorithm is correct (well there is a flaw somewhere, either in the algorithm or in its implementation)

In a cycle, we can make at most floor (n/2) trades in a day.  However what we are doing is placing exactly floor(n/2) traders with the item they desire, so this is the best we can do ever.  In a single trade in a cycle of n>2, we can never match the request for two traders simultaneously, since it would mean that they form a cycle of 2.


-----------------------------------

klopyrev

Fri Mar 09, 2007 2:15 am


Re: Sorting

-----------------------------------

Cutting down in size by printing inside the actual loop will not work, because I have to print all the days backwards, since the starting point is 1 2 3 4 5 6 7 and you have to get 2 1 3 5 6 7 4. Otherwise, I really don't understand why its wrong either. Take a look at the translation of the original problem I posted and perhaps you can help me think of cases that will break my code. Thanks for the input. I'm going to take a look at the sorting chapter in Art of Computer Programming now to see if I can find something to help me out.

KL


-----------------------------------

bugzpodder

Fri Mar 09, 2007 2:21 am


RE:Sorting

-----------------------------------

i figured out what the fuck was wrong (i think)

consider this case:
1 7 8 2 ..
7 8 2 3 ..

the point is 8 would skipped.  I want to switch adjacent elements in a cycle, but the way I did it it was breaking the cycle which is bad.  

btw you owe me an hour of sleep :P


-----------------------------------

klopyrev

Fri Mar 09, 2007 2:31 am


Re: Sorting

-----------------------------------

I don't completely understand what you mean.

KL


-----------------------------------

bugzpodder

Fri Mar 09, 2007 9:50 am


RE:Sorting

-----------------------------------

you have to follow through a cycle.  if the cycle are in the order

1 7 8 2 5 4

you must swap 1,7 8,2 5,4
if you swap in order, you might swap 1,7 2,5


-----------------------------------

klopyrev

Fri Mar 09, 2007 3:11 pm


Re: Sorting

-----------------------------------

I still don't understand how that applies to this problem  :(


-----------------------------------

bugzpodder

Fri Mar 09, 2007 4:10 pm


Re: Sorting

-----------------------------------

that means you can't swap arr[i] with arr[arr[i]] because you'll end up with things like 1,7 2,5 which skips an element in the middle (which is bad if you skip several single elements in a chain)


-----------------------------------

klopyrev

Fri Mar 09, 2007 4:39 pm


Re: Sorting

-----------------------------------

But if you skip the element, you then get it during the next day? Can you give me a complete example of the algorithm not working. I'm kind of slow :(


-----------------------------------

bugzpodder

Fri Mar 09, 2007 10:45 pm


RE:Sorting

-----------------------------------

but we want to get as many trades in as possible in a single day right?  hmm lets see... its difficult to construct


1 2 3 4 5 6 7 8
4 6 1 5 2 7 8 3
that is my starting point

1 2 3 4 5 6 7 8
5 7 1 4 2 6 3 8

1 2 3 4 5 6 7 8
2 3 1 4 5 6 7 8

1 2 3 4 5 6 7 8
3 2 1 4 5 6 7 8

1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8

so this is 4 days.



1 4 5 2 6 7 8 3
4 5 2 6 7 8 3 1

1 4 5 2 6 7 8 3
5 4 6 2 8 7 1 3

1 4 5 2 6 7 8 3
6 4 5 2 1 7 8 3

1 4 5 2 6 7 8 3
1 4 5 2 6 7 8 3

three steps


-----------------------------------

Brightguy

Sat Mar 10, 2007 7:45 am


Re: Sorting

-----------------------------------

Oh, I see now the problem was modified to minimize days, but n/2 still isn't right.  For a cycle of length n you can do a maximum of floor(n/2) swaps per day, but you still have a cycle of ceil(n/2) left over... so if n is the length of the longest of the cycles, then ceil(lg(n)) is the minimum number of days.  (lg is base 2)

Here's the algorithm to solve your original problem in a minimum number of steps:
for(int i=0; i