Tính toán và tạo thừa số, hoán vị và kết hợp trong Python

Kinh doanh

Toán học mô-đun tiêu chuẩn cho các hàm toán học trong Python có thể được sử dụng để tính toán các giai thừa. SciPy cũng có các chức năng tính tổng số hoán vị / tổ hợp.

Mô-đun itertools cũng có thể được sử dụng để tạo các hoán vị và kết hợp từ các danh sách (mảng), v.v. và liệt kê chúng.

Phần sau được giải thích ở đây, cùng với mã mẫu.

  • yếu tố:math.factorial()
  • Tính tổng số các hoán vị
    • math.factorial()
    • scipy.special.perm()
  • Tạo và liệt kê các hoán vị từ một danh sách:itertools.permutations()
  • Tính tổng số tổ hợp
    • math.factorial()
    • scipy.special.comb()
    • Cách không sử dụng math.factorial ()
  • Tạo và liệt kê các kết hợp từ danh sách:itertools.combinations()
  • Tính tổng số kết hợp trùng lặp
  • Tạo và liệt kê các kết hợp trùng lặp từ một danh sách:itertools.combinations_with_replacement()

Như một ví dụ về việc sử dụng hoán vị, điều sau đây cũng được giải thích.

  • Tạo đảo ngữ từ chuỗi

Nếu bạn muốn tạo một tổ hợp các phần tử của nhiều danh sách thay vì một danh sách, hãy sử dụng itertools.product () trong mô-đun itertools.

yếu tố:math.factorial()

Mô-đun toán học cung cấp một hàm giai thừa () trả về giai thừa.

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

Các giá trị âm, không phải là số nguyên sẽ dẫn đến lỗi ValueError.

# print(math.factorial(1.5))
# ValueError: factorial() only accepts integral values

# print(math.factorial(-1))
# ValueError: factorial() not defined for negative values

Tính tổng số các hoán vị

math.factorial()

Hoán vị là số trường hợp trong đó r được chọn từ n cái khác nhau và được xếp vào một hàng.

Tổng số các hoán vị, p, có được trong phương trình sau sử dụng thừa số.

p = n! / (n - r)!

Nó có thể được tính toán như sau bằng cách sử dụng hàm math.factorial (), trả về giai thừa. Toán tử ⌘, thực hiện phép chia số nguyên, được sử dụng để trả về một kiểu số nguyên.

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

print(permutations_count(4, 2))
# 12

print(permutations_count(4, 4))
# 24

scipy.special.perm ()

SciPy cung cấp một hàm scipy.special.perm () trả về tổng số hoán vị. Cần cài đặt SciPy riêng. Có sẵn từ phiên bản 0.14.0.

from scipy.special import perm

print(perm(4, 2))
# 12.0

print(perm(4, 2, exact=True))
# 12

print(perm(4, 4, exact=True))
# 24

exact=False
Đối số thứ ba được đặt như trên theo mặc định và trả về một số dấu phẩy động. Lưu ý rằng nếu bạn muốn lấy nó dưới dạng số nguyên, bạn cần đặt nó như sau.
exact=True

Lưu ý rằng chỉ “import scipy” sẽ không tải mô-đun scipy.special.

Thực thi perm () dưới dạng “từ scipy.special import perm” như trong ví dụ trên hoặc thực thi scipy.special.perm () dưới dạng “import scipy.special”.

Tạo và liệt kê các hoán vị từ một danh sách:itertools.permutations()

Không chỉ tổng số, mà còn có thể tạo và liệt kê các hoán vị từ danh sách (mảng), v.v.

Sử dụng hàm hoán vị () của mô-đun itertools.

Truyền một đối số có thể lặp lại (danh sách hoặc tập hợp) làm đối số đầu tiên và số phần được chọn làm đối số thứ hai trả về một trình lặp cho hoán vị đó.

import itertools

l = ['a', 'b', 'c', 'd']

p = itertools.permutations(l, 2)

print(type(p))
# <class 'itertools.permutations'>

Để liệt kê tất cả chúng, bạn có thể sử dụng vòng lặp for.

for v in itertools.permutations(l, 2):
    print(v)
# ('a', 'b')
# ('a', 'c')
# ('a', 'd')
# ('b', 'a')
# ('b', 'c')
# ('b', 'd')
# ('c', 'a')
# ('c', 'b')
# ('c', 'd')
# ('d', 'a')
# ('d', 'b')
# ('d', 'c')

Vì nó là một trình lặp hữu hạn, nó cũng có thể được chuyển đổi thành một kiểu danh sách với list ().

Khi số phần tử trong danh sách được lấy bằng len (), có thể khẳng định rằng nó khớp với tổng số hoán vị được tính từ giai thừa.

p_list = list(itertools.permutations(l, 2))

print(p_list)
# [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'a'), ('b', 'c'), ('b', 'd'), ('c', 'a'), ('c', 'b'), ('c', 'd'), ('d', 'a'), ('d', 'b'), ('d', 'c')]

print(len(p_list))
# 12

Nếu đối số thứ hai bị bỏ qua, hoán vị để chọn tất cả các phần tử sẽ được trả về.

for v in itertools.permutations(l):
    print(v)
# ('a', 'b', 'c', 'd')
# ('a', 'b', 'd', 'c')
# ('a', 'c', 'b', 'd')
# ('a', 'c', 'd', 'b')
# ('a', 'd', 'b', 'c')
# ('a', 'd', 'c', 'b')
# ('b', 'a', 'c', 'd')
# ('b', 'a', 'd', 'c')
# ('b', 'c', 'a', 'd')
# ('b', 'c', 'd', 'a')
# ('b', 'd', 'a', 'c')
# ('b', 'd', 'c', 'a')
# ('c', 'a', 'b', 'd')
# ('c', 'a', 'd', 'b')
# ('c', 'b', 'a', 'd')
# ('c', 'b', 'd', 'a')
# ('c', 'd', 'a', 'b')
# ('c', 'd', 'b', 'a')
# ('d', 'a', 'b', 'c')
# ('d', 'a', 'c', 'b')
# ('d', 'b', 'a', 'c')
# ('d', 'b', 'c', 'a')
# ('d', 'c', 'a', 'b')
# ('d', 'c', 'b', 'a')

print(len(list(itertools.permutations(l))))
# 24

Trong itertools.permutations (), các phần tử được xử lý dựa trên vị trí, không phải giá trị. Các giá trị trùng lặp không được tính đến.

l = ['a', 'a']

for v in itertools.permutations(l, 2):
    print(v)
# ('a', 'a')
# ('a', 'a')

Điều tương tự cũng áp dụng cho các chức năng sau, được mô tả bên dưới.

  • itertools.combinations()
  • itertools.combinations_with_replacement()

Tính tổng số tổ hợp

math.factorial()

Số lượng kết hợp là số lượng r miếng để chọn từ n miếng khác nhau. Thứ tự không được coi là trong hoán vị.

Tổng số tổ hợp c có được bởi phương trình sau.

c = n! / (r! * (n - r)!)

Nó có thể được tính toán như sau bằng cách sử dụng hàm math.factorial (), trả về giai thừa. Toán tử ⌘, thực hiện phép chia số nguyên, được sử dụng để trả về một kiểu số nguyên.

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

print(combinations_count(4, 2))
# 6

scipy.special.comb()

SciPy cung cấp một hàm scipy.special.comb () trả về tổng số hoán vị. Cần cài đặt SciPy riêng. Có sẵn từ phiên bản 0.14.0. Lưu ý rằng scipy.misc.comb () không triển khai lặp lại đối số được mô tả bên dưới.

from scipy.special import comb

print(comb(4, 2))
# 6.0

print(comb(4, 2, exact=True))
# 6

print(comb(4, 0, exact=True))
# 1

exact=False
Như với scipy.special.perm (), đối số thứ ba được đặt như trên theo mặc định và trả về một số dấu phẩy động. Lưu ý rằng nếu bạn muốn lấy nó dưới dạng số nguyên, bạn cần đặt nó như sau.
exact=True
Tổng số kết hợp trùng lặp cũng có thể nhận được với đối số thứ tư, sự lặp lại. Điều này được mô tả dưới đây.

Một lần nữa, lưu ý rằng chỉ “import scipy” sẽ không tải mô-đun scipy.special.

Như trong ví dụ trên, thực thi comb () là “from scipy.special import comb” hoặc thực thi scipy.special.comb () là “import scipy.special”. Điều tương tự cũng áp dụng cho “scipy.misc”.

Cách không sử dụng math.factorial ()

Một phương pháp khác chỉ sử dụng thư viện chuẩn và nhanh hơn phương pháp sử dụng math.factorial () là phương thức sau.

from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

print(combinations_count(4, 2))
# 6

print(combinations_count(4, 0))
# 1

Tạo và liệt kê các kết hợp từ danh sách:itertools.combinations()

Có thể tạo và liệt kê tất cả các kết hợp từ danh sách (mảng), v.v. cũng như tổng số.

Sử dụng hàm kết hợp () của mô-đun itertools.

Truyền một đối số có thể lặp lại (danh sách hoặc loại tập hợp) làm đối số đầu tiên và số phần được chọn làm đối số thứ hai trả về trình lặp cho tổ hợp đó.

l = ['a', 'b', 'c', 'd']

c = itertools.combinations(l, 2)

print(type(c))
# <class 'itertools.combinations'>

for v in itertools.combinations(l, 2):
    print(v)
# ('a', 'b')
# ('a', 'c')
# ('a', 'd')
# ('b', 'c')
# ('b', 'd')
# ('c', 'd')

c_list = list(itertools.combinations(l, 2))

print(c_list)
# [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]

print(len(c_list))
# 6

Tính tổng số kết hợp trùng lặp

Số tổ hợp trùng lặp là số trường hợp trong đó r được chọn từ n tổ hợp khác nhau, cho phép tạo ra các kết hợp trùng lặp.

Tổng số tổ hợp trùng lặp bằng số tổ hợp để chọn (r) trong số (n + r – 1) tổ hợp khác nhau.

Do đó, chúng ta có thể sử dụng hàm được định nghĩa ở trên để tính tổng số kết hợp.

def combinations_with_replacement_count(n, r):
    return combinations_count(n + r - 1, r)

print(combinations_with_replacement_count(4, 2))
# 10

Trong “scipy.special.comb ()” được mô tả ở trên, tổng số kết hợp trùng lặp có thể thu được bằng cách đặt đối số thứ tư “repeat = True.
Lưu ý rằng đối số “lặp lại” không được triển khai trong “scipy.misc.comb ()” trong các phiên bản trước “SciPy0.14.0”.

from scipy.special import comb

print(comb(4, 2, exact=True, repetition=True))
# 10

Tạo và liệt kê các kết hợp trùng lặp từ một danh sách:itertools.combinations_with_replacement()

Có thể tạo và liệt kê tất cả các kết hợp trùng lặp từ danh sách (mảng), v.v. cũng như tổng số.

Sử dụng hàm links_with_replacement () trong mô-đun itertools.

Truyền một đối số có thể lặp lại (danh sách hoặc loại tập hợp) làm đối số đầu tiên và số phần được chọn làm đối số thứ hai trả về một trình lặp cho kết hợp chồng chéo đó.

h = itertools.combinations_with_replacement(l, 2)

print(type(h))
# <class 'itertools.combinations_with_replacement'>

for v in itertools.combinations_with_replacement(l, 2):
    print(v)
# ('a', 'a')
# ('a', 'b')
# ('a', 'c')
# ('a', 'd')
# ('b', 'b')
# ('b', 'c')
# ('b', 'd')
# ('c', 'c')
# ('c', 'd')
# ('d', 'd')

h_list = list(itertools.combinations_with_replacement(l, 2))

print(h_list)
# [('a', 'a'), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'b'), ('b', 'c'), ('b', 'd'), ('c', 'c'), ('c', 'd'), ('d', 'd')]

print(len(h_list))
# 10

Tạo đảo ngữ từ chuỗi

Itertools.permutations () giúp dễ dàng tạo các hoán vị chuỗi (đảo chữ).

s = 'arc'

for v in itertools.permutations(s):
    print(v)
# ('a', 'r', 'c')
# ('a', 'c', 'r')
# ('r', 'a', 'c')
# ('r', 'c', 'a')
# ('c', 'a', 'r')
# ('c', 'r', 'a')

Để kết hợp một bộ ký tự tại một thời điểm thành một chuỗi và tạo thành một danh sách, hãy làm như sau

anagram_list = [''.join(v) for v in itertools.permutations(s)]

print(anagram_list)
# ['arc', 'acr', 'rac', 'rca', 'car', 'cra']

Phương thức join (), nối các phần tử của một danh sách hoặc bộ vào một chuỗi và ký hiệu hiểu danh sách được sử dụng.