2. Puzzles
  3. Next Permutation

Next Permutation

Aim: Find a larger permutation

We must move a larger number forward. So we should go from the tail to find any new number is smaller than a number behind it. If no next permutation, reverse list.

In [ ]:
def next_permutation(l):
    '''Give out the next permutation of list l
    >>> next_permutation([2, 1, 3])
    [2, 3, 1]
    >>> next_permutation([3, 2, 1])
    [1, 2, 3]
    '''
    n=len(l)
    for i in range(n-2, -1, -1):
        if l[i]<l[i+1]:
            for j in range(n-1, i, -1):
                if l[j]>l[i]:
                    l[j],l[i]=l[i],l[j]
                    l[i+1:]=l[n-1:i:-1]
                    return l
    return l[::-1]

# Peumutation Loop until reoccurance

In [ ]:
def permu_circ(l):
    '''Loop over permutations until goes back to initial permutation given by list l
    >>> for k in permu_circ([2,1,3]): print(k)
    [2, 1, 3]
    [2, 3, 1]
    [3, 1, 2]
    [3, 2, 1]
    [1, 2, 3]
    [1, 3, 2]
    '''
    assert(isinstance(l, list))
    ini=l.copy()
    while True:
        yield l
        l=next_permutation(l)
        if l==ini:
            break
    return

# Permutation of 1 to n

It is inefficient for all permutations in this way

In [3]:
def permu_num(n):
    '''Permutations over 1, 2,..., n
    >>> for k in permu_num(3): print(k)
    [1, 2, 3]
    [1, 3, 2]
    [2, 1, 3]
    [2, 3, 1]
    [3, 1, 2]
    [3, 2, 1]
    '''
    return permu_circ(list(range(1,n+1)))
if __name__=='__main__':
    import doctest
    doctest.testmod()

Comments

comments powered by Disqus