Programming interview tip : Combinations from a list

This question will be discussed in python, since it is uber simple to write functioning yet short programs in :)

Say you have a list of n items e.g.
seq = [1,2,3]

Find products of all items with each other
This is the simplest question.
Solution:

	seq = [1,2,3]
	n=len(seq)
	for i in range(n):
	for j in range(n):
	print "%s * %s = %s"%(seq[i],seq[j],seq[i]*seq[j])

view raw gistfile1.py hosted with ❤ by GitHub

This gives the following output:

1 * 1 = 1
1 * 2 = 2
1 * 3 = 3
2 * 1 = 2
2 * 2 = 4
2 * 3 = 6
3 * 1 = 3
3 * 2 = 6
3 * 3 = 9

Find unique products of the items with each other
This means that you need that you can only have 1*2 or 2*1 etc
Solution: Really simple to do. Each time in the inner loop start at i rather than 0 as shown:

	seq = [1,2,3]
	n=len(seq)
	for i in range(n):
	for j in range(i,n):
	print "%s * %s = %s"%(seq[i],seq[j],seq[i]*seq[j])

view raw gistfile1.py hosted with ❤ by GitHub

This gives the following output:

1 * 1 = 1
1 * 2 = 2
1 * 3 = 3
2 * 2 = 4
2 * 3 = 6
3 * 3 = 9

Basically notice at each increment of i we do not allow j to go back.

Find unique products and do not multiply a list item with itself
This means that you cannot have 1*1 , 2*2 etc.
Solution: In the inner loop you need to avoid starting at i and rather start at i+1 (since this is the i*i case we need to avoid).

	seq = [1,2,3]
	n=len(seq)
	for i in range(n):
	for j in range(i+1,n):
	print "%s * %s = %s"%(seq[i],seq[j],seq[i]*seq[j])

view raw gistfile1.py hosted with ❤ by GitHub

Also if this is all you do at i = n the inner loop will not run so its better to stop the outer loop at n-1

	seq = [1,2,3]
	n=len(seq)
	for i in range(n-1):
	for j in range(i+1,n):
	print "%s * %s = %s"%(seq[i],seq[j],seq[i]*seq[j])

view raw gistfile1.py hosted with ❤ by GitHub

In both cases the output will be:

1 * 2 = 2
1 * 3 = 3
2 * 3 = 6

Enjoy!