[code] Python next_permutation & prev_permutation

def next_permutation(a):

    # if list has less than two elements, has no next permutation.
    if len(a) < 2: return False

    # step 1: find max i for a[i] > a[i+1]
    i = len(a)-2
    while i >= 0 and a[i] >= a[i+1]: i -= 1
    if i < 0: return False
    j = i + 1

    # step 2: find max k for a[k] > a[i]
    k = len(a) - 1
    while a[i] >= a[k]: k -= 1

    # step 3: swap a[i] and a[k]
    (a[i], a[k]) = (a[k], a[i])

    # step 4: reverse a[j:]
    a[j:] = a[:j-1:-1]

    return True

def prev_permutation(a):

    # if list has less than two elements, has no prev permutation.
    if len(a) < 2: return False

    # step 1: find max i for a[i] < a[i+1]
    i = len(a)-2
    while i >= 0 and a[i] <= a[i+1]: i -= 1
    if i < 0: return False
    j = i + 1

    # step 2: find max k for a[k] < a[i]
    k = len(a) - 1
    while a[i] <= a[k]: k -= 1

    # step 3: swap a[i] and a[k]
    (a[i], a[k]) = (a[k], a[i])

    # step 4: reverse a[j:]
    a[j:] = a[:j-1:-1]

    return True

【转载请附】愿以此功德,回向 >>

原文链接:https://www.huangwenchao.com.cn/2015/05/python-permutation.html【

Python next_permutation & prev_permutation】

发表评论

电子邮件地址不会被公开。 必填项已用*标注