2022年 11月 8日

python实现排列和组合

python实现排列和组合

  • 一、模块
  • 二、python实现

一、模块

python模块实现排列和组合

  1. 组合
from itertools import combinations
s = "123456"
print(list(combinations(s, 4)))

# [('1', '2', '3', '4'), ('1', '2', '3', '5'), ('1', '2', '3', '6'), 
# ('1', '2', '4', '5'), ('1', '2', '4', '6'), ('1', '2', '5', '6'), 
# ('1', '3', '4', '5'), ('1', '3', '4', '6'), ('1', '3', '5', '6'), 
# ('1', '4', '5', '6'), ('2', '3', '4', '5'), ('2', '3', '4', '6'), 
# ('2', '3', '5', '6'), ('2', '4', '5', '6'), ('3', '4', '5', '6')]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

combinations(iterable,r)
iterable:可迭代对象,需要组合的对象
r:需要组合的位数
2. 排列

from itertools import permutations
s = "123456"
print(list(permutations(s, 2)))

# [('1', '2'), ('1', '3'), ('1', '4'), ('1', '5'), ('1', '6'), ('2', '1'), 
# ('2', '3'), ('2', '4'), ('2', '5'), ('2', '6'), ('3', '1'), ('3', '2'), 
# ('3', '4'), ('3', '5'), ('3', '6'), ('4', '1'), ('4', '2'), ('4', '3'), 
# ('4', '5'), ('4', '6'), ('5', '1'), ('5', '2'), ('5', '3'), ('5', '4'), 
# ('5', '6'), ('6', '1'), ('6', '2'), ('6', '3'), ('6', '4'), ('6', '5')]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

permutations(iterable,r)
iterable:可迭代对象,需要排列的对象
r:需要排列的位数

二、python实现

来源于官网,效率不如模块

  1. 组合
def combinations(iterable, r):
    pool = tuple(iterable)
    n = len(iterable)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i + 1, r):
            indices[j] = indices[j - 1] + 1
        yield tuple(pool[i] for i in indices)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  1. 排列
def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(iterable)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n - r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i + 1:] + indices[i:i + 1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22