Python recursive permutation by integer and returns a set of tuples-CodePudding

First and foremost, I have searched many sites and have taken so much time finding a way to implement this specific requirement. To name a few, this and this from SO and many others from external sites.

The requirement is fairly simple to understand.

I cannot use import and can only use recursive to achieve this task. This function alone must be able to solve the problem by itself. No helper functions allowed.

I have to write a function with this definition:

def permutation(n: int) -> set[tuple[int]]:

The expected result when calling permutation(3) is as follows:

{(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)}

I feel so frustrated that I cannot come up with any useful attempt to provide here. I tried to think of a solution for this but couldn't come up with anything useful. Therefore, I have no example code to start with.

CodePudding user response：

The idea is that if you can get the list of every permutation for n - 1, you can insert n in between every point within those permuted results.

def permutation(n):
    if n == 0:
        # base case
        return {()}
    result = set()
    for x in permutation(n - 1):
        for i in range(n):
            # insert n in position i in the permutation of all of the lesser numbers
            result.add(x[:i]   (n,)   x[i:])
    return result