Python的17种排列

以下是Python中实现17种排列的代码：

1. 字典序排列

import itertools

items = ['a', 'b', 'c']
permutations = list(itertools.permutations(items))
print(permutations)

2. 字典序反向排列

import itertools

items = ['a', 'b', 'c']
permutations = list(itertools.permutations(items, len(items)))[::-1]
print(permutations)

3. 任意排列

import itertools

items = ['a', 'b', 'c']
permutations = list(itertools.permutations(items, len(items)))
print(permutations)

4. 随机排列

import random

items = ['a', 'b', 'c']
random.shuffle(items)
print(items)

5. 不重复随机排列

import random

items = ['a', 'b', 'c']
permutations = []
while len(permutations) < 6:
    random.shuffle(items)
    if items not in permutations:
        permutations.append(list(items))
print(permutations)

6. 非递归排列

def next_permutation(a):
    i = len(a) - 2
    while not (i < 0 or a[i] < a[i+1]):
        i -= 1
    if i < 0:
        return False
    j = len(a) - 1
    while not (a[j] > a[i]):
        j -= 1
    a[i], a[j] = a[j], a[i]
    a[i+1:] = reversed(a[i+1:])
    return True

items = ['a', 'b', 'c']
permutations = []
while True:
    permutations.append(list(items))
    if not next_permutation(items):
        break
print(permutations)

7. 递归排列

def permute(arr, l, r):
    if l == r:
        print(arr)
    else:
        for i in range(l, r + 1):
            arr[l], arr[i] = arr[i], arr[l]
            permute(arr, l + 1, r)
            arr[l], arr[i] = arr[i], arr[l]

items = ['a', 'b', 'c']
permute(items, 0, len(items) - 1)

8. Johnson-Trotter算法

def johnson_trotter(n):
    def move(i, d):
        a[i], a[i+d] = a[i+d], a[i]
        s[i], s[i+d] = s[i+d], s[i]

    def permute(n):
        if n == 1:
            yield tuple(a)
        else:
            for i in range(n-1):
                yield from permute(n-1)
                if n % 2 == 0:
                    move(i, n-1)
                else:
                    move(0, n-1)
            yield from permute(n-1)

    a = list(range(1, n+1))
    s = [True] * n
    yield tuple(a)
    yield from permute(n)
    
permutations = list(johnson_trotter(3))
print(permutations)

9. Heap算法

def heap_permute(n):
    def generate(k):
        if k == 1:
            yield tuple(a)
        else:
            for i in range(k):
                yield from generate(k-1)
                j = i if k % 2 == 0 else 0
                a[j], a[k-1] = a[k-1], a[j]

    a = list(range(1, n+1))
    yield tuple(a)
    yield from generate(n)

permutations = list(heap_permute(3))
print(permutations)

10. Steinhaus-Johnson-Trotter算法

def steinhaus_johnson_trotter(n):
    def move(i, d):
        a[i], a[i+d] = a[i+d], a[i]
        s[i], s[i+d] = s[i+d], s[i]

    def permute(n):
        if n == 1:
            yield tuple(a)
        else:
            for i in range(n-1):
                yield from permute(n-1)
                if s[i]:
                    move(i, -1)
                else:
                    move(i+1, -1)
                s[i] = not s[i]
            yield from permute(n-1)

    a = list(range(1, n+1))
    s = [True] * n
    yield tuple(a)
    yield from permute(n)

permutations = list(steinhaus_johnson_trotter(3))
print(permutations)

11. 普通交换排列

def swap_permute(n):
    def generate(k):
        if k == 1:
            yield tuple(a)
        else:
            for i in range(k):
                generate(k-1)
                j = i if k % 2 == 0 else 0
                a[j], a[k-1] = a[k-1], a[j]

    a = list(range(1, n+1))
    yield tuple(a)
    yield from generate(n)

permutations = list(swap_permute(3))
print(permutations)

12. 字典序排列，递归实现

def permute_rec(arr):
    if len(arr) == 0:
        yield []
    elif len(arr) == 1:
        yield arr
    else:
        for i in range(len(arr)):
            rest = arr[:i] + arr[i+1:]
            for x in permute_rec(rest):
                yield [arr[i]] + x

items = ['a', 'b', 'c']
permutations = list(permute_rec(items))
print(permutations)

13. 字典序排列，生成器实现

def permute_gen(arr):
    if len(arr) == 0:
        yield []
    elif len(arr) == 1:
        yield arr
    else:
        for i in range(len(arr)):
            rest = arr[:i] + arr[i+1:]
            for x in permute_gen(rest):
                yield [arr[i]] + x

items = ['a', 'b', 'c']
permutations = [p for p in permute_gen(items)]
print(permutations)

14. 字典序排列，递归实现2

def permute_rec2(arr):
    if len(arr) == 0:
        return [[]]
    res = []
    for i in range(len(arr)):
        rest = arr[:i] + arr[i+1:]
        for x in permute_rec2(rest):
            res.append([arr[i]] + x)
    return res

items = ['a', 'b', 'c']
permutations = permute_rec2(items)
print(permutations)

15. 字典序排列，生成器实现2

def permute_gen2(arr):
    if len(arr) == 0:
        yield []
    else:
        for i in range(len(arr)):
            rest = arr[:i] + arr[i+1:]
            for x in permute_gen2(rest):
                yield [arr[i]] + x

items = ['a', 'b', 'c']
permutations = [p for p in permute_gen2(items)]
print(permutations)

16. 字典序排列，itertools.permutations实现

import itertools

items = ['a', 'b', 'c']
permutations = itertools.permutations(items)
print(list(permutations))

17. 字典序排列，自定义实现

def permutations(arr):
    if len(arr) == 0:
        yield []
    elif len(arr) == 1:
        yield arr
    else:
        for i in range(len(arr)):
            for x in permutations(arr[:i] + arr[i+1:]):
                yield [arr[i]] + x

items = ['a', 'b', 'c']
permutations = list(permutations(items))
print(permutations)