"""
 heaps_permute.py

 Generate all permutations of a list of n items.
 Qdapted from https://en.wikipedia.org/wiki/Heap's_algorithm .
 "Not to be confused with heapsort."

 >>> for p in heaps_permute( (1,2,3) ):
 ...   print(p)
 [1, 2, 3]
 [2, 1, 3]
 [3, 1, 2]
 [1, 3, 2]
 [2, 3, 1]
 [3, 2, 1]

 Note that this uses a python language feature called "generators",
 indicated by the "yield" keyword in heaps_permute(items) which
 looks like a function ... but isn't really. Running it returns
 a generator object which produces a sequence of values.
 See for example https://docs.python.org/3/howto/functional.html
 for the details.

 Jim Mahoney | cs.bennington.college | May 2022 | MIT License
"""

def swap(items, i, j):
    """ swap items[i] with items[j], in place """
    tmp = items[i]
    items[i] = items[j]
    items[j] = tmp

def heaps_permute(items):
    """ return a python generator yielding every permutation of items """
    _items = list(items)    # Make a mutable copy of the items..
    n = len(_items)
    state = [0]*n
    yield list(_items)                    # Yield a copy of the original list.
    i = 0
    while i < n:
        if state[i] < i:
            if i % 2 == 0: # Even?
                swap(_items, 0, i)
                #(_items[0], _items[i]) = (_items[i], _items[0])
            else:
                swap(_items, state[i], i)
                #(_items[state[i]], _items[i]) = (_items[i], _items[state[i]])
            yield list(_items)            # Yield a copy of the next permutation.
            state[i] += 1
            i = 0
        else:
            state[i] = 0
            i += 1

if __name__ == '__main__':
    import doctest
    doctest.testmod()
    print("Passed all tests.")