Di Python de faktorîal, permutasyon û kombînasyonan hesab bikin û biafirînin

Dikan

Matematîka modula standard ji bo fonksiyonên matematîkî yên li Python dikare ji bo hesabkirina faktoran were bikar anîn. SciPy di ​​heman demê de fonksiyonên xwe jî hene ku jimara giştî ya guheztinan / berhevokan hesab dike.

Modula itertools di heman demê de dikare were bikar anîn da ku ji navnîşan (array) û hwd veguheztin û berhevokan çêbike û wan bihejmêre.

Ya jêrîn li vir, digel koda nimûneyê, tê rave kirin.

  • faktorî:math.factorial()
  • Bihejmêre hejmara giştî ya permutations
    • math.factorial()
    • scipy.special.perm()
  • Ji navnîşek guheztinan biafirînin û bijmêrin:itertools.permutations()
  • Bihejmêre hejmara giştî ya combinations
    • math.factorial()
    • scipy.special.comb()
    • Meriv çawa math.factorial bikar nayîne()
  • Ji navnîşan berhevokan biafirînin û bijmêrin:itertools.combinations()
  • Bihejmêre hejmara giştî ya kombînasyona dubare
  • Ji navnîşek berhevokên dubare biafirînin û bijmêrin:itertools.combinations_with_replacement()

Wekî mînakek karanîna permutasyonan, jêrîn jî tê ravekirin.

  • Ji têlan anagraman çêbikin

Heke hûn dixwazin li şûna navnîşek yekane hevokek hêmanên pir navnîşan çêbikin, di modula itertools de itertools.product() bikar bînin.

faktorî:math.factorial()

Modula matematîkê fonksiyonek faktorîal() peyda dike ku faktoriyê vedigerîne.

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

Nirxên ne-tevjimar, neyînî dê bibe sedema ValueError.

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

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

Bihejmêre hejmara giştî ya permutations

math.factorial()

Permutasyon hejmara haletan in ku r ji n cuda têne hilbijartin û li rêzê têne danîn.

Tevahiya hejmara permutations, p, bi hevkêşana jêrîn bi bikaranîna faktorîlan tê bidestxistin.

p = n! / (n - r)!

Ew dikare wekî jêrîn bi karanîna fonksiyona math.factorial(), ku faktoriyê vedigerîne, were hesibandin. Operatora ⌘, ku dabeşkirina jimarê pêk tîne, ji bo vegerandina tîpek jimarek tê bikar anî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 fonksiyonek scipy.special.perm() peyda dike ku jimara giştî ya guheztinan vedigerîne. Sazkirinek SciPy ya cihê hewce ye. Ji guhertoya 0.14.0 peyda dibe.

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
Argumana sêyemîn ji hêla xwerû ve wekî li jor hatî destnîşan kirin û jimareyek xala herikandinê vedigerîne. Bala xwe bidinê ku heke hûn dixwazin wê wekî jimareyek tevahî bistînin, hûn hewce ne ku wê wekî jêrîn saz bikin.
exact=True

Bala xwe bidinê ku tenê “import scipy” dê modula scipy.special bar neke.

Perm() wekî “ji scipy.special import perm” wekî di mînaka jorîn de bimeşîne, an jî scipy.special.perm() wekî “import scipy.special” bixebitîne.

Ji navnîşek guheztinan biafirînin û bijmêrin:itertools.permutations()

Ne tenê hejmarên tevahî, lê di heman demê de veguheztin jî dikarin ji navnîşan (array) û hwd werin çêkirin û jimartin.

Fonksiyona permutations() ya modula itertools bikar bînin.

Derbaskirina îterable (lîste an celebek sazkirî) wekî argumana yekem û hejmara perçeyên ku wekî argumana duyemîn têne hilbijartin, ji bo wê veguheztinê îteratorek vedigerîne.

import itertools

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

p = itertools.permutations(l, 2)

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

Ji bo jimartina wan hemûyan, hûn dikarin lekeyek for bikar bînin.

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

Ji ber ku ew îteratorek bêdawî ye, ew dikare bi list() re jî bibe celebek navnîşê were veguheztin.

Dema ku jimara hêmanên di lîsteyê de bi len(-ê) were bidestxistin, meriv dikare were piştrast kirin ku ew bi tevahî hejmarên veguheztinê yên ku ji faktorê têne hesibandin re têkildar e.

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

Ger argumana duyemîn ji holê were rakirin, veguheztina ji bo hilbijartina hemî hêmanan tê vegerandin.

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

Li itertools.permutations(), hêman li gorî pozîsyonê têne derman kirin, ne nirx. Nirxên dubare nayên hesibandin.

l = ['a', 'a']

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

Heman tişt ji bo fonksiyonên jêrîn, ku li jêr têne diyar kirin, derbas dibe.

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

Bihejmêre hejmara giştî ya combinations

math.factorial()

Hejmara berhevokan hejmara r perçeyên ku ji n perçeyên cûda hilbijêrin ye. Rêz wekî di guheztinan de nayê hesibandin.

Hejmara tevheviya c bi hevkêşana jêrîn tê wergirtin.

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

Ew dikare wekî jêrîn bi karanîna fonksiyona math.factorial(), ku faktoriyê vedigerîne, were hesibandin. Operatora ⌘, ku dabeşkirina jimarê pêk tîne, ji bo vegerandina tîpek jimarek tê bikar anî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 fonksiyonek scipy.special.comb() peyda dike ku jimara giştî ya guheztinan vedigerîne. Sazkirinek SciPy ya cihê hewce ye. Ji guhertoya 0.14.0 peyda dibe. Bala xwe bidinê ku scipy.misc.comb() dubarekirina argumana ku li jêr hatî destnîşan kirin bicîh nayîne.

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
Mîna scipy.special.perm(), argumana sêyem wekî li jor ji hêla xwerû ve hatî danîn û jimareyek xala hêlînê vedigerîne. Bala xwe bidinê ku heke hûn dixwazin wê wekî jimareyek tevahî bistînin, hûn hewce ne ku wê wekî jêrîn saz bikin.
exact=True
Bi argumana çaremîn, dubarekirinê, jimareya giştî ya berhevokên dubare jî dikare were bidestxistin. Ev li jêr hatiye diyarkirin.

Dîsa, bala xwe bidin ku tenê “scipy import” dê modula scipy.special bar neke.

Mîna di mînaka jorîn de, comb() wekî “ji scipy.special import comb” an jî scipy.special.comb() wekî “import scipy.special” bi kar bîne. Heman tişt ji bo “scipy.misc” jî derbas dibe.

Meriv çawa math.factorial bikar nayîne()

Rêbazek din a ku tenê pirtûkxaneya standard bikar tîne û ji rêbaza ku math.factorial() bikar tîne zûtir e, rêbaza jêrîn e.

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

Ji navnîşan berhevokan biafirînin û bijmêrin:itertools.combinations()

Mimkun e ku hemî berhevokên ji navnîşan (array) û hwd û hem jî hejmarên giştî bêne çêkirin û hejmartin.

Fonksiyona berhevokan() ya modula itertools bikar bînin.

Derbaskirina îterable (lîste an celebek sazkirî) wekî argumana yekem û hejmara perçeyên ku wekî argumana duyemîn têne hilbijartin, îteratorê ji bo wê berhevokê vedigerîne.

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

Bihejmêre hejmara giştî ya kombînasyona dubare

Hejmara berhevokên ducarî hejmara bûyeran e ku tê de r ji n cûda têne hilbijartin, ku destûrê dide dubareyan.

Hejmara giştî ya hevberdanên dubare bi hejmara berhevokên ku ji nav (n + r – 1) yên cûda hilbijêrin (r) wekhev e.

Ji ber vê yekê, em dikarin fonksiyona ku li jor hatî destnîşan kirin bikar bînin da ku jimara giştî ya berhevokan hesab bikin.

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

print(combinations_with_replacement_count(4, 2))
# 10

Di “scipy.special.comb()” de, ku li jor hatî behs kirin, bi danîna argumana çaremîn “repetition=True” jimareya giştî ya berhevokên dubare dikare were bidestxistin.
Bala xwe bidinê ku argumana “dubarekirin” di “scipy.misc.comb()” de di versiyonên berî “SciPy0.14.0” de nayê bicîh kirin.

from scipy.special import comb

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

Ji navnîşek berhevokên dubare biafirînin û bijmêrin:itertools.combinations_with_replacement()

Mimkun e ku hemî berhevokên dubare yên ji navnîşan (array) û hwd û hem jî hejmarên giştî werin çêkirin û hejmartin.

Di modula itertools de fonksiyona combinations_with_replacement() bikar bînin.

Derbaskirina îterable (lîste an celebek sazkirî) wekî argumana yekem û hejmara perçeyên ku wekî argumana duyemîn têne hilbijartin, îteratorek ji bo wê kombînasyona hevgirtî vedigerîne.

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

Ji têlan anagraman çêbikin

Itertools.permutations() çêkirina permutasyonên rêzê (anagram) hêsan dike.

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

Ji bo ku yek carek tîpek karakterek di nav rêzek de bicivînin û wê bikin navnîşek, jêrîn bikin

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

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

Rêbaza join() ya ku hêmanên lîsteyek an pirtikan di nav rêzekê de vedihewîne, û nîşana têgihîştina navnîşê tê bikar anîn.