{"id":12681,"date":"2021-11-15T18:45:43","date_gmt":"2021-11-15T23:45:43","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12681"},"modified":"2026-06-02T14:59:26","modified_gmt":"2026-06-02T18:59:26","slug":"tr-138-on-generating-random-permutations-with-arbitrary-distributions","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1988\/tr-138-on-generating-random-permutations-with-arbitrary-distributions\/","title":{"rendered":"TR-138: On Generating Random Permutations with Arbitrary Distributions"},"content":{"rendered":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-138: On Generating Random Permutations with Arbitrary Distributions\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n<p>Carleton University<br>\n<a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1988\/\">Technical Report<\/a> <strong>TR-138<\/strong><br>\nJune 1988<\/p>\n\n\n\n<h2 id=\"on-generating-random-permutations-with-arbitrary-distributions\" class=\"wp-block-heading tr_t1\">On Generating Random Permutations with Arbitrary Distributions<\/h2>\n\n\n\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">B. J. Oommen &amp; D.T.H. Ng<\/div>\n<\/div>\n<\/div>\n\n\n\n<div>\n<h3>Abstract<\/h3>\n<p>Let  = {R1 ,R2, .. ,,RM} be an ordered set of M elements where Ri &lt; Rj whenever i &lt; j. Let 7t be the set of permutations of 1. We consider the problem of randomly generating the elements of 7t according to a distribution G(7t). Various algorithms including those due to Durstenfeld [D2, K1] and Moses et al [M1] are available for the case when the distribution G(7t) is a uniform distribution (i.e., where all the elements of 7t are generated with equal probability). In this paper we consider the case when the distribution G(7t) is not necessarily uniform. We present a strategy for specifying the distribution G(7t) and propose a technique for generating the elements of the 7t according to the distribution G(7t). Applications of the technique to generate &#8220;almost sorted lists&#8221; and in the Travelling Salesman Problem have been presented. Finally, simulation results have been included which demonstrate the power of the Random Permutation Generation (RPG) technique.<\/p>\n<\/div>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/tr-138.pdf\">TR-138.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-138 June 1988 On Generating Random Permutations with Arbitrary Distributions B. J. Oommen &amp; D.T.H. Ng Abstract Let = {R1 ,R2, .. ,,RM} be an ordered set of M elements where Ri &lt; Rj whenever i &lt; j. Let 7t be the set of permutations of 1. We consider the problem [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11829,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-12681","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12681","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=12681"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12681\/revisions"}],"predecessor-version":[{"id":12682,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12681\/revisions\/12682"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11829"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12681"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12681"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}