-4

I'm having trouble solving this task:

Write a recursive function that inputs a positive integer n and outputs all n! permutations of {1, 2, . . . , n}. Do not use any of Sage’s permutation commands. Use a list to store the values and work with that list.

Sample Input: 3

Expected Output: (1,2,3), (1,3,2), (2,3,1),(2,1,3), (3,1,2), (3,2,1)

All the things that I have found online generates permutation of list not for an integer.

I thought of calculating my factorial will help determining my output length. I could not thing of how would I do this. Please help me out! Thank you !

I have tried this 

def per(n):
   a = []
   for i in range(n):
       for j in range(n-i):
           a.append((i, j, n-i-j-1))
   return a
per(3)

[(0, 0, 2), (0, 1, 1), (0, 2, 0), (1, 0, 1), (1, 1, 0), (2, 0, 0)]

Improve this question
6
  • 3
    This function isn't recursive... Commented Oct 9, 2016 at 21:13
  • would you please help me out! I have been trying for long time, but I could not get it! Thank you ! Commented Oct 9, 2016 at 21:13
  • What you actually need is to return combinations of list(range(1, n + 1)). This could be done with itertools.permutations(range(1, n + 1), n). So, you could take a look at the docs for a possible implementation of this algorithm. Commented Oct 9, 2016 at 21:16
  • Have a look at this post. The question appears to be the same as yours and the response explains the algorithm quite well (although it's in Java). In your case n and kshould have the same value. Commented Oct 9, 2016 at 21:31
  • 1
    Not sure why this has been so heavily downvoted, it is not trivial for a beginner especially when a question like this stackoverflow.com/questions/39948902/… gets upvoted without a line of code. Commented Oct 9, 2016 at 22:53

2 Answers 2

Reset to default
2

You can use a backtracking algorithm to get the permutations:

def backtrack(n=None, arr=None,  i=0, out=None):
    if out is None:
        out = []
        arr = list(range(1, n + 1))
    if i == n:
        out.append(tuple(arr))
    else:
        for j in range(i, len(arr)):
            arr[i], arr[j] = arr[j], arr[i]
            backtrack(n, arr, i + 1, out)
            arr[i], arr[j] = arr[j], arr[i]
    return out

Just pass in the number of elements:

In [18]: backtrack(3)
Out[18]: [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 2, 1), (3, 1, 2)]

Or using a generator function:

def backtrack(n=None, arr=None,  i=0):
    if arr is None:
        arr = list(range(1, n + 1))
    if i == n:
        yield (tuple(arr))
    else:
        for j in range(i, len(arr)):
            arr[i], arr[j] = arr[j], arr[i]
            yield from backtrack(n, arr, i + 1)
            arr[i], arr[j] = arr[j], arr[i]



print(list(backtrack(3)))
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

Edit: I created a solution that uses no modules and works recursive:

def per(n, current_perm=[], results=[], remaining=None):
    if remaining is None:
        # Create a list of all items
        remaining = list(range(1, n+1))
    if len(remaining) == 1:
        # Only one item remaining - combine with
        # current path and add to results
        current_perm.append(remaining[0])
        results.append(current_perm)
        return
    for item in remaining:
        # Create a copy of the remaining list
        # and the current_permutation
        rem = list(remaining)
        cur = list(current_perm)
        # Remove the current item from the copy
        rem.remove(item)
        # Add the item to the current path
        cur.append(item)
        per(n, cur, results, rem)
    return results

print(per(3))

Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Improve this answer

4 Comments

Write a recursive function.
Whoops - I overlooked that requirement. Is it appropriate to delete this answer?
I understand. Since I have mentioned that I am not allowed to use any of Python build-in command. I believe since no one have voted, you can delete it. Thank you !
I just updated my answer and created a recursive solution. Not sure if it works similar to the solution of @PadraicCunningham, but it works ;-)

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.