diff options
author | William Carroll <wpcarro@gmail.com> | 2020-01-29T14·29+0000 |
---|---|---|
committer | William Carroll <wpcarro@gmail.com> | 2020-01-29T14·29+0000 |
commit | fb9380ba268b3cd27372acadb87b14cc96163374 (patch) | |
tree | f65d7fc8d8726499165a0949af39afd1abc8118c /universe/data_structures_and_algorithms/shuffle.py | |
parent | 15110e6de9f85537c7847267caa35fa068aea001 (diff) | |
parent | 8ad51b24dd8719840aac47134835ea25cfe1b0b8 (diff) |
Add 'universe/' from commit '8ad51b24dd8719840aac47134835ea25cfe1b0b8'
git-subtree-dir: universe git-subtree-mainline: 15110e6de9f85537c7847267caa35fa068aea001 git-subtree-split: 8ad51b24dd8719840aac47134835ea25cfe1b0b8
Diffstat (limited to 'universe/data_structures_and_algorithms/shuffle.py')
-rw-r--r-- | universe/data_structures_and_algorithms/shuffle.py | 34 |
1 files changed, 34 insertions, 0 deletions
diff --git a/universe/data_structures_and_algorithms/shuffle.py b/universe/data_structures_and_algorithms/shuffle.py new file mode 100644 index 000000000000..bdfbad24263c --- /dev/null +++ b/universe/data_structures_and_algorithms/shuffle.py @@ -0,0 +1,34 @@ +import random + + +def get_random(floor, ceiling): + return random.randrange(floor, ceiling + 1) + + +# shuffle_in_place :: [a] -> IO () +def shuffle_in_place(xs): + """Fisher-Yates algorithm. Notice that shuffling here is the same as + selecting a random permutation of the input set, `xs`.""" + n = len(xs) - 1 + for i in range(len(xs)): + r = get_random(i, n) + xs[i], xs[r] = xs[r], xs[i] + return xs + + +# shuffle :: [a] -> [a] +def shuffle_not_in_place(xs): + result = [] + + while xs: + i = get_random(0, len(xs) - 1) + x = xs.pop(i) + result.append(x) + + return result + + +xs = [x for x in range(9)] +print(xs) +# print(shuffle_not_in_place(xs)) +print(shuffle_in_place(xs[:])) |