# Generate successive k-length permutations. (3.00)
# @note This has come full circle to something very similar to the version that
# appears at docs.python.org/3/library/itertools.html#itertools.permutations
# @see 3UOMj3, vSELdo
 
def permutations(iterable, k=None):
    items = list(iterable)
    n = len(items)
    if k is None:
        k = n
    elif k > n:
        return
    cycle = list(range(k))
 
    while True:
        yield tuple(items[:k])
        for i in reversed(range(k)):
            j = cycle[i] + 1
            if j < n:
                cycle[i] = j
                items[i], items[j] = items[j], items[i]
                break
            cycle[i] = i
            items.append(items.pop(i))
        else:
            return
 
# Test.
 
import itertools
import time
 
n = 3
a = list(range(n))
for k in range(2+len(a)):
    print(list(permutations(a, k)))
    print(list(itertools.permutations(a, k)))
 
def test(f, a):
    t = time.process_time()
    for _ in f(a):
        pass
    t = time.process_time() - t
    print('Elapsed: {:.6f}s'.format(t))
    m = sum(1 for _ in f(a))
    n = sum(1 for _ in itertools.permutations(a))
    assert m == n
    for x, y in zip(f(a), itertools.permutations(a)):
        assert x == y
 
n = 8
a = list(range(n))
test(permutations, a)
test(itertools.permutations, a)

IyBHZW5lcmF0ZSBzdWNjZXNzaXZlIGstbGVuZ3RoIHBlcm11dGF0aW9ucy4gKDMuMDApCiMgQG5vdGUgVGhpcyBoYXMgY29tZSBmdWxsIGNpcmNsZSB0byBzb21ldGhpbmcgdmVyeSBzaW1pbGFyIHRvIHRoZSB2ZXJzaW9uIHRoYXQKIyBhcHBlYXJzIGF0IGRvY3MucHl0aG9uLm9yZy8zL2xpYnJhcnkvaXRlcnRvb2xzLmh0bWwjaXRlcnRvb2xzLnBlcm11dGF0aW9ucwojIEBzZWUgM1VPTWozLCB2U0VMZG8KCmRlZiBwZXJtdXRhdGlvbnMoaXRlcmFibGUsIGs9Tm9uZSk6CiAgICBpdGVtcyA9IGxpc3QoaXRlcmFibGUpCiAgICBuID0gbGVuKGl0ZW1zKQogICAgaWYgayBpcyBOb25lOgogICAgICAgIGsgPSBuCiAgICBlbGlmIGsgPiBuOgogICAgICAgIHJldHVybgogICAgY3ljbGUgPSBsaXN0KHJhbmdlKGspKQoKICAgIHdoaWxlIFRydWU6CiAgICAgICAgeWllbGQgdHVwbGUoaXRlbXNbOmtdKQogICAgICAgIGZvciBpIGluIHJldmVyc2VkKHJhbmdlKGspKToKICAgICAgICAgICAgaiA9IGN5Y2xlW2ldICsgMQogICAgICAgICAgICBpZiBqIDwgbjoKICAgICAgICAgICAgICAgIGN5Y2xlW2ldID0gagogICAgICAgICAgICAgICAgaXRlbXNbaV0sIGl0ZW1zW2pdID0gaXRlbXNbal0sIGl0ZW1zW2ldCiAgICAgICAgICAgICAgICBicmVhawogICAgICAgICAgICBjeWNsZVtpXSA9IGkKICAgICAgICAgICAgaXRlbXMuYXBwZW5kKGl0ZW1zLnBvcChpKSkKICAgICAgICBlbHNlOgogICAgICAgICAgICByZXR1cm4KCiMgVGVzdC4KCmltcG9ydCBpdGVydG9vbHMKaW1wb3J0IHRpbWUKCm4gPSAzCmEgPSBsaXN0KHJhbmdlKG4pKQpmb3IgayBpbiByYW5nZSgyK2xlbihhKSk6CiAgICBwcmludChsaXN0KHBlcm11dGF0aW9ucyhhLCBrKSkpCiAgICBwcmludChsaXN0KGl0ZXJ0b29scy5wZXJtdXRhdGlvbnMoYSwgaykpKQoKZGVmIHRlc3QoZiwgYSk6CiAgICB0ID0gdGltZS5wcm9jZXNzX3RpbWUoKQogICAgZm9yIF8gaW4gZihhKToKICAgICAgICBwYXNzCiAgICB0ID0gdGltZS5wcm9jZXNzX3RpbWUoKSAtIHQKICAgIHByaW50KCdFbGFwc2VkOiB7Oi42Zn1zJy5mb3JtYXQodCkpCiAgICBtID0gc3VtKDEgZm9yIF8gaW4gZihhKSkKICAgIG4gPSBzdW0oMSBmb3IgXyBpbiBpdGVydG9vbHMucGVybXV0YXRpb25zKGEpKQogICAgYXNzZXJ0IG0gPT0gbgogICAgZm9yIHgsIHkgaW4gemlwKGYoYSksIGl0ZXJ0b29scy5wZXJtdXRhdGlvbnMoYSkpOgogICAgICAgIGFzc2VydCB4ID09IHkKCm4gPSA4CmEgPSBsaXN0KHJhbmdlKG4pKQp0ZXN0KHBlcm11dGF0aW9ucywgYSkKdGVzdChpdGVydG9vbHMucGVybXV0YXRpb25zLCBhKQ==