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

Maurice
  • 11,482
  • 2
  • 25
  • 45
ADAM
  • 105
  • 1
  • 7
  • 3
    This function isn't recursive... – ForceBru Oct 09 '16 at 21:13
  • would you please help me out! I have been trying for long time, but I could not get it! Thank you ! – ADAM Oct 09 '16 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](https://docs.python.org/3/library/itertools.html#itertools.permutations) for a possible implementation of this algorithm. – ForceBru Oct 09 '16 at 21:16
  • Have a look at [this](https://stackoverflow.com/questions/29910312/algorithm-to-get-all-the-combinations-of-size-n-from-an-array-java) 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 `k`should have the same value. – Maurice Oct 09 '16 at 21:31
  • Might help to think about what it means to break down this problem recursively. permutations([1,2,3]) = [ [1]+permutations([2,3]), [2]+permutations([1,3]), [3]+[permutations([1,2]) ]. Recursively break this down until the list argument to permutations is empty. Check out how this would be done in a functional language, such as Scala: https://www.youtube.com/watch?v=342WnW0Okng – IceArdor Oct 09 '16 at 22:39
  • 1
    Not sure why this has been so heavily downvoted, it is not trivial for a beginner especially when a question like this http://stackoverflow.com/questions/39948902/how-to-generate-all-possible-combinations-of-0-1-matrix-in-python/39948977?noredirect=1#comment67178801_39948977 gets upvoted without a line of code. – Padraic Cunningham Oct 09 '16 at 22:53

2 Answers2

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)))
Padraic Cunningham
  • 176,452
  • 29
  • 245
  • 321
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]]

Maurice
  • 11,482
  • 2
  • 25
  • 45
  • *Write a recursive function*. – Padraic Cunningham Oct 09 '16 at 22:14
  • Whoops - I overlooked that requirement. Is it appropriate to delete this answer? – Maurice Oct 09 '16 at 22:16
  • 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 ! – ADAM Oct 09 '16 at 22:26
  • I just updated my answer and created a recursive solution. Not sure if it works similar to the solution of @PadraicCunningham, but it works ;-) – Maurice Oct 09 '16 at 22:41