关闭

关闭

关闭

封号提示

内容

首页 in-place shuffle

in-place shuffle.pdf

in-place shuffle

gougou
2011-10-10 0人阅读 0 0 0 暂无简介 举报

简介:本文档为《in-place shufflepdf》,可适用于IT/计算机领域

arXiv:vcsDSMayASimpleInPlaceAlgorithmforInShufflePeiyushJain,MicrosoftCorporationJulyIntroductionAninshuffleofadeckofcardsisdonebycuttingthedeckintotwoequalhalvesandinterleavingthemperfectly,withthefirstcardofthesecondhalfbeingthefirstcardoftheshuffleddeckIncaseofncards,thiskindofashufflegivesrisetoapermutation(calledtheinshufflepermutationofordern)givenby:i→imod(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,thengisaprimitiverootofpkforanyk≥AproofofthistheoremcanbefoundinNar,pItcanbeeasilyseenthatisaprimitiverootofFromtheabovetheoremitfollowsthatisalsoaprimitiverootofkforanyk≥Thisimpliesthatthegroup(Zk)∗iscyclicwithbeingitsgeneratorNowletusanalysethecyclesofaninshufflepermutationwhenn=k−Thecyclecontainingisnothingbutthegroup(Zk)∗,whichconsistsofallnumbersrelativelyprimetokandlessthanitLet≤s<kConsiderthecyclecontainingsEverynumberinthiscycleisoftheformst(modulok)for≤t≤ϕ(k)(whereϕistheEulertotientfunction)Sinceisageneratorof(Zk)∗,thiscyclecontainsexactlythenumberslessthankwhicharedivisiblebysbutnotbyanyhigherpowerofThismeansthatinaninshufflepermutationoforderk−,wehaveexactlykcycleswith,,,,k−eachbelongingtoadifferentcycleThusforthesepermutations,itbecomeseasytopickthe’next’cycleinordertoapplythecycleleaderalgorithmNotethatthelengthofthecyclecontainingsisϕ(k)s,whichhelpsusimplementthecycleleaderalgorithmmoreefficientlyWepresentthealgorithmforthegeneralcaseofaninshufflepermutationoforderninthenextsectionAlgorithmWestartwithanobservationSupposeforeachnwecaneasilyfindam(=Ω(n)and≤n)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=k−suchthatk≤n<kStepDoarightcyclicshiftofAm,,nmbyadistancemStepForeachi∈{,,,k−},startingati,dothecycleleaderalgorithmfortheinshufflepermutationofordermStepRecursivelydotheinshufflealgorithmonAm,,nSpaceandTimeComplexityLetT(n)bethetimetakenonaninputarrayofsizenLetuslookatthetimeandspaceboundsforeachofthestepsStepcanbedoneinplaceinO(logn)timeStepcanbedoneinplaceinO(n)timeStepcanbedoneinplaceinO(m)timeStepisatailrecursivecallandhencecanbeimplementedinconstantspaceThetimetakenbythiscallisT((n−m))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)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/3

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部

举报
资料