This problem asks:

Given: A positive integer n≤7

Return: The total number of permutations of length n, followed by a list of all such permutations (in any order).

Restate the problem

Before putting the problem in my own words, I read:

I’m going to get a number less than or equal to 7. I need to return the number of possible permutations of a list of integers as long as that number. I also need to return a set of all of those permutations.

Solution steps

This certainly tests my new rule about not using libraries, since the math and itertools libraries include functions to do these two tasks.

I wrote a small, recursive program that calculates factorials. That encouraged me to try a recursive approach to generating permutations.

I wrote a simple recursive permutations function from scratch. It’s very similar to the recursive factorial function. You can see the full code here.

Python concepts

Both functions in this challenge were recursive in that they called themselves. The factorial code is easiest to understand:

def factorial(n):
    if n < 2:
        return 1
    else:
        return n * factorial(n - 1)

In English: For any n >= 2, return n * factorial of n - 1

The permutations function works almost the same way:

def permutations(input):
    if len(input) == 0:
        return []
    if len(input) == 1:
        return [input]
    set = []
    for j in range(len(input)):
        element = input[j]
        remainder = input[:j] + input[j+1:]
        for p in permutations(remainder):
            set.append([element] + p)
    return set

In English: for sets longer than one, return each element combined with the permutations from all the other elements.

To write the resulting permutations to a file in the format that Project Rosalind requires, I needed to strip out all the brackets and commas with:

file.write(str(perm).replace('[','').replace(']', '').replace(',',''))

Problem-solving concepts

Even though I did a lot of reading about how to write recursive functions for these two tasks, actually writing the code from scratch taught me a lot more than I would have learned using the math and itertools libraries.