In-place permuting and perfect shuffling using involutions

doi:10.1016/j.ipl.2013.02.017

CORC > 北京大学 > 信息科学技术学院

	In-place permuting and perfect shuffling using involutions
	Yang, Qingxuan ; Ellis, John ; Mamakani, Khalegh ; Ruskey, Frank
刊名	information processing letters
	2013
关键词	Algorithms Analysis of algorithms Combinatorial problems Parallel algorithms Perfect shuffle Permutation Involution PERMUTATION CYCLES
DOI	10.1016/j.ipl.2013.02.017
英文摘要	Every permutation of {1, 2, ... , N} can be written as the product of two involutions. As a consequence, any permutation of the elements of an array can be performed in-place using simultaneous swaps in two rounds of swaps. In the case where the permutation is the k-way perfect shuffle, we develop two methods for efficiently computing the pair of involutions that accomplishes these swaps. The first method works whenever N is a power of k; in this case the time is O(N) and space O (log(2) N). The second method applies to the general case where N is a multiple of k; here the time is O (N log N) and the space is O (log(2) N). If k = 2 the space usage of the first method can be reduced to O (log N) on a machine that has a SADD (population count) instruction. (C) 2013 Elsevier B.V. All rights reserved.; http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000318192000007&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=8e1609b174ce4e31116a60747a720701 ; Computer Science, Information Systems; SCI(E); EI; 1; ARTICLE; 10-11; 386-391; 113
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/152314]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Yang, Qingxuan,Ellis, John,Mamakani, Khalegh,et al. In-place permuting and perfect shuffling using involutions[J]. information processing letters,2013.
APA	Yang, Qingxuan,Ellis, John,Mamakani, Khalegh,&Ruskey, Frank.(2013).In-place permuting and perfect shuffling using involutions.information processing letters.
MLA	Yang, Qingxuan,et al."In-place permuting and perfect shuffling using involutions".information processing letters (2013).