{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T11:52:25Z","timestamp":1759665145929,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,8,13]],"date-time":"2020-08-13T00:00:00Z","timestamp":1597276800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,8,13]],"date-time":"2020-08-13T00:00:00Z","timestamp":1597276800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e1 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["2017\/22166-9"],"award-info":[{"award-number":["2017\/22166-9"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comp. Appl. Math."],"published-print":{"date-parts":[[2020,9]]},"DOI":"10.1007\/s40314-020-01295-4","type":"journal-article","created":{"date-parts":[[2020,8,13]],"date-time":"2020-08-13T15:49:59Z","timestamp":1597333799000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient generation of random derangements with the expected distribution of cycle lengths"],"prefix":"10.1007","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5516-0568","authenticated-orcid":false,"given":"J. Ricardo G.","family":"Mendon\u00e7a","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,8,13]]},"reference":[{"issue":"1","key":"1295_CR1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01933579","volume":"20","author":"SG Akl","year":"1989","unstructured":"Akl SG (1989) A new algorithm for generating derangements. BIT Numer Math 20(1):2\u20137","journal-title":"BIT Numer Math"},{"issue":"5","key":"1295_CR2","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1080\/00029890.1986.11971821","volume":"93","author":"D Aldous","year":"1986","unstructured":"Aldous D, Diaconis P (1986) Shuffling cards and stopping times. Am Math Mon 93(5):333\u2013348","journal-title":"Am Math Mon"},{"key":"1295_CR3","doi-asserted-by":"crossref","DOI":"10.4171\/000","volume-title":"Logarithmic combinatorial structures: a probabilistic approach","author":"R Arratia","year":"2003","unstructured":"Arratia R, Barbour AD, Tavar\u00e9 S (2003) Logarithmic combinatorial structures: a probabilistic approach. EMS, Z\u00fcrich"},{"issue":"2","key":"1295_CR4","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/3009909","volume":"13","author":"A Bacher","year":"2017","unstructured":"Bacher A, Bodini O, Hwang H-K, Tsai T-H (2017) Generating random permutations by coin tossing: classical algorithms, new analysis, and modern implementation. ACM Trans Algorithms 13(2):24","journal-title":"ACM Trans Algorithms"},{"issue":"1\u20133","key":"1295_CR5","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/j.dam.2003.06.002","volume":"140","author":"JL Baril","year":"2004","unstructured":"Baril JL, Vajnovszki V (2004) Gray code for derangements. Discret Appl Math 140(1\u20133):207\u2013221","journal-title":"Discret Appl Math"},{"issue":"1","key":"1295_CR6","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1006\/jcph.1998.6149","volume":"149","author":"I Beichl","year":"1999","unstructured":"Beichl I, Sullivan F (1999) Approximating the permanent via importance sampling with application to the dimer covering problem. J Comput Phys 149(1):128\u2013147","journal-title":"J Comput Phys"},{"key":"1295_CR7","unstructured":"Blumberg O (2012) Cutoff for the transposition walk on permutations with one-sided restrictions. arXiv:1202.4797 [math.PR]"},{"key":"1295_CR8","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781107325708","volume-title":"Combinatorial matrix theory","author":"RA Brualdi","year":"1991","unstructured":"Brualdi RA, Ryser RJ (1991) Combinatorial matrix theory. Cambridge University Press, Cambridge"},{"key":"1295_CR9","volume-title":"Enumerative combinatorics","author":"CA Charalambides","year":"2002","unstructured":"Charalambides CA (2002) Enumerative combinatorics. Chapman & Hall\/CRC, Boca Raton"},{"issue":"469","key":"1295_CR10","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1198\/016214504000001303","volume":"100","author":"Y Chen","year":"2005","unstructured":"Chen Y, Diaconis P, Holmes SP, Liu JS (2005) Sequential Monte Carlo methods for statistical analysis of tables. J Am Stat Assoc 100(469):109\u2013120","journal-title":"J Am Stat Assoc"},{"key":"1295_CR11","doi-asserted-by":"publisher","unstructured":"Chung F, Diaconis P, Graham R (2019) Permanental generating functions and sequential importance sampling. Adv Appl Math. https:\/\/doi.org\/10.1016\/j.aam.2019.05.004(in press)","DOI":"10.1016\/j.aam.2019.05.004"},{"key":"1295_CR12","doi-asserted-by":"crossref","DOI":"10.1214\/lnms\/1215467407","volume-title":"Group representations in probability and statistics","author":"P Diaconis","year":"1988","unstructured":"Diaconis P (1988) Group representations in probability and statistics. IMS, Hayward"},{"issue":"25","key":"1295_CR13","doi-asserted-by":"crossref","first-page":"14600","DOI":"10.1073\/pnas.95.25.14600","volume":"95","author":"PW Diaconis","year":"1998","unstructured":"Diaconis PW, Holmes SP (1998) Matchings and phylogenetic trees. Proc Natl Acad Sci USA 95(25):14600\u201314602","journal-title":"Proc Natl Acad Sci USA"},{"key":"1295_CR14","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1214\/EJP.v7-105","volume":"7","author":"P Diaconis","year":"2002","unstructured":"Diaconis P, Holmes S (2002) Random walks on trees and matchings. Electron J Probab 7:6","journal-title":"Electron J Probab"},{"key":"1295_CR15","doi-asserted-by":"crossref","unstructured":"Diaconis P, Kolesnik B (2019) Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs. arXiv:1907.02333 [math.PR]","DOI":"10.1007\/978-3-662-59204-5_6"},{"issue":"2","key":"1295_CR16","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/BF00535487","volume":"57","author":"P Diaconis","year":"1981","unstructured":"Diaconis P, Shahshahani M (1981) Generating a random permutation by random transpositions. Z Wahrsch Verw Gebiete 57(2):159\u2013179","journal-title":"Z Wahrsch Verw Gebiete"},{"key":"1295_CR17","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1214\/lnms\/1215090070","volume-title":"State of the art in probability and statistics: Festschrift for Willem R. van Zwet","author":"P Diaconis","year":"2001","unstructured":"Diaconis P, Graham RL, Holmes SP (2001) Statistical problems involving permutations with restricted positions. In: de Gunst M, Klaassen C, Van der Vaart A (eds) State of the art in probability and statistics: Festschrift for Willem R. van Zwet. IMS, Beachwood, pp 195\u2013222"},{"issue":"3","key":"1295_CR18","doi-asserted-by":"crossref","first-page":"1146","DOI":"10.1137\/18M1172910","volume":"33","author":"M Dyer","year":"2019","unstructured":"Dyer M, M\u00fcller H (2019) Counting perfect matchings and the switch chain. SIAM J Discret Math 33(3):1146\u20131174","journal-title":"SIAM J Discret Math"},{"issue":"2","key":"1295_CR19","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1145\/2822322","volume":"64","author":"M Dyer","year":"2017","unstructured":"Dyer M, Jerrum M, M\u00fcller H (2017) On the switch Markov chain for perfect matchings. J ACM 64(2):12","journal-title":"J ACM"},{"issue":"2","key":"1295_CR20","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0097-3165(90)90056-3","volume":"53","author":"P Flajolet","year":"1990","unstructured":"Flajolet P, Soria M (1990) Gaussian limiting distributions for the number of components in combinatorial structures. J Comb Theor Ser A 53(2):165\u2013182","journal-title":"J Comb Theor Ser A"},{"issue":"3","key":"1295_CR21","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1007\/BF01941134","volume":"28","author":"D Gries","year":"1988","unstructured":"Gries D, Xue J (1988) Generating a random cyclic permutation. BIT Numer Math 28(3):569\u2013572","journal-title":"BIT Numer Math"},{"issue":"2","key":"1295_CR22","doi-asserted-by":"crossref","first-page":"26","DOI":"10.37236\/1284","volume":"3","author":"P Hanlon","year":"1996","unstructured":"Hanlon P (1996) A random walk on the rook placements on a Ferrer\u2019s board. Electron J Comb 3(2):26","journal-title":"Electron J Comb"},{"issue":"4","key":"1295_CR23","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/j.ipl.2004.02.006","volume":"90","author":"JF Korsh","year":"2004","unstructured":"Korsh JF, LaFollette PS (2004) Constant time generation of derangements. Inf Process Lett 90(4):181\u2013186","journal-title":"Inf Process Lett"},{"issue":"6","key":"1295_CR24","doi-asserted-by":"crossref","first-page":"749","DOI":"10.1007\/BF02366856","volume":"32","author":"NY Kuznetsov","year":"1996","unstructured":"Kuznetsov NY (1996) Computing the permanent by importance sampling method. Cybern Syst Anal 32(6):749\u2013755","journal-title":"Cybern Syst Anal"},{"key":"1295_CR25","volume-title":"Matching theory. Corrected reprint","author":"L Lov\u00e1sz","year":"2009","unstructured":"Lov\u00e1sz L, Plummer MD (2009) Matching theory. Corrected reprint. AMS, Providence"},{"key":"1295_CR26","doi-asserted-by":"crossref","unstructured":"Mart\u00ednez C, Panholzer A, Prodinger H (2008) Generating random derangements. In: Sedgewick R, Szpankowski W (eds) Proceedings of the fifth workshop on analytic algorithmics and combinatorics\u2014ANALCO. SIAM, Philadelphia, pp 234\u2013240","DOI":"10.1137\/1.9781611972986.7"},{"key":"1295_CR27","unstructured":"Ozel E (2017) The number of $$k$$-cycles in a family of restricted permutations. arXiv:1710.07885 [math.PR]"},{"issue":"2","key":"1295_CR28","first-page":"219","volume":"3","author":"A Panholzer","year":"2004","unstructured":"Panholzer A, Prodinger H, Riedel M (2004) Measuring post\u2013quickselect disorder. J Iran Stat Soc 3(2):219\u2013249","journal-title":"J Iran Stat Soc"},{"key":"1295_CR29","first-page":"75","volume":"65","author":"H Prodinger","year":"2002","unstructured":"Prodinger H (2002) On the analysis of an algorithm to generate a random cyclic permutation. Ars Comb 65:75\u201378","journal-title":"Ars Comb"},{"issue":"2","key":"1295_CR30","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1002\/rsa.3240050208","volume":"5","author":"LE Rasmussen","year":"1994","unstructured":"Rasmussen LE (1994) Approximating the permanent: a simple approach. Random Struct Algorithms 5(2):349\u2013361","journal-title":"Random Struct Algorithms"},{"issue":"6","key":"1295_CR31","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0020-0190(86)90073-6","volume":"22","author":"S Sattolo","year":"1986","unstructured":"Sattolo S (1986) An algorithm to generate a random cyclic permutation. Inf Process Lett 22(6):315\u2013317","journal-title":"Inf Process Lett"},{"issue":"2","key":"1295_CR32","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1145\/356689.356692","volume":"9","author":"R Sedgewick","year":"1977","unstructured":"Sedgewick R (1977) Permutation generation methods. Comput Surv 9(2):137\u2013164","journal-title":"Comput Surv"},{"issue":"4","key":"1295_CR33","doi-asserted-by":"crossref","first-page":"1406","DOI":"10.1007\/s10959-014-0559-7","volume":"28","author":"A Smith","year":"2015","unstructured":"Smith A (2015) Comparison theory for Markov chains on different state spaces and application to random walk on derangements. J Theor Probab 28(4):1406\u20131430","journal-title":"J Theor Probab"},{"key":"1295_CR34","unstructured":"Vigna S (2019) xoshiro\/xoroshiro generators and the PRNG shootout. http:\/\/xoshiro.di.unimi.it\/. Accessed 15 Dec 2019"},{"issue":"4","key":"1295_CR35","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1007\/s00026-009-0003-3","volume":"12","author":"MC Wilson","year":"2009","unstructured":"Wilson MC (2009) Random and exhaustive generation of permutations and cycles. Ann Comb 12(4):509\u2013520","journal-title":"Ann Comb"},{"key":"1295_CR36","unstructured":"Wolfram Research, Inc. (2018) Mathematica, Version 11.3. Champaign"}],"container-title":["Computational and Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40314-020-01295-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s40314-020-01295-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40314-020-01295-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,5]],"date-time":"2023-10-05T18:46:56Z","timestamp":1696531616000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s40314-020-01295-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,13]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["1295"],"URL":"https:\/\/doi.org\/10.1007\/s40314-020-01295-4","relation":{},"ISSN":["2238-3603","1807-0302"],"issn-type":[{"type":"print","value":"2238-3603"},{"type":"electronic","value":"1807-0302"}],"subject":[],"published":{"date-parts":[[2020,8,13]]},"assertion":[{"value":"5 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 January 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 August 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 August 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"244"}}