# -*- coding: utf-8 -*-
# Python 2.7
'''From here: http://stackoverflow.com/questions/4250125/generate-permutations-of-list-with-repeated-elements
and here: http://b...content-available-to-author-only...n.se/2008/04/lexicographic-permutations-using.html'''
 
def lexicographic_permutations(seq):
    '''Algorithm L for The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations.'''
 
    def reverse(seq, start, end):
        '''In-place reversion. Start and end denote the slice ends which forms the chunk to reverse'''
        # seq = seq[:start] + reversed(seq[start:end]) + \
        #       seq[end:]
 
        end -= 1
        while start < end:
            seq[start], seq[end] = seq[end], seq[start]
            start += 1
            end -= 1
 
 
    #Some checks
    if not seq:
        raise StopIteration
 
    try:
        seq[0]
    except TypeError:
        raise TypeError("seq must allow random access.")
 
 
    end = len(seq)
    seq = seq[:] #copy the input sequence
 
    yield seq #return the seq itself as a first value
 
 
    while True:
        j = end - 1
        while True:
            # Step 1.
            j -= 1
            if j == -1:
                raise StopIteration 
            if seq[j] < seq[j+1]:
                # Step 2.
                l = end - 1
                while not seq[j] < seq[l]:
                    l -= 1
                seq[j], seq[l] = seq[l], seq[j]
                # Step 3.
                reverse(seq, j+1, end)
                # Change to yield references to get rid of
                # (at worst) |seq|! copy operations.
                yield seq[:]
                break
 
 
if __name__ == '__main__':
    import timeit
    #use 'pass' instead of 'print(p)' to get rid of hefty print function time complexity charges.
    t = timeit.Timer(stmt='for p in lexicographic_permutations(range(9)): pass',setup='from __main__ import lexicographic_permutations')
    print(t.timeit(number=1))
 
 
 

IyAtKi0gY29kaW5nOiB1dGYtOCAtKi0KIyBQeXRob24gMi43CicnJ0Zyb20gaGVyZTogaHR0cDovL3N0YWNrb3ZlcmZsb3cuY29tL3F1ZXN0aW9ucy80MjUwMTI1L2dlbmVyYXRlLXBlcm11dGF0aW9ucy1vZi1saXN0LXdpdGgtcmVwZWF0ZWQtZWxlbWVudHMKYW5kIGhlcmU6IGh0dHA6Ly9iLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5uLnNlLzIwMDgvMDQvbGV4aWNvZ3JhcGhpYy1wZXJtdXRhdGlvbnMtdXNpbmcuaHRtbCcnJwoKZGVmIGxleGljb2dyYXBoaWNfcGVybXV0YXRpb25zKHNlcSk6CiAgICAnJydBbGdvcml0aG0gTCBmb3IgVGhlIEFydCBvZiBDb21wdXRlciBQcm9ncmFtbWluZywgVm9sdW1lIDQsIEZhc2NpY2xlIDI6IEdlbmVyYXRpbmcgQWxsIFR1cGxlcyBhbmQgUGVybXV0YXRpb25zLicnJwoKICAgIGRlZiByZXZlcnNlKHNlcSwgc3RhcnQsIGVuZCk6CiAgICAgICAgJycnSW4tcGxhY2UgcmV2ZXJzaW9uLiBTdGFydCBhbmQgZW5kIGRlbm90ZSB0aGUgc2xpY2UgZW5kcyB3aGljaCBmb3JtcyB0aGUgY2h1bmsgdG8gcmV2ZXJzZScnJwogICAgICAgICMgc2VxID0gc2VxWzpzdGFydF0gKyByZXZlcnNlZChzZXFbc3RhcnQ6ZW5kXSkgKyBcCiAgICAgICAgIyAgICAgICBzZXFbZW5kOl0KICAgICAgICAKICAgICAgICBlbmQgLT0gMQogICAgICAgIHdoaWxlIHN0YXJ0IDwgZW5kOgogICAgICAgICAgICBzZXFbc3RhcnRdLCBzZXFbZW5kXSA9IHNlcVtlbmRdLCBzZXFbc3RhcnRdCiAgICAgICAgICAgIHN0YXJ0ICs9IDEKICAgICAgICAgICAgZW5kIC09IDEKCgogICAgI1NvbWUgY2hlY2tzCiAgICBpZiBub3Qgc2VxOgogICAgICAgIHJhaXNlIFN0b3BJdGVyYXRpb24KCiAgICB0cnk6CiAgICAgICAgc2VxWzBdCiAgICBleGNlcHQgVHlwZUVycm9yOgogICAgICAgIHJhaXNlIFR5cGVFcnJvcigic2VxIG11c3QgYWxsb3cgcmFuZG9tIGFjY2Vzcy4iKQoKCiAgICBlbmQgPSBsZW4oc2VxKQogICAgc2VxID0gc2VxWzpdICNjb3B5IHRoZSBpbnB1dCBzZXF1ZW5jZQogICAgCiAgICB5aWVsZCBzZXEgI3JldHVybiB0aGUgc2VxIGl0c2VsZiBhcyBhIGZpcnN0IHZhbHVlCgogICAKICAgIHdoaWxlIFRydWU6CiAgICAgICAgaiA9IGVuZCAtIDEKICAgICAgICB3aGlsZSBUcnVlOgogICAgICAgICAgICAjIFN0ZXAgMS4KICAgICAgICAgICAgaiAtPSAxCiAgICAgICAgICAgIGlmIGogPT0gLTE6CiAgICAgICAgICAgICAgICByYWlzZSBTdG9wSXRlcmF0aW9uIAogICAgICAgICAgICBpZiBzZXFbal0gPCBzZXFbaisxXToKICAgICAgICAgICAgICAgICMgU3RlcCAyLgogICAgICAgICAgICAgICAgbCA9IGVuZCAtIDEKICAgICAgICAgICAgICAgIHdoaWxlIG5vdCBzZXFbal0gPCBzZXFbbF06CiAgICAgICAgICAgICAgICAgICAgbCAtPSAxCiAgICAgICAgICAgICAgICBzZXFbal0sIHNlcVtsXSA9IHNlcVtsXSwgc2VxW2pdCiAgICAgICAgICAgICAgICAjIFN0ZXAgMy4KICAgICAgICAgICAgICAgIHJldmVyc2Uoc2VxLCBqKzEsIGVuZCkKICAgICAgICAgICAgICAgICMgQ2hhbmdlIHRvIHlpZWxkIHJlZmVyZW5jZXMgdG8gZ2V0IHJpZCBvZgogICAgICAgICAgICAgICAgIyAoYXQgd29yc3QpIHxzZXF8ISBjb3B5IG9wZXJhdGlvbnMuCiAgICAgICAgICAgICAgICB5aWVsZCBzZXFbOl0KICAgICAgICAgICAgICAgIGJyZWFrCgoKaWYgX19uYW1lX18gPT0gJ19fbWFpbl9fJzoKICAgIGltcG9ydCB0aW1laXQKICAgICN1c2UgJ3Bhc3MnIGluc3RlYWQgb2YgJ3ByaW50KHApJyB0byBnZXQgcmlkIG9mIGhlZnR5IHByaW50IGZ1bmN0aW9uIHRpbWUgY29tcGxleGl0eSBjaGFyZ2VzLgogICAgdCA9IHRpbWVpdC5UaW1lcihzdG10PSdmb3IgcCBpbiBsZXhpY29ncmFwaGljX3Blcm11dGF0aW9ucyhyYW5nZSg5KSk6IHBhc3MnLHNldHVwPSdmcm9tIF9fbWFpbl9fIGltcG9ydCBsZXhpY29ncmFwaGljX3Blcm11dGF0aW9ucycpCiAgICBwcmludCh0LnRpbWVpdChudW1iZXI9MSkpCiAgICAKICAgIAo=