Implementing Roulette Wheel in Python

Fitness Proportionate Selection is a common method in Evolutionary Algorithms, which is also known to us as Roulette Wheel Selection in Evolutionary Algorithms[1] such as Genetic Algorithms.

The basic idea here is to get a random value out of a sample based on a pre-defined bias.

Following is the python implementation (using numpy library) of the Roulette Wheel selection. The wheel_vector should be provided in the following format [….value, bias…..], values can be added as much as required. Bias value is relative, higher the bias value higher the change of getting selected the corresponding value.

For an example, if it is required to declare the wheel vector for a bias dice where no. 6 is more likely to be appeared than other values, it should be defined as follow: note that value 6 is prone to be appeared 5 times more than any other value.

wheel_vector = np.array([1,1,2,1,3,1,4,1,5,1,6,5])

“all Python codes in this article are released under Creative Commons — Public Domain

#!/usr/bin/python

import numpy as np
import random as rand

roulette_wheel = np.array((0))
slot_count = 0

def init_roul_wheel(value_array):

	slot_count = 0
	i=0
	arrsize = value_array.size
	while i < arrsize/2:
		slot_count = slot_count + value_array[2*i+1]
		i = i + 1
	roulette_wheel = np.zeros((slot_count),dtype=np.int)
	#print(roulette_wheel)
	i = 0

	while i < arrsize/2:
		rv = value_array[2*i]
		bv = value_array[2*i+1]
		j = 0
		while j<span 				data-mce-type="bookmark" 				id="mce_SELREST_start" 				data-mce-style="overflow:hidden;line-height:0" 				style="overflow:hidden;line-height:0" 			></span><span 				data-mce-type="bookmark" 				id="mce_SELREST_start" 				data-mce-style="overflow:hidden;line-height:0" 				style="overflow:hidden;line-height:0" 			></span><span 				data-mce-type="bookmark" 				id="mce_SELREST_start" 				data-mce-style="overflow:hidden;line-height:0" 				style="overflow:hidden;line-height:0" 			></span><bv:
			t = rand.randint(0,slot_count-1)
			wheel_alloc = roulette_wheel[t]
			if wheel_alloc == 0:
				roulette_wheel[t] = rv
				j = j + 1
		i = i + 1
	return (roulette_wheel)

def spin(rw):
	slot_count = rw.size
	randno = rand.randint(0,10000)
	rot_degree = randno%360
	rot_unit = 360/slot_count
	rol_no = (rot_degree - (rot_degree%(rot_unit)))/rot_unit
	rol_value = rw[int(rol_no)]
	return rol_value	

wheel_vector = np.array([10,1,20,2,30,2,40,4,50,5,60,4,70,3,80,2,90,2])
x = init_roul_wheel(wheel_vector)
print (spin(x))

Check how the above code works (online python demo)

The above code is quite lengthy as I purposely omitted shortcuts to slice the arrays hoping that it improves the readability of the code.

The next step is to check if the function is really bias. In order to check that the code has been altered as follow. This version iterates the wheel 1,000,000 times and check the results.

#!/usr/bin/python

import numpy as np
import random as rand

roulette_wheel = np.array((0))
slot_count = 0

def init_roul_wheel(value_array):

	slot_count = 0
	i=0
	arrsize = value_array.size
	while i < arrsize/2:
		slot_count = slot_count + value_array[2*i+1]
		i = i + 1
	roulette_wheel = np.zeros((slot_count),dtype=np.int)
	#print(roulette_wheel)
	i = 0

	while i < arrsize/2:
		rv = value_array[2*i]
		bv = value_array[2*i+1]
		j = 0
		while j<bv:
			t = rand.randint(0,slot_count-1)
			wheel_alloc = roulette_wheel[t]
			if wheel_alloc == 0:
				roulette_wheel[t] = rv
				j = j + 1
		i = i + 1
	return (roulette_wheel)

def spin(rw):
	slot_count = rw.size
	randno = rand.randint(0,10000)
	rot_degree = randno%360
	rot_unit = 360/slot_count
	rol_no = (rot_degree - (rot_degree%(rot_unit)))/rot_unit
	rol_value = rw[int(rol_no)]
	return rol_value	

wheel_vector = np.array([10,1,20,2,30,2,40,4,50,5,60,4,70,3,80,2,90,2])
x = init_roul_wheel(wheel_vector)
#print (spin(x))

cal_rounds = 1000000

results = np.zeros((cal_rounds),dtype=np.int);

i =0 

while i<cal_rounds:
	value = spin(x)
	results[i] = value
	i = i +1

unique, counts = np.unique(results, return_counts=True)
print ("RW Vector", wheel_vector, "\n")
print ("Roulette Wheel", x)
print ("Results: ",unique,"\n\t" ,counts)

i = 0
while i<counts.size:
	#print (unique[i], "occured " + str(counts[i]))
	precentage = (counts[i]*100)/np.sum(counts)
	print (unique[i]," precentage - ",str(precentage) + ' %','('+str(round(precentage))+')')
	i = i +1

rws_output

Check the output of the code above, it shows number of times the values has been selected and the values have been selected based on the bias (check the percentages). Therefore it can be concluded that the function is working as expected.

References

[1] Lipowskia, Adam and Lipowskab, Dorota Roulette-wheel selection via stochastic acceptance – http://www.sciencedirect.com/science/article/pii/S0378437111009010


CC0

To the extent possible under law,
this article, the author

has waived all copyright and related or neighboring rights to “Implementing Roulette Wheel in Python”.

Advertisements

Mixology: Tamarind vodka cocktail

Tamarind is an acidic fruit. The sourness of the fruit is so great and strong which adds an extra uniqueness.  So I though of trying out a cocktail mixture out of Tamarind. This is how it went.

How to prepare Tamarind concentrate

This is not a difficult task, just get the fruit, peel the outer crust off. Then soak it in water, extract it by hand (use less water to make it more concentrated). Use a porous cloth to strain the juice.  Now you have tamarind concentrate.

Conceptual Design

Awakening the sourness, the acidity of the tamarind juice is my main intention here. However not everyone can bear it, the solution is adding sugar which is not my way. So I thought of softening the sourness with milk. Therefore I added milk instead of sugar. I took White Russian as the inspiration here. So I have two varieties now. Lets try it !

Preparation

Ingredients : 

  • Tamarind concentrate
  • Vodka (used Smirnoff)
  • Whipping Cream/ Milk
  • Sugar cyrup
  • Lime juice
  • Pepper

How to:

For the drink no.1, add 1:1 tamarind concentrate and vodka. Add sugar syrup if you prefer. Fill the shaker with ice and shake well. Strain it and add some lime juice and little bit of Pepper and mix it well. Finally add little Pepper on top of the surface. Serve.

For the next drink, The drink no.2, fill the glass with ice cubes. Then add cream and then Tamarind juice on top of it. You may add little bit of milk to get the cloudiness (however this is hard to notice). Stir a bit before serving. I prefer this with no sugar as milk soften the sourness to a manageable limit. But for sugar fans add it to the concentrate and make it ready. Do not add sugar when mixing.

Garnish

Salt rim glass would be more suitable. Again sugar for sugar fans.

Drink No. 1 – Tamarind Concentrate and Vodka

 

Drink No. 2 – Tamarind Concentrate, Cream/ Milk and Vodka

Aromatic

Fumes of both drinks are rich in sourness of tamarind. Adding some pepper on top of the first drink boosts the vibrant levels. Do not forget to inhale the aroma with care when pepper presents on the surface.

Taste

The sourness of tamarind is dominant here. The vodka gets much more soften in presence of tamarind. If you want it to be much stronger consider increasing the vodka portion or add equal amounts of tequila (just a suggestion). If  it is unpleasant due to high acidity level consider adding some salt to the tamarind concentrate.

Fitness

Does not matter the time of the date, the drink no. 1 is indeed a good starting point. Suits well for open-air, under-the-sun events ex: pool party, beach party etc. In summary, if you are looking for a punch or getting ready to start the evening, this would be one of the best choices.

Improvements

Instead of vodka, try this with tequila base. Or a base like in Long Island which is tequila, vodka, run, gin and triple Sec.

Try it and add your comments…

Non-Standard rounding function in Python

This post is about a trivial operation which is rounding. Recently I came across a situation where I need to perform a non standard integer rounding. As we know the standard functions available would round the valie to the nearest 10 or its multiplications. My requirement was rounding to the nearest 5.

So I came across the following solution and I immediately fall in love with this little python snippet and thought of sharing.

Here is goes.

#!/usr/bin/python

def floor(value, divisor):
    ans = value%divisor
    return value-ans

def ceiling(value, divisor):
    ans = value%divisor
    return value+divisor-ans

a = 105

x = ceiling(a,5)
y = floor(a,5)

print(x)
print(y)

The ceiling ( ) function round the value to the nearest upper value which is a multiplication of 5. The floor ( ) function would round the value to the nearest lower value which is a multiplication of 5.


Symmetric-Key Encryption using openSSL

I wrote few blog posts on Asymmetric Key encryption using PHPSecLib library recently and this blog post is on Symmetric-Key Encryption and I ll be using PHP openSSL extension for the implementation. OpenSSL is a open source library which implements SSL and other major cryptographic functions. It is extensively used in Linux, Windows and other operating systems. Luckily PHP got an extension, so we can straightaway use it.

Instead of PHPSecLib, openSSL can be used to implement RSA cryptography functions in PHP as well.

The major drawback in Symmetric-Key Encryption is the usage of the same key to encrypt and decrypt data. However unlike in Asymmetric-Key encryption (I would say RSA hereafter) there is no limit on the data size that can be encrypted and it is relatively faster than RSA. As a result RSA is used to exchange Symmetric Keys securely and then the client and the server continues to communicate based on symmetric-key encryption. Not only for communication but also we can use symmetric key encryption in data storage too. For an example before storing data on a database, it is a good practice to encrypt those data, in such a scenario symmetric key encryption is much more suitable than RSA.

There are plenty of other libraries which provide symmetric key encryption, however it is recommended to use libraries like openSSL or PHPSecLib as they are extensively tested and well maintained. My advice is to use openSSL as much as possible, however due to limitations on your server, it may not be possible to use openSSL for RSA but it can always be used for symmetric key encryption.

Will check the PHP code for the task. It is simple !

My PHP version is PHP Version 7.0.10 and using OpenSSL/1.0.2h, if you want to check yours you can use phpinfo(); function which gives all information regarding your PHP installation.

<?PHP 
$text = 'This is a secret message that should be encrypted before saving it to the database so that even the database is compromised the attacker wont be able to steal data'; 

$encryption_key = 'password'; $iv = 'randomdigit16bit'; 

$encrypted_data = openssl_encrypt($text, 'aes-256-cbc', $encryption_key, OPENSSL_RAW_DATA, $iv); 

$encrypted_data = base64_encode($encrypted_data); 
var_dump($encrypted_data); 
?>

The code is self explaining, openssl_encrypt is the function that should be used and $text is the data that should be encrypted, then the next parameter is the cipher method, $encryption_key is the key to decrypt the encrypted text. This needs to be stored as it is required later to decrypt the data. I ll discuss about storing keys securely in a future blog post, as it is quite out of the scope for this topic.

Decryption is to be carried out as follow:

<?PHP

$text = 'This is a secret message that should be encrypted before saving it to the database so that even the database is compromised the attacker wont be able to steal data';

$encryption_key = 'password';
$iv = 'randomdigit16bit';

$encrypted_data = openssl_encrypt($text, 'aes-256-cbc', $encryption_key, OPENSSL_RAW_DATA, $iv);

//$encrypted_data = base64_encode($encrypted_data);

$decrypted_data = openssl_decrypt($encrypted_data, 'aes-256-cbc', $encryption_key, OPENSSL_RAW_DATA, $iv);

var_dump($decrypted_data);

?>

Same as the openssl_encrypt function openssl_decrypt function could be used. Note that same $encryption_key and the $iv have been used.

Same as the $encryption_key, $iv should be same in encryption and decryption. $iv is known as the Initialization Vector which adds an extra layer of protection. It can be a random 16 bits string and the value should be stored as it requires in the decryption process as same as the encryption key.

The role of the $iv (Initialization Vector) is to differentiate the encrypted text. For an example the encryption key could be common per user or your web site etc. But you can use a random $iv per each encryption. As a result if you encrypt the same value using the same key, the result is going to be different when you use two different $iv.

Following method can be used to generate 16 bits IV. Make sure you store the IV otherwise decrypted data will not be able to decrypt back.

$iv = openssl_random_pseudo_bytes (16);

That is it, simple and handy isnt it?

Permutations with Repetition

Permutation is all about ordering objects in certain ways.

For an example, it is possible to order letters A B C D into 24 words. General form is n!. Since there are 4 distinct letters number of ways are 4! which is 24. But what if there are identical objects. For an example lets say we need to order following letters, A B B C D, note that there are 2 Bs.

Such situations are termed as “Permutations with Repetitions”.

Taking the above example of 5 letters, A B B C D. If the letters were distinct then there should be 5! ways of ordering them. But as it got 2 Bs the number of ways should get reduced, because it doesn’t really matter which B comes first and which B comes next. Both are identical. As a result we need to filter-out such occurrences.

In order to achieve the correct result, the total number of permutations which is 5! should be divided by the number of ways that the identical objects can be arranged. In this case it is 2Bs, 2!. So the answer is 5!/2!

 EXAMPLES

Lets see how the word “R E F E R E N C E” can be written in different ways.

Note that it has 9 letters. R is repeated twice, E is repeated four-times. Therefore if there were no identical letters then number of ways are 9!. But since there are 2 Rs and 4 Es, 9! should be divided by the number of ways that the identical letters can be arranges which is 2! for R and 4! for E. So the number of ways are 9! / (2! 4!)  = 7560

Lets see how following digits can be arranged 2, 2, 2, 7, 7, 8, 8, 8, 9

There are three 2s, two 7s, three 8s and one 9. Again 9 digits therefore total number of ways are 9!, but it should be divided by the repeating digits. Therefore the total number of ways are 9!/(3! 2! 3!) =  5040

Selecting and Arranging

Sometimes we need to order objects, first selecting them from a pool of objects and then arrange them in an order. Lets assume we are given 4 distinct letters and we need to group them and create two letter words. Then we have total number of ways of 4! / (4-2)! = 12

It can be termed as nPr = n! / (n-r)!, where the n is the pool size and the r is the number of objects that can be selected.

If there are identical objects them as we did early we need to divide the total number of ways from the number of ways that he identical objects can be arranged.

EXAMPLE

If the object pool is “A B B C C C D E”, how many ways are there to construct 4 letter words out of them?

Since there are 8 letters in the pool and as we get 4 letters out of it, total number of arrangements are 8! / (8 – 4) ! = 1680

Then as there are identical objects, 2Bs and 3Cs, total number of ways 1680 / (2! 3!) = 140

In other words: 8 ! / {(8 -4)! * 2! * 3!} = 140

If you are interested consider taking up following quizzes:

Some worked-out examples
http://www.vitutor.com/statistics/combinatorics/permutations_repetition.html

Calculator
http://www.dcode.fr/permutations-with-repetitions

Quiz
https://brilliant.org/practice/pemutations-with-repetition-easy/?subtopic=counting&chapter=permutations

Handling arrays (lists) in Python

Arrays are one of the fundamentals in any programming language. However if you have used Python; for example, you may not find arrays in it. Instead you get list. It is a more general form of an array.

I prefer using NumPy library for handling arrays in real-time python developments. However it is required to have a basic knowledge of handling arrays in Python first.

List [ ]

List is a data structure that holds values of any type. It can be a collection of strings, integers or any other valid data type in python. They are dynamic (known as mutable too), meaning that you can add or delete values as you wish.

Define a List with [ ]

It is quite same as other languages, you can use [ ] to define a list.

newArray = []

or with values

newArray = ["Population","X","size",200,"size"]

As in arrays, the element counts starts from 0 and you can use “slicing” in Lists too.

print (newArray[2])

you may use the slicing to assign values to a List elements too.

newArray[2] = 100

You may notice that you can assign a new value and it can be in a different type.

Following is a python script showing things we discussed so far

#!/usr/bin/python
newArray = ["Population","X","size",200,"size"]
print (newArray)
print ("Property of X = " + newArray[2])
newArray[3] = 200/3.5
print (newArray)

m-D List

It is possible to define multi dimensional lists and they behave quite similar to multidimensional arrays.

newArray = ["POST",["Status Code",100,200,300],["fail","pass","error"]]

you can use any combination of data types and any number of dimensions. Again slicing can be used to retrieve or assign values as we have observed above. Refer to the example code below:

#!/usr/bin/python
newArray = ["POST",["Status Code",100,200,300],["fail","pass","error"]]
print (newArray[1][2])
newArray[2][1] = "Success"
print (newArray)

Associative Arrays in Python

However our goal in this post is to see how associative arrays can be handled in Python. In Python associated arrays are termed as dictionaries. Simply it is ordered key-value pairs.

How to define a dictionary:

dataArray = {"method":"POST", "action":"file.py", "status": 500}

So that later you can use the key value to retrieve the value of the element.

dataArray["action"]

It is possible to use dict(sequence) function to create a dictionary too.

seq = (("method","POST"), ("action","file.py"), (2,500))

dataArray = dict(seq)

Values can be altered referring to the key value

seq = (("method","POST"), ("action","file.py"), (2,500))
dataArray = dict(seq)
dataArray[2] = 100
print (dataArray)

To delete an element, del(element) statement can be used.

seq = (("method","POST"), ("action","file.py"), (2,500))<span 				data-mce-type="bookmark" 				id="mce_SELREST_start" 				data-mce-style="overflow:hidden;line-height:0" 				style="overflow:hidden;line-height:0" 			></span>
dataArray = dict(seq)
del(dataArray["action"])
print (dataArray)

Methods on List

List data type has more methods that are very useful, will cover them briefly.

list.count(x) – Return the number of times value x appears in the list.

list.append(x) – Add element x to the list

list.extend(newList) – Extend the list by appending all the items in the newList

list.insert(n, x) – Insert the element x at n position. The current element at the position n will be moved backward.

list.remove(x) – Remove element which is the first item having the value x

list.pop([i]) – i is optional, remove the element in position i

list.index(x) – Return the index of the first element whose value is x in the list.

list.reverse() – Reverse the elements of a list

In the next part of the post will check how to implement basic data-structures such as stack and queue in python using lists.

Stack

Stack is analogous to a pile of books. The elements which goes last comes first. Therefore stack is a list where the index 0 of the list is the first element of the stack (this element will be the last element to be taken out).

#!/usr/bin/python
stack = [1, 2, 3, 4]
#add elements to the stack
stack.append(5)
stack.append(6)
print(stack)
#taking elements out
x = stack.pop()
print(x)

Queue

Not like stacks, in queues element which goes first come out first. Therefore it is possible to use pop() to retrieve values from a queue but when appending elements it should be placed at the beginning of the list. That is quite inefficient in lists as whole list should be shifted right to accommodate space to the new element.

It is recommended to use collections.deque in python for this purpose which is much more efficient.

However in this post will see how queues can be implemented using the knowledge we have gained so far.

#!/usr/bin/python
queue = [4,3,2,1]
value = [5]
value.extend(queue)
queue = value
print (queue)

Note that in the above example, the new value has been define as an element having one element. Otherwise it is not possible to use this technique.

Following is another way:

#!/usr/bin/python
queue = [4,3,2,1]
queue.reverse()
queue.append(5)
queue.reverse()
print (queue)

Both techniques have 4 lines but I guess that the first method should be more efficient.

Will write on NumPy in the next post.

Have you lived yet?

We live this one routing of a day for 75 years and we call it life, no that is not life. If you are still thinking why you have been sent here, if you are still juggling with the concept why you are here, you have not lived yet. You work hard, you make money , you do it for your self. that is not life.

You go out, seek for people who need your help, you make their lives better, you become that sponge which can absorb all the negativity and you become that person who can emit beautiful positive vibes, and when you realize you have changed someone’s life and because of you, this person didn’t give up that is the day when you live.