{"id":1626,"date":"2021-07-20T22:18:14","date_gmt":"2021-07-21T05:18:14","guid":{"rendered":"http:\/\/66.94.114.210\/?p=1626"},"modified":"2021-07-20T22:24:07","modified_gmt":"2021-07-21T05:24:07","slug":"fisher-yates-shuffle","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2021\/07\/20\/fisher-yates-shuffle\/","title":{"rendered":"Fisher\u2013Yates Shuffle"},"content":{"rendered":"\n

Generating a random permutation of a finite sequence.<\/p>\n\n\n\n

O(n^2) <\/h2>\n\n\n\n

The basic method given for generating a random permutation of the numbers 1 through N<\/em> goes as follows:<\/p>\n\n\n\n

  1. Write down the numbers from 1 through\u00a0N<\/em>.<\/li>
  2. Pick a random number\u00a0k<\/em>\u00a0between one and the number of unstruck numbers remaining (inclusive).<\/li>
  3. Counting from the low end, strike out the\u00a0k<\/em>th number not yet struck out, and write it down at the end of a separate list.<\/li>
  4. Repeat from step 2 until all the numbers have been struck out.<\/li>
  5. The sequence of numbers written down in step 3 is now a random permutation of the original numbers.<\/li><\/ol>\n\n\n\n

    It is obvious that at each step, a number has equal possibility to be picked out. <\/p>\n\n\n\n

    Or we can consider it in the other way: at each step the number we will pick will have sizeof(remaining_list)<\/code> possibilities. So overall we will have n!<\/code> possibilities.<\/p>\n\n\n\n

    O(n)<\/h2>\n\n\n\n
    -- To shuffle an array a<\/em> of n<\/em> elements (indices 0..n<\/em>-1):
    for<\/strong> i<\/em> from<\/strong> 0 to<\/strong> n<\/em>\u22122 do<\/strong>
         j<\/em> \u2190 random integer such that i<\/em> \u2264 j<\/em> < n<\/em>
         exchange a<\/em>[i<\/em>] and a<\/em>[j<\/em>]<\/pre>\n\n\n\n
    vector<int> shuffle(vector<int> const& origin) {\n  vector<int> res = origin;\n  for (int i = 0; i + 1 < res.size(); ++i) {\n    int j = i + rand() % (res.size() - i);\n    swap(res[i], res[j]);\n  }\n  return res;\n}<\/code><\/pre>\n\n\n\n
    The correctness is also obvious. We basically use the original array as the separate list.<\/p>\n","protected":false},"excerpt":{"rendered":"
    Generating a random permutation of a finite sequence. O(n^2) The basic method given for generating a random permutation of the numbers 1 through N goes as follows: Write down the numbers from 1 through\u00a0N. Pick a random number\u00a0k\u00a0between one and the number of unstruck numbers remaining (inclusive). Counting from the low end, strike out the\u00a0kth number not…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,68],"tags":[],"class_list":["post-1626","post","type-post","status-publish","format-standard","hentry","category-alg","category-random"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1626","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=1626"}],"version-history":[{"count":3,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1626\/revisions"}],"predecessor-version":[{"id":1630,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1626\/revisions\/1630"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1626"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1626"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1626"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}