Python recursive permutation by integer and returns a set of tuples

Question

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.

I'm guessing you're not allowed to define a helper function within your permutation() function? — rchome
– rchome, Commented Dec 10, 2021 at 4:52

rchome · Accepted Answer · 2021-12-10 06:06:18Z

2

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

edited Dec 10, 2021 at 6:06

answered Dec 10, 2021 at 5:01

rchome

2,72310 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Python recursive permutation by integer and returns a set of tuples

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related