Напишите рекурсивную функцию, которая вводит положительное целое число n и выводит все перестановки {1, 2,. , , , П}

Question

У меня возникли проблемы, решая эту задачу:

Напишите рекурсивную функцию, которая вводит положительное целое число п и выходов все п! перестановки {1, 2,. , , , n}. Не используйте никакие команды перестановки Sage. Используйте список для хранения значений и работы с этим списком.

Пример ввода: 3

Ожидаемый результат: (1,2,3), (1,3,2), (2,3,1),(2,1,3), (3,1,2), (3,2,1)

Все вещи, которые я нашел в Интернете генерирует перестановку список не для целого.

Я думал о вычислении моего факториала, помогая определить мою выходную длину. Я не мог понять, как это сделать. Пожалуйста, помогите мне! Спасибо !

Я попытался это

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

Answer 1

Edit: Я создал решение, которое не использует модули и работает рекурсивная:

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

Выход:[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Answer 2

Вы можете использовать backtracking algorithm, чтобы получить перестановками:

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 

Просто передать количество элементов:

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

Или с помощью функции генератора:

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