This is a real story: I tried to repair my headphone's cable, soldering 3 wires with minijack together. But which is left? Right? I couldn't even find ground wire. I asked myself, how many ways there are to solder 3 wires to 3-pin minijack? I could try them all and pick the combination that sounds best.
With Python's itertools module this is just:
import itertools
wires=["red", "green", "blue"]
for i in itertools.permutations(wires):
print i
('red', 'green', 'blue')
('red', 'blue', 'green')
('green', 'red', 'blue')
('green', 'blue', 'red')
('blue', 'red', 'green')
('blue', 'green', 'red')
(Just 6 ways.)
What if there are 4 wires?
import itertools
wires=["red", "green", "blue", "yellow"]
for i in itertools.permutations(wires):
print i
('red', 'green', 'blue', 'yellow')
('red', 'green', 'yellow', 'blue')
('red', 'blue', 'green', 'yellow')
('red', 'blue', 'yellow', 'green')
('red', 'yellow', 'green', 'blue')
('red', 'yellow', 'blue', 'green')
('green', 'red', 'blue', 'yellow')
('green', 'red', 'yellow', 'blue')
('green', 'blue', 'red', 'yellow')
('green', 'blue', 'yellow', 'red')
('green', 'yellow', 'red', 'blue')
('green', 'yellow', 'blue', 'red')
('blue', 'red', 'green', 'yellow')
('blue', 'red', 'yellow', 'green')
('blue', 'green', 'red', 'yellow')
('blue', 'green', 'yellow', 'red')
('blue', 'yellow', 'red', 'green')
('blue', 'yellow', 'green', 'red')
('yellow', 'red', 'green', 'blue')
('yellow', 'red', 'blue', 'green')
('yellow', 'green', 'red', 'blue')
('yellow', 'green', 'blue', 'red')
('yellow', 'blue', 'red', 'green')
('yellow', 'blue', 'green', 'red')
(24 ways.)
This is what is called "permutation" in combinatorics.
There was a hit and run. And you're police officer. And this is what your only witness says about 4-digit license plate of the guilty vehicle:
There was 13: 1 and 3 together, I'm sure, but not sure where, 13 as first 2 digits, last 2 digits or in the middle. And there was also 6, or maybe 8, or maybe even 9, not sure which, but one of them.
Combinatorics textbooks are abound with exercises like this: can you enumerate all possible 4-digit numbers constrained in this way?
import itertools
part1_list=["13"]
part2_list=["6", "8", "9"]
part3_list=["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
for i in itertools.product(part1_list, part2_list, part3_list):
for j in itertools.permutations(i):
print "".join(j)
1360 1306 6130 6013 ... 9139 9913 9139 9913( 180 numbers )
This is something you can query registered vehicle database with...
You forgot a password, but this is what you remember: there was a name of your parent, or wife, or one of children. Also, someone's year of birth. And one punctuation character, which are so recommended in passwords. Can you enumerate all possible passwords?
import itertools
part1_list=["jake", "melissa", "oliver", "emily"]
part2_list=["1987", "1954", "1963"]
part3_list=["!","@","#","$","%","&","*","-","=","_","+",".",","]
for part1 in part1_list:
for part2 in part2_list:
for part3 in part3_list:
l=[part1, part2, part3]
for i in list(itertools.permutations(l)):
print "".join(i)
jake1987! jake!1987 1987jake! 1987!jake !jake1987 ... 1963emily, 1963,emily ,emily1963 ,1963emily
( 936 of them in total )
But nested for's are not aesthetically pleasing. They can be replaced with "cartesian product" operation:
import itertools
part1_list=["jake", "melissa", "oliver", "emily"]
part2_list=["1987", "1954", "1963"]
part3_list=["!","@","#","$","%","&","*","-","=","_","+",".",","]
for l in itertools.product(part1_list, part2_list, part3_list):
for i in list(itertools.permutations(l)):
print "".join(i)
And this is a way to memorize it: the length of the final result equals to lengths of all input lists multiplied with each other (like "product").
import itertools
part1_list=["jake", "melissa", "oliver", "emily"] # 4 elements
part2_list=["1987", "1954", "1963"] # 3 elements
part3_list=["!","@","#","$","%","&","*","-","=","_","+",".",","] # 13 elements
for l in itertools.product(part1_list, part2_list, part3_list):
print l
('jake', '1987', '!')
('jake', '1987', '@')
('jake', '1987', '#')
('jake', '1987', '$')
('jake', '1987', '%')
('jake', '1987', '&')
('jake', '1987', '*')
...
('emily', '1963', '*')
('emily', '1963', '-')
('emily', '1963', '=')
('emily', '1963', '_')
('emily', '1963', '+')
('emily', '1963', '.')
('emily', '1963', ',')
4*3*13=156, and this is a size of a list, to be permuted...
Now the new problem: some Latin characters may be uppercased, some are lowercased. I'll add another "cartesian product" operation to alter a final string in all possible ways:
import itertools, string
part1_list=["jake", "melissa", "oliver", "emily"]
part2_list=["1987", "1954", "1963"]
part3_list=["!","@","#","$","%","&","*","-","=","_","+",".",","]
for l in itertools.product(part1_list, part2_list, part3_list):
for i in list(itertools.permutations(l)):
s="".join(i)
t=[]
for char in s:
if char.isalpha():
t.append([string.lower(char), string.upper(char)])
else:
t.append([char])
for q in itertools.product(*t):
print "".join(q)
JAke1987! JAkE1987! JAKe1987! JAKE1987! jake!1987 jakE!1987 jaKe!1987 jaKE!1987 ... ,1963eMIly ,1963eMIlY ,1963eMILy ,1963eMILY ,1963Emily ,1963EmilY ,1963EmiLy
( 56160 passwords )
Now leetspeak. This is somewhat popular only among youngsters, but still, this is what people of all age groups do: replacing "o" with "0" in passwords, "e" with "3", etc. Let's add this as well:
import itertools, string
part1_list=["jake", "melissa", "oliver", "emily"]
part2_list=["1987", "1954", "1963"]
part3_list=["!","@","#","$","%","&","*","-","=","_","+",".",","]
for l in itertools.product(part1_list, part2_list, part3_list):
for i in list(itertools.permutations(l)):
s="".join(i)
t=[]
for char in s:
if char.isalpha():
to_be_appended=[string.lower(char), string.upper(char)]
if char.lower()=='e':
to_be_appended.append('3')
elif char.lower()=='i':
to_be_appended.append('1')
elif char.lower()=='o':
to_be_appended.append('0')
t.append(to_be_appended)
else:
t.append([char])
for q in itertools.product(*t):
print "".join(q)
jake1987! jakE1987! jak31987! jaKe1987! jaKE1987! jaK31987! ... ,1963EM1lY ,1963EM1Ly ,1963EM1LY ,19633mily ,19633milY ,19633miLy
( 140400 passwords )
Obviously, you can't try all 140400 passwords on Facebook, Twitter or any other well-protected internet service. But this is a peace of cake to brute-force them all on password protected RAR-archive or feed them all to John the Ripper, HashCat, etc.
All the files: https://github.com/DennisYurichev/yurichev.com/tree/master/blog/comb.