Permutations

I was solving one of the puzzles in Project Euler, and the problem statement was related to encryption/decryption. There was a encrypted text file containing only numbers. Encryption technique used was of doing XOR with a 3 letter key. In order to find the three letter key, one had to do bruteforce. So, following is the code which can generate all possible combinations of a 3 letter word containing (0-9a-z). Possible combinations would be 36^3 = 46656.

Python rocked again :)

#!/usr/bin/python

# List of all the possible characters
vals=list("0123456789abcdefghijklmnopqrstuvwxyz")

# Number of digits where the above characters can fit into.
init="000"

# Total number of permutations :
# Formula: (total_possible_chars)^(lengh_of_numbers)
# In above case: (36)^3 = 46656

class HashTable:
	def __init__(self):
		self.list = {};
	def get(self, key):
		return self.list[key]
	def set(self,key,value):
		self.list.setdefault(key,[]).append(value);				
	
htable = HashTable();
htable.set(init, 0);

# Rotation logic. Take 1st char in a temporary variable,
# and copy the whole string starting from index 1 to 0th 
# location. Then copy the char stored in temp variable to 
# the last location. Once we get the string, store it in
# dictionary (hash) if not stored already

def rotate_left(string):
	global htable
	ts = string
	for i in range(1, len(string)):
		tchar = list(string)[0];
		string = string[1:]
		sl = list(string)
		sl.append(tchar)
		string =  "".join(sl)
		if (string == ts):
			break;
		if (htable.list.has_key(string) == False):
			htable.set(string, 0);


# List generation logic: Idea is to initalize the list with 
# all 0s. Then insert one char (out of all posible chars) at 
# a time to the last position. Something like:
# 	001
# 	002
# 	003
# 	...
# 	009
# Strings generated from this function will be passed to another
# function, which will rotate the whole string left by one and 
# insert the new char (again out of all possible chars) at the end. 
# Something like:
# 	010
# 	011
# 	012
# 	013
# 	...
# 	019
# Copy all such combination into a dictionary (hash) table. Once all 
# the values are stored in hash, just do rotate_left() on all the values. 
# Again, store all these values into hash, and sort the hash() to print 
# them in order.

tl = [init]
def generate_list(tl):
	global htable	
	for t in tl:
		for i in vals:
			tstr = insert_char_at_last(t, i);
			if (htable.list.has_key(tstr) == False):
				htable.set(tstr, 0);
				tl.append(tstr);

def insert_char_at_last(string, tchar):
	string = string[1:]
	sl = list(string)
	sl.append(tchar)
	string =  "".join(sl)
	return string


generate_list(tl)


# Generate all the combinations of the word by rotating
# each character left (by one position).

for keys in htable.list.keys():
	rotate_left(keys)
cnt = 0;

# Display keys in sorted order
tkeys = htable.list.keys
for keys in sorted(tkeys()):
	cnt = cnt + 1;
	print cnt, keys

Have fun!!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s