Research on Algorithms for Random Permutation with Probability Weight

As random algorithm can assure fairness, moreover, it can solve some of the problems which the definite algorithm can´t solve; the random algorithm has wide spread use. In this paper, it designed an algorithm with time complexity of Ø(NlgN) to solve the probability weight oriented permutation problem, further, the algorithm need no extra space. The probability weight oriented random permutation algorithm does not only guarantee that the permutation is random, but it also guarantees that the element with higher weight has higher probability of ranking in the front of the permutation, and vice versa. Basically, there are two types of algorithms for random permutation, one for the same possibilities and the other for different possibilities. Compare the result of the test and the original probability weight, It shows that the permutation is random and the permutation embodies the probability weight of each element.