from random import randint

# generate one random permutation of array from 0 to n-1: (no recursion needed)
def genperm(n):
  P=[0]*n
  for i in range(0,n): P[i]=i   # create identity permutation
  for i in range(0,n-1):
     r = randint(i,n-1)
     P[i],P[r] = P[r],P[i]  # swap random number into ith position
  return P
#


# generate all possible permutations of an array

def genperms(A):  # generate and return list of permutations of array A
    n = len(A)
    if n<2: return [A]  # base case
    PERMS = []
    fix = n-1  # index of value to be fixed
    while fix>=0:
        #remove fix from P non-distructively
        P2 = A[0:fix]+A[fix+1:n]  # non-destructively remove A[fix]
        Pm = genperms(P2)
        for p in Pm: PERMS.append(p+[A[fix]]) # add fix to end of each
        fix -= 1
    # while fix
    return PERMS
    

print(genperms([0,1,2,3]))


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