Stable matching and two simple tricks(mix and comparison)

Stable matching

Recently, we begin our computer science lessons for the second period in A2 in X. The first course is a very interesting subject: Stable matching, which emerges in various situation like job-seeking and the choice of our marriage. (Oh, it's all about the big problem.)

An algorithm proposed by Gale and Shapley is very simple and it applies the idea that we do every day. Imagine that n boys would like to choose their girlfriend and there are n women. Everyone has a list totally ordered. The unstable matching means in two couples, the man and woman have intention to break up and regroup a new couple. So the algorithm of Gale works like this: one guy begins to find his girlfriend from the top to bottom of his list. He dates the girl available or replace the ex-boyfriend. If the latter happens, the poor ex-boyfriend has to find another girlfriend.

This algorithm always works and finishes with a stable matching because the configuration is always stable. Moreover, the boyfriends of the girls become better and better(according to the personal criteria) and the boy never asks a girl two times(so sad).

To implement this algorithm, we have to pay attention to the complexity. We can cut the branching for economize the time, but the greatest problem is that we should construct a table for avoiding the time consumed in comparison between two men. After all, the complexity is about O(n^2).(We can use stacks and lists but they are not essential)

Some other version various is like we can join the possibility of preference of being single. That is to say, we can put ourselves in the list. Then, we will not get married with the man or woman after ourselves.

Tip: Do not put yourself at the first place of the list TT.

Knuth mix
How to make a permutation more random? This is a question. In the famous paper about riffle-shuffle, Diaconis tells us that 7 times can make a deck of cards very random, but it is just a asymptotic way not a perfect solution.

A method from Knuth: we do one cycle and each time, we do the exchange of cards between it and the cards before it.

Some simple calculus shows that it works, but how to get this idea is really amazing.

How many times to get the max and min?
We know n times comparison makes the max, so does min. But if we want both of them, we need 2n times?

NO!We take 2n number and group two-by-two so that n pairs. Then one comparison in every group makes the n "big-one" and n "small-one". The max is in the n "big-one" and the min is in the "small-one". So 3n times comparison make the result.

Therefore, generally, for n number, 3/2 * n times comparison get help us get both the max and the min.