Python дээр факториал, сэлгэлт, хослолыг тооцоолох, үүсгэх

Python хэл дээрх математик функцүүдийн математикийн стандарт модулийг хүчин зүйлүүдийг тооцоолоход ашиглаж болно. SciPy нь нийт сэлгэлт/хослолын тоог тооцоолох функцтэй.

itertools модулийг жагсаалтаас (массив) гэх мэтээр солих болон хослол үүсгэж, тэдгээрийг тоолоход ашиглаж болно.

Дараахыг жишээ кодын хамт энд тайлбарлав.

• хүчин зүйл:math.factorial()
• Сэлгээний нийт тоог тооцоол
  • math.factorial()
  • scipy.special.perm()
• Жагсаалтаас сэлгэлт үүсгэж, тоолох:itertools.permutations()
• Нийт хослолын тоог тооцоол
  • math.factorial()
  • scipy.special.comb()
  • math.factorial()-г хэрхэн ашиглахгүй байх вэ
• Жагсаалтаас хослол үүсгэж, тоолох:itertools.combinations()
• Давхардсан хослолуудын нийт тоог тооцоол
• Жагсаалтаас давхардсан хослол үүсгэж, тоолох:itertools.combinations_with_replacement()

Сүлжээ ашиглах жишээ болгон дараахь зүйлийг мөн тайлбарлав.

• Мөрүүдээс анаграмм үүсгэх

Хэрэв та нэг жагсаалтын оронд олон жагсаалтын элементүүдийн хослолыг үүсгэхийг хүсвэл itertools модулийн itertools.product()-г ашиглана уу.

хүчин зүйл:math.factorial()

Математикийн модуль нь факториал () функцийг өгдөг бөгөөд энэ нь факториалыг буцаадаг.

• math.factorial(x) — Mathematical functions — Python 3.10.4 Documentation

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

Бүхэл бус, сөрөг утгууд нь ValueError-д хүргэдэг.

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

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

Сэлгээний нийт тоог тооцоол

math.factorial()

Пермутаци гэдэг нь n өөр зүйлээс r-г сонгож дараалан байрлуулсан тохиолдлын тоо юм.

Сэлгээний нийт тоо p-ийг факториал ашиглан дараах тэгшитгэлээр олно.

p = n! / (n - r)!

Үүнийг факториалыг буцаадаг math.factorial() функцийг ашиглан дараах байдлаар тооцоолж болно. Бүхэл тоо хуваах ⌘ оператор нь бүхэл тооны төрлийг буцаахад ашиглагддаг.

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 нь нийт шилжүүлгийн тоог буцаадаг scipy.special.perm() функцээр хангадаг. Тусдаа SciPy суулгац шаардлагатай. 0.14.0 хувилбараас авах боломжтой.

• scipy.special.perm — SciPy v1.8.0 Reference Guide

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
Гурав дахь аргументыг өгөгдмөлөөр дээрх байдлаар тохируулсан бөгөөд хөвөгч цэгийн тоог буцаана. Хэрэв та бүхэл тоогоор авахыг хүсвэл дараах байдлаар тохируулах хэрэгтэйг анхаарна уу.
exact=True

Зөвхөн “импорт scipy” нь scipy.special модулийг ачаалахгүй гэдгийг анхаарна уу.

Дээрх жишээн дээрх шиг perm()-г “from scipy.special import perm” гэж, эсвэл scipy.special.perm()-г “import scipy.special” гэж ажиллуул.

Жагсаалтаас сэлгэлт үүсгэж, тоолох:itertools.permutations()

Жагсаалтаас (массив) гэх мэтээр зөвхөн нийт тоо төдийгүй сэлгэлтийг үүсгэж, тоолж болно.

itertools модулийн permutations() функцийг ашиглана уу.

• itertools.permutations(iterable, r=None) — Functions creating iterators for efficient looping — Python 3.10.4 Documentation

Эхний аргумент болгон давтагдах боломжтой (жагсаалт эсвэл олонлогийн төрөл) болон хоёр дахь аргумент болгон сонгох хэсгүүдийн тоог дамжуулах нь тухайн сэлгэцийн давталтыг буцаана.

import itertools

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

p = itertools.permutations(l, 2)

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

Тэдгээрийг бүгдийг нь тоолохын тулд та 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')

Энэ нь хязгаарлагдмал давталттай тул list()-ийн тусламжтайгаар жагсаалтын төрөл рүү хөрвүүлэх боломжтой.

Жагсаалтын элементүүдийн тоог len() ашиглан олж авах үед энэ нь факториалаас тооцсон нийт сэлгэцийн тоотой таарч байгааг баталж болно.

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

Хэрэв хоёр дахь аргументыг орхигдуулсан бол бүх элементийг сонгох сэлгэн залгалт буцаана.

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

itertools.permutations() дээр элементүүдийг үнэ цэнэ биш харин байрлалд тулгуурлан авч үздэг. Давхардсан утгыг тооцохгүй.

l = ['a', 'a']

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

Доор тайлбарласан дараах функцүүдэд мөн адил хамаарна.

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

Нийт хослолын тоог тооцоол

math.factorial()

Хослолын тоо нь n өөр хэсгээс сонгох r ширхэгийн тоо юм. Захиалгыг сэлгэн залгалт гэж үзэхгүй.

Нийт c хослолын тоог дараах тэгшитгэлээр олно.

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

Үүнийг факториалыг буцаадаг math.factorial() функцийг ашиглан дараах байдлаар тооцоолж болно. Бүхэл тоо хуваах ⌘ оператор нь бүхэл тооны төрлийг буцаахад ашиглагддаг.

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 нь нийт шилжүүлгийн тоог буцаадаг scipy.special.comb() функцээр хангадаг. Тусдаа SciPy суулгац шаардлагатай. 0.14.0 хувилбараас авах боломжтой. Scipy.misc.comb() нь доор тайлбарласан аргументуудын давталтыг хэрэгжүүлдэггүй гэдгийг анхаарна уу.

• scipy.special.comb — SciPy v1.8.0 Reference Guide
• scipy.misc.comb — SciPy v0.13.0 Reference Guide

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
Scipy.special.perm()-ийн нэгэн адил гурав дахь аргументыг өгөгдмөлөөр дээрх байдлаар тохируулсан бөгөөд хөвөгч цэгийн тоог буцаана. Хэрэв та бүхэл тоогоор авахыг хүсвэл дараах байдлаар тохируулах хэрэгтэйг анхаарна уу.
exact=True
Давхардсан хослолуудын нийт тоог дөрөв дэх аргумент болох давталтаар олж авч болно. Үүнийг доор тайлбарлав.

Зөвхөн “импорт scipy” нь scipy.special модулийг ачаалахгүй гэдгийг дахин анхаарна уу.

Дээрх жишээн дээрх шиг comb()-г “scipy.special import comb” гэж гүйцэтгэх эсвэл scipy.special.comb()-г “import scipy.special” гэж ажиллуул. “scipy.misc”-д мөн адил хамаарна.

math.factorial()-г хэрхэн ашиглахгүй байх вэ

Зөвхөн стандарт номын санг ашигладаг, math.factorial() ашигладаг аргаас хурдан байдаг өөр нэг арга бол дараах арга юм.

• Is there a math nCr function in python? – Stack Overflow

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

Жагсаалтаас хослол үүсгэж, тоолох:itertools.combinations()

Жагсаалт (массив) гэх мэтээс бүх хослолыг үүсгэж, тоолох боломжтой.

itertools модулийн combos() функцийг ашиглана уу.

• itertools.combinations(iterable, r) — Functions creating iterators for efficient looping — Python 3.10.4 Documentation

Эхний аргумент болгон давтагдах боломжтой (жагсаалт эсвэл багц төрөл), хоёр дахь аргумент болгон сонгох хэсгүүдийн тоог дамжуулснаар тухайн хослолын давтагчийг буцаана.

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

Давхардсан хослолуудын нийт тоог тооцоол

Давхардсан хослолын тоо нь r-ийг n өөр нэгээс сонгож, давхардуулах боломжийг олгодог тохиолдлын тоо юм.

Давхардсан хослолын нийт тоо нь (n + r – 1) өөр нэгээс (r) сонгох хослолын тоотой тэнцүү байна.

Тиймээс бид дээр тодорхойлсон функцийг ашиглан нийт хослолын тоог тооцоолж болно.

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

print(combinations_with_replacement_count(4, 2))
# 10

Дээр тайлбарласан “scipy.special.comb()”-д “давталт=Үнэн” гэсэн дөрөв дэх аргументыг тохируулснаар давхардсан хослолын нийт тоог гаргаж болно.
“Дахин давтах” аргумент нь “SciPy0.14.0”-ээс өмнөх хувилбаруудад “scipy.misc.comb()”-д хэрэгжээгүйг анхаарна уу.

from scipy.special import comb

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

Жагсаалтаас давхардсан хослол үүсгэж, тоолох:itertools.combinations_with_replacement()

Жагсаалт (массив) гэх мэтээс давхардсан бүх хослолууд болон нийт тоонуудыг үүсгэж, тоолох боломжтой.

itertools модулийн combines_with_replacement() функцийг ашиглана уу.

• itertools.combinations_with_replacement(iterable, r) — Functions creating iterators for efficient looping — Python 3.10.4 Documentation

Эхний аргумент болгон давтагдах боломжтой (жагсаалт эсвэл багцын төрөл) болон хоёр дахь аргумент болгон сонгох хэсгүүдийн тоог дамжуулах нь давхцаж буй хослолын давталтыг буцаана.

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

Мөрүүдээс анаграмм үүсгэх

Itertools.permutations() нь стринг солих (анаграмм) үүсгэхэд хялбар болгодог.

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')

Нэг тэмдэгтийн багцыг мөр болгон нэгтгэж, жагсаалт болгохын тулд дараах зүйлийг хийнэ үү

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

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

Жагсаалт эсвэл хэлхээний элементүүдийг мөр болгон нэгтгэдэг join() арга ба жагсаалтыг ойлгох тэмдэглэгээг ашигладаг.

• ХОЛБООТОЙ:Python дээр мөрүүдийг холбох (холбох).
• ХОЛБООТОЙ:Python жагсаалтын ойлголтыг хэрхэн ашиглах талаар