In-place random list permutations

機構典藏 > College of Engineering > Graduate Institute & Department of Computer Science and Information Engineering > Journal Article > Item 987654321/45370

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/45370

Title:	In-place random list permutations
Authors:	Hwang, Wen-ping;王慶林;Wang, Ching-lin
Contributors:	淡江大學資訊工程學系
Keywords:	Algorithms;Data structures
Date:	1999-06-30
Issue Date:	2010-03-26 19:09:07 (UTC+8)
Publisher:	Elsevier
Abstract:	We give two algorithms to randomly permute a linked list of length n in place using O(nlogn) time and O(logn) stack space in both the expected case and the worst case. The first algorithm uses well-known sequential random sampling, and the second uses inverted sequential random sampling.
Relation:	Information processing letters 70(6), pp.255-257
DOI:	10.1016/S0020-0190(99)00076-9
Appears in Collections:	[Graduate Institute & Department of Computer Science and Information Engineering] Journal Article

Files in This Item:

File	Size	Format
	0Kb	Unknown	256	View/Open