{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T20:15:09Z","timestamp":1769976909522,"version":"3.49.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,2,7]],"date-time":"2017-02-07T00:00:00Z","timestamp":1486425600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"name":"ANR-MOST Joint Project MetAConC","award":["ANR 2015-BLAN-0204 and MOST 105-2923-E-001-001-MY4"],"award-info":[{"award-number":["ANR 2015-BLAN-0204 and MOST 105-2923-E-001-001-MY4"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,4,30]]},"abstract":"<jats:p>Several simple, classical, little-known algorithms in the statistics and computer science literature for generating random permutations by coin tossing are examined, analyzed, and implemented. These algorithms are either asymptotically optimal or close to being so in terms of the expected number of times the random bits are generated. In addition to asymptotic approximations to the expected complexity, we also clarify the corresponding variances, as well as the asymptotic distributions. A brief comparative discussion with numerical computations in a multicore system is also given.<\/jats:p>","DOI":"10.1145\/3009909","type":"journal-article","created":{"date-parts":[[2017,2,10]],"date-time":"2017-02-10T13:28:54Z","timestamp":1486733334000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Generating Random Permutations by Coin Tossing"],"prefix":"10.1145","volume":"13","author":[{"given":"Axel","family":"Bacher","sequence":"first","affiliation":[{"name":"LIPN, Universit\u00e9 Paris 13, Villetaneuse"}]},{"given":"Olivier","family":"Bodini","sequence":"additional","affiliation":[{"name":"LIPN, Universit\u00e9 Paris 13, Villetaneuse"}]},{"given":"Hsien-Kuei","family":"Hwang","sequence":"additional","affiliation":[{"name":"Academia Sinica, Taipei, Taiwan"}]},{"given":"Tsung-Hsi","family":"Tsai","sequence":"additional","affiliation":[{"name":"Academia Sinica, Taipei, Taiwan"}]}],"member":"320","published-online":{"date-parts":[[2017,2,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/97444.97674"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the International Symposium on Distributed Computing and Artificial Intelligence. Springer, 183--190","author":"Andr\u00e9s D. M."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"E. B. Barker and J. M. Kelsey. 2007. Recommendation for Random Number Generation using Deterministic Random Bit Generators (Revised). U.S. Department of Commerce Technology Administration National Institute of Standards and Technology Computer Security Division Information Technology Laboratory.  E. B. Barker and J. M. Kelsey. 2007. Recommendation for Random Number Generation using Deterministic Random Bit Generators (Revised). U.S. Department of Commerce Technology Administration National Institute of Standards and Technology Computer Security Division Information Technology Laboratory.","DOI":"10.6028\/NIST.SP.800-90"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"K. J. Berry J. E. Johnston and P. W. Mielke Jr. 2014. A Chronicle of Permutation Statistical Methods (1920--2000 and Beyond). Springer Berlin.  K. J. Berry J. E. Johnston and P. W. Mielke Jr. 2014. A Chronicle of Permutation Statistical Methods (1920--2000 and Beyond). Springer Berlin.","DOI":"10.1007\/978-3-319-02744-9"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90210-4"},{"key":"e_1_2_1_6_1","first-page":"7","article-title":"Generalized association plots: Information visualization via iteratively generated correlation matrices","volume":"12","author":"Chen C.-H.","year":"2002","journal-title":"Stat. Sin."},{"key":"e_1_2_1_7_1","volume-title":"Nonuniform Random Variate Generation","author":"Devroye L."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7908-2604-3_1"},{"key":"e_1_2_1_9_1","unstructured":"L. Devroye and C. Gravel. 2016. The expected bit complexity of the von Neumann rejection algorithm. Stat. Comput. (2016) 1--12.  L. Devroye and C. Gravel. 2016. The expected bit complexity of the von Neumann rejection algorithm. Stat. Comput. (2016) 1--12."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/364520.364540"},{"key":"e_1_2_1_11_1","unstructured":"A. Erd\u00e9lyi W. Magnus F. Oberhettinger and F. G. Tricomi. 1953. Higher Transcendental Functions. Vol. I. McGraw--Hill New York NY.  A. Erd\u00e9lyi W. Magnus F. Oberhettinger and F. G. Tricomi. 1953. Higher Transcendental Functions. Vol. I. McGraw--Hill New York NY."},{"key":"e_1_2_1_12_1","unstructured":"R. A. Fisher and F. Yates. 1948. Statistical Tables for Biological Agricultural and Medical Research. 3rd ed. Oliver 8 Boyd.  R. A. Fisher and F. Yates. 1948. Statistical Tables for Biological Agricultural and Medical Research. 3rd ed. Oliver 8 Boyd."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 9th Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithmics and Combinatorics. SIAM","author":"Flajolet P."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/204637.204638"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the Twenty-2nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201911)","author":"Flajolet P."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00002-E"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"P. Flajolet and R. Sedgewick. 2009. Analytic Combinatorics. Cambridge University Press New York NY USA.   P. Flajolet and R. Sedgewick. 2009. Analytic Combinatorics. Cambridge University Press New York NY USA.","DOI":"10.1017\/CBO9780511801655"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.01.024"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-004-0561-x"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 14th International Workshop on Fast Software Encryption (FSE\u201907)","author":"Granboulan L."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1981.1056363"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1048516530"},{"key":"e_1_2_1_24_1","first-page":"103","article-title":"Asymptotic variance of random symmetric digital search trees","volume":"12","author":"Hwang H.-K.","year":"2010","journal-title":"Discr. Math. Theor. Comput. Sci."},{"key":"e_1_2_1_25_1","volume-title":"Intel Digital Random Number Generator (DRNG): Software Implementation Guide"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00167-9"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1080\/00207168908803745"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","volume-title":"The Art of Computer Programming","author":"Knuth D. E.","DOI":"10.1145\/1283920.1283929"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","volume-title":"The Art of Computer Programming","author":"Knuth D. E.","DOI":"10.1145\/1283920.1283929"},{"key":"e_1_2_1_30_1","unstructured":"D. E. Knuth and A. C. Yao. 1976. The complexity of nonuniform random number generation. Algorithms and Complexity: New Directions and Recent Results. Academic Press New York 357--428.  D. E. Knuth and A. C. Yao. 1976. The complexity of nonuniform random number generation. Algorithms and Complexity: New Directions and Recent Results. Academic Press New York 357--428."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-014-1202-1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.378"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2669372"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1090\/psapm\/010\/0113289"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.2989\/QM.2008.31.4.2.606"},{"key":"e_1_2_1_36_1","volume-title":"Optimal discrete uniform generation from coin flips, and applications. CoRR abs\/1304.1916","author":"Lumbroso J.","year":"2013"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1239\/jap\/1059060904"},{"key":"e_1_2_1_38_1","volume-title":"Bootstrap and Monte Carlo Methods in Biology","author":"Manly B. F. J."},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","volume-title":"Collision-Resolution Algorithms and Random-Access Communications","author":"Massey J. L.","DOI":"10.1007\/978-3-7091-2900-5_4"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"L. E. Moses and R. V. Oakford. 1963. Tables of Random Permutations. Stanford University Press.  L. E. Moses and R. V. Oakford. 1963. Tables of Random Permutations. Stanford University Press.","DOI":"10.2307\/2282765"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.877833"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1075828056"},{"key":"e_1_2_1_43_1","volume-title":"Sums of Independent Random Variables","author":"Petrov V. V."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1968.tb00751.x"},{"key":"e_1_2_1_45_1","first-page":"45","article-title":"Complexity of tabular methods of simulating finite discrete distributions","volume":"7","author":"Pokhodze\u012d B. B.","year":"1985","journal-title":"Izv. Vyssh. Uchebn. Zaved. Mat."},{"key":"e_1_2_1_46_1","first-page":"75","article-title":"On the analysis of an algorithm to generate a random cyclic permutation","volume":"65","author":"Prodinger H.","year":"2002","journal-title":"Ars Combin."},{"key":"e_1_2_1_47_1","first-page":"305","article-title":"Generation of random permutation of given number of elements using random sampling numbers","volume":"23","author":"Rao C. R.","year":"1961","journal-title":"Sankhya A"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/1191546.1191729"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90222-H"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1080\/0161-119191865812"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/363269.363619"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1962.tb00474.x"},{"key":"e_1_2_1_53_1","volume-title":"The Theory of the Riemann Zeta-Function","author":"Titchmarsh E. C."},{"key":"e_1_2_1_54_1","first-page":"36","article-title":"Various techniques used in connection with random digits","volume":"12","author":"von Neumann J.","year":"1951","journal-title":"J. Res. Nat. Bur. Standards"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31464-3_30"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-009-0002-4"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-009-0003-3"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3009909","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3009909","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:34Z","timestamp":1750273534000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3009909"}},"subtitle":["Classical Algorithms, New Analysis, and Modern Implementation"],"short-title":[],"issued":{"date-parts":[[2017,2,7]]},"references-count":56,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,4,30]]}},"alternative-id":["10.1145\/3009909"],"URL":"https:\/\/doi.org\/10.1145\/3009909","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,2,7]]},"assertion":[{"value":"2016-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-02-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}