Перестановка с повторением: предотвращение переполнения

Question

Фон:

Дано n шаров, таких что:

'a' balls are of colour GREEN
'b' balls are of colour BLUE
'c' balls are of colour RED
...

(конечно a + b + c + ... = n)

Количество перестановок, в которых эти шары могутупорядочить задается следующим образом:

perm = n! / (a! b! c! ..)

Вопрос 1: Как «элегантно» вычислить perm, чтобы избежать целочисленного переполнения как можно дольше , и быть увереннымчто когда я закончу вычисления, у меня либо будет правильное значение perm, либо я знаю , что окончательный результат будет переполнен?

По сути, я хочу избежать использования чего-то вроде GNUGMP.

Опционально, Вопрос 2: действительно ли это * плохая идея, и я должен просто пойти дальше и использовать GMP?

Answer 1

Они известны как многочленные коэффициенты, которые я обозначу 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

Тогда это простой вопрос использования рекурсии для вычисления коэффициентов. Обратите внимание, что во избежание экспоненциального времени выполнения вам необходимо либо кэшировать свои результаты (чтобы избежать повторного вычисления), либо использовать динамическое программирование.

Чтобы проверить переполнение, просто убедитесь, что суммы не переполнены.

И да, очень плохо использовать библиотеки произвольной точности для выполнения этой простой задачи.

Answer 2

Если у вас есть глобусы процессорного времени, вы можете составить списки из всех факториалов, затем найти простую факторизацию всех чисел в списках, а затем отменить все числа сверху с теми, что внизу, до тех пор, пока цифры полностью уменьшены.

Answer 3

Самый безопасный способ - это способ, который предложил Дейв. Вы найдете показатель, с которым простое число p делит n! на сумму

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

Вычтите показатели p в разложениях a! и т. Д. Сделайте это для всех простых чисел <= n, и вы получите разложение множителя. Это вычисление переполняется тогда и только тогда, когда переполняется окончательный результат. Но мультиномиальные коэффициенты растут довольно быстро, так что у вас будет переполнение уже при довольно малых n. Для существенных вычислений вам понадобится библиотека bignum (если вам не нужны точные результаты, вы можете получить немного больше, используя double s).

Даже если вы используете библиотеку 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 умножений, сохраняя промежуточные результаты умеренно небольшими.

Answer 4

В соответствии с этой ссылкой , вы можете рассчитать полиномиальные коэффициенты как произведение нескольких биномиальных коэффициентов, контролируя целочисленное переполнение в пути.

Это сводит исходную задачу к управляемому переполнением вычислению биномиального коэффициента.

Answer 5

Обозначения: n! = prod(1,n) где prod вы можете догадаться, что делает.

Это очень просто, но сначала вы должны знать, что для любых 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

Таким образом, каждыйделение даст целое число.