How to pass by reference in XCAS ?

[Albert Chan]

Another example, in-place permutations of list.
We can swap 2 elements to create another permutation, this involved 3 assignments.

x = lst[i]; lst[i] = lst[j]; lst[j] = x;

We could reduce above to about 2 assignments, by reusing x.
Here is Ive's method, see Permutation Generation Methods, by Robert Sedgewick, page 148-149

Code:

def ives(lst, i, j):
    if i >= j: yield lst; return
    x = lst[i]
    idx = xrange(i+1, j+1)
    for pat in ives(lst, i+1, j-1): # (n-2)! permutations
        for block in idx:           # (n-1) blocks
            yield pat               # n     pats/block
            for k in idx:           # shift x to right
                pat[k-1] = pat[k]
                pat[k] = x
                yield pat
            pat[j] = pat[i]         # restore x to front
            pat[i] = x

>>> permute = lambda lst: ives(lst, 0, len(lst)-1)
>>> for pat in permute(range(1,6)): print pat
...
[1, 2, 3, 4, 5]
[2, 1, 3, 4, 5]
[2, 3, 1, 4, 5]
[2, 3, 4, 1, 5]
[2, 3, 4, 5, 1]
[1, 3, 4, 5, 2]
[3, 1, 4, 5, 2]
[3, 4, 1, 5, 2]
[3, 4, 5, 1, 2]
[3, 4, 5, 2, 1]
...