Permutations in natural vs. lexigraphical order

permutations in lexicographical order

def lex_permutations(array):
    if len(array) < 2:
        yield array
    else:
        for i in range(0, len(array)):
            for shorter_permutation in lex_permutations(array[:i] + array[i+1:]):
                yield array[i:i+1] + shorter_permutation

Permutations in natural order

def permutations(array):
    if len(array) < 2:
        yield array
    else:
        for shorter_permutation in permutations(array[1:]):
            for i in range(len(array)):
                yield shorter_permutation[:i] + array[0:1] + shorter_permutation[i:]