Title :
Research on Algorithms for Random Permutation with Probability Weight
Author :
Yuan, Guo-Xiong ; Wang, Dong
Author_Institution :
Logistics Inf. Technol. & RFID Lab., Shanghai Jiao tong Univ., Shanghai, China
Abstract :
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.
Keywords :
computational complexity; probability; randomised algorithms; probability weight; random algorithm; random permutation; time complexity; Algorithm design and analysis; Approximation algorithms; Arrays; Complexity theory; Laboratories; Logistics; Sorting;
Conference_Titel :
Database Technology and Applications (DBTA), 2010 2nd International Workshop on
Conference_Location :
Wuhan
Print_ISBN :
978-1-4244-6975-8
Electronic_ISBN :
978-1-4244-6977-2
DOI :
10.1109/DBTA.2010.5658998