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
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])

if len(prefix) == n:
return

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

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

# 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()
```