"""
 permute.py

 Generate the permutations of a list, using a backtracking tree search.

 This code is based on the ideas at
 geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string

 There are other trickier approaches to this classic task;
 see wikipedia.org/wiki/Heap%27s_algorithm and
 wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations .

 And python has a built-in library to do this sort of thing;
 see https://docs.python.org/3/library/itertools.html .

 Jim Mahoney | cs.bennington.collete | April 2022 | MIT License
"""

def swap(xs, i, j):
    (xs[i], xs[j]) = (xs[j], xs[i])

def permute(xs, i=0, result=[]):
    """ return permutations of a list xs """
    if i == len(xs) - 1:
        result.append(list(xs))
    else:
        for j in range(i, len(xs)):
            swap(xs, i, j)
            permute(xs, i+1)
            swap(xs, i ,j)
    return result

if __name__ == '__main__':
    print('example: permute([1,2,3])')
    print(permute([1,2,3]))