# Generate successive k-length permutations. (2.00)
# @see 3UOMj3
 
def permutations(iterable, k=None):
    def detail(a, i, k):
        if i == k:
            yield tuple(a[:k])
        else:
            n = len(a)
            j = i
            while True:
                yield from detail(a, i+1, k)
                j += 1
                if j == n:
                    break
                a[i], a[j] = a[j], a[i]
            a.append(a.pop(i))
    a = list(iterable)
    n = len(a)
    k = n if k is None else k
    return detail(a, 0, k) if k <= n else []
 
# 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)

IyBHZW5lcmF0ZSBzdWNjZXNzaXZlIGstbGVuZ3RoIHBlcm11dGF0aW9ucy4gKDIuMDApCiMgQHNlZSAzVU9NajMKCmRlZiBwZXJtdXRhdGlvbnMoaXRlcmFibGUsIGs9Tm9uZSk6CiAgICBkZWYgZGV0YWlsKGEsIGksIGspOgogICAgICAgIGlmIGkgPT0gazoKICAgICAgICAgICAgeWllbGQgdHVwbGUoYVs6a10pCiAgICAgICAgZWxzZToKICAgICAgICAgICAgbiA9IGxlbihhKQogICAgICAgICAgICBqID0gaQogICAgICAgICAgICB3aGlsZSBUcnVlOgogICAgICAgICAgICAgICAgeWllbGQgZnJvbSBkZXRhaWwoYSwgaSsxLCBrKQogICAgICAgICAgICAgICAgaiArPSAxCiAgICAgICAgICAgICAgICBpZiBqID09IG46CiAgICAgICAgICAgICAgICAgICAgYnJlYWsKICAgICAgICAgICAgICAgIGFbaV0sIGFbal0gPSBhW2pdLCBhW2ldCiAgICAgICAgICAgIGEuYXBwZW5kKGEucG9wKGkpKQogICAgYSA9IGxpc3QoaXRlcmFibGUpCiAgICBuID0gbGVuKGEpCiAgICBrID0gbiBpZiBrIGlzIE5vbmUgZWxzZSBrCiAgICByZXR1cm4gZGV0YWlsKGEsIDAsIGspIGlmIGsgPD0gbiBlbHNlIFtdCgojIFRlc3QuCgppbXBvcnQgaXRlcnRvb2xzCmltcG9ydCB0aW1lCgpuID0gMwphID0gbGlzdChyYW5nZShuKSkKZm9yIGsgaW4gcmFuZ2UoMitsZW4oYSkpOgogICAgcHJpbnQobGlzdChwZXJtdXRhdGlvbnMoYSwgaykpKQogICAgcHJpbnQobGlzdChpdGVydG9vbHMucGVybXV0YXRpb25zKGEsIGspKSkKCmRlZiB0ZXN0KGYsIGEpOgogICAgdCA9IHRpbWUucHJvY2Vzc190aW1lKCkKICAgIGZvciBfIGluIGYoYSk6CiAgICAgICAgcGFzcwogICAgdCA9IHRpbWUucHJvY2Vzc190aW1lKCkgLSB0CiAgICBwcmludCgnRWxhcHNlZDogezouNmZ9cycuZm9ybWF0KHQpKQogICAgbSA9IHN1bSgxIGZvciBfIGluIGYoYSkpCiAgICBuID0gc3VtKDEgZm9yIF8gaW4gaXRlcnRvb2xzLnBlcm11dGF0aW9ucyhhKSkKICAgIGFzc2VydCBtID09IG4KICAgIGZvciB4LCB5IGluIHppcChmKGEpLCBpdGVydG9vbHMucGVybXV0YXRpb25zKGEpKToKICAgICAgICBhc3NlcnQgeCA9PSB5CgpuID0gOAphID0gbGlzdChyYW5nZShuKSkKdGVzdChwZXJtdXRhdGlvbnMsIGEpCnRlc3QoaXRlcnRvb2xzLnBlcm11dGF0aW9ucywgYSk=