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). |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论