hoán vị với Lặp: Tránh Overflow

Question

Bối cảnh:

Với n quả bóng sao cho:

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

(tất nhiên a + b + c + ... = n)

Số hoán vị, trong đó những quả bóng có thể được sắp xếp được đưa ra bởi:

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

Câu hỏi 1: Làm thế nào tôi có thể 'thanh lịch' tính toán perm để tránh một số nguyên tràn như càng lâu càng tốt, và chắc chắn rằng khi tôi thực hiện tính toán, tôi hoặc là có giá trị chính xác của perm, hoặc tôi biết rằng kết quả cuối cùng sẽ tràn?

Về cơ bản, tôi muốn tránh sử dụng một cái gì đó như GNU GMP.

Tùy chọn, Câu hỏi 2: Đây có phải là thực sự ý tưởng tồi và tôi có nên tiếp tục sử dụng GMP không?

Answer 1

Nếu bạn có thời gian cpu, bạn có thể tạo danh sách trong tất cả giai thừa, sau đó tìm hệ số chính của tất cả các số trong danh sách, sau đó hủy tất cả các số ở trên cùng với các số ở dưới cùng, cho đến các con số được giảm hoàn toàn.

Answer 2

Đây được gọi là hệ số đa thức, mà tôi sẽ biểu thị bằng m(a,b,...).

Và bạn có hiệu quả có thể tính toán cho họ tránh tràn bằng cách khai thác bản sắc này (mà nên khá đơn giản để chứng minh):

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 

Sau đó, nó là một vấn đề đơn giản của việc sử dụng đệ quy để tính toán hệ số. Lưu ý rằng để tránh thời gian chạy theo hàm mũ, bạn cần phải lưu lại kết quả của mình (để tránh tính toán lại) hoặc sử dụng lập trình động.

Để kiểm tra tình trạng tràn, chỉ cần đảm bảo khoản tiền sẽ không tràn.

Và có, đó là một ý tưởng rất xấu khi sử dụng các thư viện chính xác tùy ý để thực hiện tác vụ đơn giản này.

Answer 3

Cách tràn an toàn nhất là cách Dave đề xuất. Bạn tìm thấy số mũ mà Thủ p chia n! bởi tổng

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

Trừ số mũ của p trong factorisations của a! vv Làm mà cho tất cả các số nguyên tố <= n, và bạn có phân tích nhân tử của hệ số đa thức. Tính toán đó sẽ tràn nếu và chỉ khi kết quả cuối cùng tràn. Nhưng các hệ số đa thức phát triển khá nhanh, vì vậy bạn sẽ có tràn cho một số lượng khá nhỏ n. Để tính toán đáng kể, bạn sẽ cần một thư viện bignum (nếu bạn không cần kết quả chính xác, bạn có thể nhận được lâu hơn một chút bằng cách sử dụng double s).

Thậm chí nếu bạn sử dụng một thư viện bignum, nó là đáng giá để giữ kết quả trung gian từ trở nên quá lớn, do đó thay vì tính giai thừa và chia con số khổng lồ, nó là tốt hơn để tính toán các bộ phận trong chuỗi,

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

và để tính toán mỗi một trong các yếu tố này, chúng ta hãy thứ hai mang tính minh họa,

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

được tính với

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

Cuối cùng nhân các phần. Điều này đòi hỏi phải có n phân chia và n + number_of_parts - 1 phép nhân, giữ cho kết quả trung gian vừa phải nhỏ.

Answer 4

Theo this link, bạn có thể tính toán hệ số đa thức như một sản phẩm của một số hệ số nhị thức, kiểm soát tràn số nguyên trên đường.

Điều này làm giảm vấn đề ban đầu đối với tính toán kiểm soát tràn của hệ số nhị thức.

Answer 5

Ký hiệu: n! = prod(1,n) nơi bạn có thể đoán được điều gì.

Nó rất dễ dàng, nhưng trước tiên bạn phải biết rằng đối với bất kỳ 2 số nguyên dương (i, n > 0) rằng biểu thức là một số nguyên dương:

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

Như vậy ý ​​tưởng là để cắt tính toán của n! trong khối nhỏ và phân chia càng sớm càng tốt.

Với a, so với b v.v.

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

Mỗi nhân tố là một số nguyên, vì vậy nếu perm sẽ không tràn, không phải một trong các yếu tố của nó sẽ làm.

Mặc dù, trong tính toán của một yếu tố như vậy có thể là một tràn ở tử số hoặc mẫu số nhưng đó là tránh làm một phép nhân trong tử số sau đó một bộ phận trong alternance:

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

Bằng cách đó mỗi bộ phận sẽ mang lại một số nguyên.