Combinatorial algorithms(permutations, combinations, powersets, subsets et, al) had never been my forte.

Infact, I was quite scared of them.
Presumably an irrational fear that stuck with after a failed effort in my graduate years.

No matter, This weekend, I set out to remedy that.
I didn’t want to read on the algorithms before implementing and decided I’d go pencil-and-paper and implement one that occurs naturally to me.

Here goes the result of that –

1. Generate unordered arrangements (combinations, nCr)


#!/usr/bin/python

def generate_combinations_helper(lst, a, prefix, startindex, n, r):
	if (startindex >= n):
		return

	prefix.append(a[startindex])

	if len(prefix) == r:
		lst.append(prefix[:])
		return

	generate_combinations_helper(lst, a, prefix[:], startindex+1, n, r)

	for i in range(startindex+2, n):
		generate_combinations_helper(lst, a, prefix[:], i, n, r)

def generate_combinations(a, n, r):
	combinations = []
	for i in range(n, r-1, -1):
		curr = generate_combinations_helper (combinations, a, [], 0, i, r)
		a.pop(0)

	return combinations

def main():
	n = int(raw_input())
	r = int(raw_input())
	a = range(1, n+1)

	combinations = generate_combinations(a, n, r)
	print len(combinations)
	for i in combinations:
		print i

if __name__ == "__main__":
	main()

Ofcourse, It generates all nCk, 0 <= k <= r to generate nCr arrangements.
So, a powerset can be constructed with r = n.

Although, I wrote a revised version, one that stores the subsets ordered by their length.

2. Powersets (use nC0 + nC1 + … + nCn == 2**n)

#!/usr/bin/python

# Add the current subset to the powerset list ordered by size
def add_to_powerset(powerset, prefix):
	i = len(prefix)

	if prefix not in powerset[i]:
		powerset[i].append(prefix)

# Generate subsets starting with given prefix
def generate_power_set_helper(powerset, a, prefix, startindex, n):
	if (startindex >= n):
		return

	prefix.append(a[startindex])
	add_to_powerset(powerset, prefix[:])

	if len(prefix) == n:
		return

	generate_power_set_helper(powerset, a, prefix[:], startindex+1, n)
	add_to_powerset(powerset, prefix[:])

	for i in range(startindex+2, n):
		generate_power_set_helper(powerset, a, prefix[:], i, n)
		add_to_powerset(powerset, prefix[:])

# Lose the starting elements of the set, one at a time to generate subsets starting from 2,3,... etc.
def generate_power_set(powerset, a, n):
	for i in range(n, 0, -1):
		generate_power_set_helper (powerset, a, [], 0, i)
		a.pop(0)

def main():
	n = int(raw_input())
	a = range(1, n+1)

	# Initialize an empty 2D list to store subsets ordered by length
	powerset = []
	for i in range(0, n+1):
		powerset.append([])

	generate_power_set(powerset, a, n)

	for i in range(0, n+1):
		print powerset[i]

if __name__ == "__main__":
	main()

And now, to the permutations.
I cheated a little here.
Generating nPr combinations proved to be a tough task, So I decided I’ll use the combinations and get an ordered rPr permutations for each combination generated.

3. Generate all ordered arrangements a.k.a. permutations of ‘n’ elements

#!/usr/bin/python

# Replicate the current nP(k-1) permutations 'k' times to make room for a new element
def replicate(a, k):
	n = len(a)
	for j in range(1, k):
		for i in range(0, n):
			a.append(a[i][:])

# Insert new 'number' into the current permutation arrangement nP(k-1) one 'slot' at a time
def arrange(a, number, k):
	n = len(a) / k
	for j in range(0, k):
		for i in range (0, n):
			a[j*n+i].insert(j, number)

# Generate all ordered arrangements(permutations) of elements in list b
def permute_all(b, n):
	permutations = [[]]

	for i in range(1, n+1):
		replicate(permutations, i)
		arrange(permutations, b[i-1], i)

	return permutations

def main():
	n = int(input())
	a = range(1, n+1)
	permutations = permute_all(a, n)

	permutations.sort()
	for i in permutations:
		print i

if __name__ == "__main__":
	main()

4. Generate ‘r’ ordered arrangements (permutations) of ‘n’ elements (use nPr == nCr * r!)


#!/usr/bin/python

def generate_permutations(a, n, r):
	# Generate unordered arrangements first
	combinations = generate_combinations(a, n, r)

	# for each unordered arrangement of length r in nCr, generate rPr ordered arrangements (permutations)
	permutations = []
	for combination in combinations:
		permutations_rr = permute_all(combination, r)
		for permutation in permutations_rr:
			permutations.append(permutation)

	return permutations

def main():
	n = int(raw_input())
	r = int(raw_input())
	a = range(1, n+1)

	permutations = generate_permutations(a, n, r)
	print len(permutations)
	for i in permutations:
		print i

if __name__ == "__main__":
	main()

Now, to the arduous task of translating this to Haskell. 🙂