Пермутация с повторение: избягване на преливане

Ако имате много процесорно време, можете да направите списъци от всички факториели, след това да намерите разлагането на прости множители на всички числа в списъците, след това да съкратите всички числа отгоре с тези отдолу, докато числата са напълно намалена.

Те са известни като мултиномиални коефициенти, които ще обознача с m(a,b,...).

И вие можете ефективно да ги изчислите, като избягвате препълване, като използвате тази идентичност (която трябва да е доста проста за доказване):

m(a,b,c,...) = m(a-1,b,c,...) + m(a,b-1,c,...) + m(a,b,c-1,...) + ...
m(0,0,0,...) = 1 // base case
m(anything negative) = 0 // base case 2

След това е прост въпрос на използване на рекурсия за изчисляване на коефициентите. Имайте предвид, че за да избегнете експоненциално време на изпълнение, трябва или да кеширате резултатите си (за да избегнете повторно изчисляване), или да използвате динамично програмиране.

За да проверите за препълване, просто се уверете, че сумите няма да препълнят.

И да, много лоша идея е да се използват библиотеки с произволна точност, за да се извърши тази проста задача.

Най-безопасният от преливане начин е начинът, по който Дейв предложи. Намирате степента, с която простото p дели n! на сумата

m = n;
e = 0;
do{
    m /= p;
    e += m;
}while(m > 0);

Извадете показателите на p в факторизациите на a! и т.н. Направете това за всички прости числа <= n и ще получите факторизацията на мултиномиалния коефициент. Това изчисление препълва, ако и само ако крайният резултат препълва. Но мултиномиалните коефициенти растат доста бързо, така че вече ще имате препълване за сравнително малко n. За съществени изчисления ще ви трябва библиотека bignum (ако не се нуждаете от точни резултати, можете да изкарате малко по-дълго, като използвате doubles).

Дори ако използвате библиотека bignum, струва си междинните резултати да не станат твърде големи, така че вместо да изчислявате факториелите и да разделяте огромни числа, е по-добре да изчислявате частите последователно,

n!/(a! * b! * c! * ...) = n! / (a! * (n-a)!) * (n-a)! / (b! * (n-a-b)!) * ...

и за да изчислим всеки от тези фактори, нека вземем втория за илюстрация,

(n-a)! / (b! * (n-a-b)!) = \prod_{i = 1}^b (n-a+1-i)/i

се изчислява с

prod = 1
for i = 1 to b
    prod = prod * (n-a+1-i)
    prod = prod / i

Накрая умножете частите. Това изисква n деления и n + number_of_parts - 1 умножения, запазвайки междинните резултати умерено малки.

Според тази връзка можете да изчислите многочленните коефициенти като произведение на няколко биномни коефициента, контролирайки целочислено препълване по пътя.

Това намалява първоначалния проблем до контролирано от препълване изчисляване на биномен коефициент.

Нотации: n! = prod(1,n) където продукт можете да познаете какво прави.

Много е лесно, но първо трябва да знаете, че за всеки 2 положителни числа (i, n > 0) този израз е положително цяло число:

prod(i,i+n-1)/prod(1,n)

По този начин идеята е изчислението на n! да се раздели на малки парчета и да се раздели възможно най-скоро.

С a, отколкото с b и т.н.

perm = (a!/a!) * (prod(a+1, a+b)/b!) * ... * (prod(a+b+c+...y+1,n)/z!)

Всеки от тези фактори е цяло число, така че ако perm няма да препълни, нито един от неговите фактори няма да свърши работа.

Въпреки това, при изчисляването на такъв коефициент може да има преливане в числителя или знаменателя, но това може да се избегне, като се направи умножение в числителя и след това деление в редуване:

prod(a+1, a+b)/b! = (a+1)(a+2)/2*(a+3)/3*..*(a+b)/b

По този начин всяко деление ще даде цяло число.