关闭

关闭

关闭

封号提示

内容

首页 in-place shuffle.pdf

in-place shuffle.pdf

in-place shuffle.pdf

上传者: gougou 2011-10-10 评分 0 0 0 0 0 0 暂无简介 简介 举报

简介:本文档为《in-place shufflepdf》,可适用于IT/计算机领域,主题内容包含arXiv:vcsDSMayASimpleInPlaceAlgorithmforInShufflePeiyushJain,MicrosoftCorpor符等。

arXiv:vcsDSMayASimpleInPlaceAlgorithmforInShufflePeiyushJain,MicrosoftCorporationJulyIntroductionAninshuffleofadeckofcardsisdonebycuttingthedeckintotwoequalhalvesandinterleavingthemperfectly,withthefirstcardofthesecondhalfbeingthefirstcardoftheshuffleddeckIncaseofncards,thiskindofashufflegivesrisetoapermutation(calledtheinshufflepermutationofordern)givenby:iimod(n),i{,,,n}InEMithasbeenshownthattheproblemofmerginglistsinplacecanbereducedtoperforminginshufflesinplaceInthesamepaper,theauthorsprovidealineartime,inplacealgorithmforperformingtheinshuffle,whenthelistisrepresentedasanarray,indexedtonInthispaperweprovideasimpleralgorithmwhichpermitsaneasyimplementationPreliminariesAnypermutationisasetofdisjointcyclesForegtheinshuffleofelementsiscomposedoftwocycles:(,,)and(,,)Itiseasytomovetheelementsofasinglecycleusingjustanextralocation,bya“cycleleader”algorithm,FMPThisalgorithmproceedsbyrepeatedlymakingaspaceinthelist,computingtheindexofelementthatbelongstothatspaceandmovingthatelement,socreatinganewspaceForanypermutation,wecanproceedbyapplyingthecycleleaderalgorithmtoeachcycleinturninordertorealisethewholepermutationIf,forapermutation,wecancomputethelocationofanelementofthe’next’cycleinconstanttimeandminimalspace,wecouldrealisethewholepermutationusingalineartimeandaninplacealgorithmWeshowthat,whennisoftheformk,wecaneasilydeterminethecyclesoftheinshufflepermutationofordernWewillneedthefollowingtheoremfromnumbertheory:TheoremIfpisanoddprimeandgisaprimitiverootofp,thengisaprimitiverootofpkforanykAproofofthistheoremcanbefoundinNar,pItcanbeeasilyseenthatisaprimitiverootofFromtheabovetheoremitfollowsthatisalsoaprimitiverootofkforanykThisimpliesthatthegroup(Zk)iscyclicwithbeingitsgeneratorNowletusanalysethecyclesofaninshufflepermutationwhenn=kThecyclecontainingisnothingbutthegroup(Zk),whichconsistsofallnumbersrelativelyprimetokandlessthanitLets<kConsiderthecyclecontainingsEverynumberinthiscycleisoftheformst(modulok)fortϕ(k)(whereϕistheEulertotientfunction)Sinceisageneratorof(Zk),thiscyclecontainsexactlythenumberslessthankwhicharedivisiblebysbutnotbyanyhigherpowerofThismeansthatinaninshufflepermutationoforderk,wehaveexactlykcycleswith,,,,keachbelongingtoadifferentcycleThusforthesepermutations,itbecomeseasytopickthe’next’cycleinordertoapplythecycleleaderalgorithmNotethatthelengthofthecyclecontainingsisϕ(k)s,whichhelpsusimplementthecycleleaderalgorithmmoreefficientlyWepresentthealgorithmforthegeneralcaseofaninshufflepermutationoforderninthenextsectionAlgorithmWestartwithanobservationSupposeforeachnwecaneasilyfindam(=Ω(n)andn)forwhichwehavealineartime,inplace,inshufflealgorithm,wethenhavealineartime,inplace,inshufflealgorithmfornThisisbecausewecanshufflethearraya,a,,am,am,,an,an,,anm,anm,,antolooklikea,a,,am,an,,anm,am,an,anm,aninlineartimeandinplacebydoingarightcyclicshiftoftheelementsam,,anmbyadistancemWecanachievethisbyreversingthesubarraym,,nmfollowedbyareversalofthesubarraysm,,nandn,,nmWecannowperformaninshuffleofthefirstmelementsandrecursivelyperformaninshuffleoftheremainingelementsThuswehavethefollowingInshuffleAlgorithm:Input:AnarrayA,,nStepFindam=ksuchthatkn<kStepDoarightcyclicshiftofAm,,nmbyadistancemStepForeachi{,,,k},startingati,dothecycleleaderalgorithmfortheinshufflepermutationofordermStepRecursivelydotheinshufflealgorithmonAm,,nSpaceandTimeComplexityLetT(n)bethetimetakenonaninputarrayofsizenLetuslookatthetimeandspaceboundsforeachofthestepsStepcanbedoneinplaceinO(logn)timeStepcanbedoneinplaceinO(n)timeStepcanbedoneinplaceinO(m)timeStepisatailrecursivecallandhencecanbeimplementedinconstantspaceThetimetakenbythiscallisT((nm))Sincem=Ω(n),itfollowsthatthetotaltimetakenbythisalgorithmisO(n)Thuswehavealineartime,inplacealgorithmfortheinshuffleofalistofnelementsConclusionWehavedescribedalineartime,inplace,inshufflealgorithmwhichIbelieveisinteresting,simpleandeasytoimplementItisnotobviouswhethertheapproachused(usingapsuchthatkisaprimitiverootofp)inthispapercanbegeneralisedforkwayshuffles,butitisprobablethatwecanusethisapproachforfixedsquarefreek,HEAForsmallk,thisapproachcandefinitelybeusedAcknowledgementIwouldliketothankBarukhZivforsuggestingthatIwriteupthispaperIwouldalsoliketothankKarthikMaheshforpointingthisproblemtomeandAnandGaneshfortheinterestingdiscussionswehadReferencesEMJEllisandMMarkovInsitu,stablemergingbywayofperfectshuffleTheComputerJournal():,()FMPFaithEFich,JIanMunro,andPatricioVPobletePermutinginplaceSIAMJournalonComputing,():,HEADRHeathBrownArtin’sconjectureforprimitiverootsQuartJMathOxfordSer()(),no,NarWNarkiewiczTheDevelopmentofPrimeNumberTheory:FromEuclidtoHardyandLittlewoodSpringerMonographsinMathematics,NewYorkIntroductionPreliminariesAlgorithmSpaceandTimeComplexityConclusion

用户评论(0)

0/200

精彩专题

上传我的资料

每篇奖励 +2积分

资料评价:

/3
0下载券 下载 加入VIP, 送下载券

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部