Combinatorial Algorithms
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. 🙂
Leave a Reply