Tags:
This christmas was way different than the previous christmas. I moved from Brasil to Canada and for the first time I was away from my family, but with some very good friends.
Some of those friends play Bingo during x-mas night, instead of exchanging gifts and we played - my daughters loved! So, today out of nowhere, she came up with the idea of playing bingo. She built some bingo cards and she wanted me to play the numbers.
hum... We don't have balls, but we have a computer. So I decided to write a python script to shuffle the balls.
It should shuffle them, but with some interesting requirements.
We have a set of balls, from 1 to 75, and we need to shuffle them all. I have some choices
Terrible idea ! This will go crazy when my set gets close to the total number of balls.
Imagine - Please don't do it !
rnd_num = randint()
while rnd_num not in my_set:
rnd_num = randint()
As I said, terrible idea. Let's move to the next.
Let me introduce the worldwide famous Thinaso algorithm! (Thiago naive shuffling algorithm)
It looks much more interesting. Steps:
First, let's write the seeking function. It will find the closest available position.
It gets a number from the vector if position is valid
def get_single_number(nums, pos):
if pos >= 0 and pos < len(nums):
return nums[pos]
return 0
Now, let's write the method that gets the number from the vector
def get_number(nums, pos):
First we try to get the number in the provided position and if the value is not available (marked as 0), we go to the right and to the left.
pr = pos+1
pl = pos-1
while get_single_number(nums, pos) == 0:
pos = pr
pr += 1
if get_single_number(nums, pos) == 0:
pos = pl
pl -= 1
If when running to the right and left we found something, let's mark the position as used and return the value
n = nums[pos]
if n != 0:
nums[pos] = 0
return n
The complex part has gone already. Now we need to get all the balls in random order.
def shuffle_numbers(nums):
import random
random.seed()
ret = []
total = len(nums)
for i in range(0, total):
pos = random.randint(0, total-1)
n = get_number(nums, pos)
ret.append(n)
return ret
IMPORTANT !
Here if we have duplicated results from randint, as I am getting the closest positions, to each random I generate, I will have a different number from my sequenced vector and add the resulting number incrementally to my results.
Using is very simple.
print shuffle_numbers(range(1, 76)) #[)
There is something interesting is this algorithm. I can shuffle the numbers inside my set.
print shuffle_numbers([2, 4, 6, 8, 10, 12]) #custom list
print shuffle_numbers(range(1, 5) + range(6, 10)) #list without 5
...
I hope you enjoyed reading as much as I enjoyed writing this very famous algorithm !
Source code: sorting/thinaso.py
Any comments or questions, compliments ?
Reach me on twitter - @thiedri