Tính toán xếp hạng kết hợp?

Question

Tôi muốn tính toán trước một số giá trị cho từng kết hợp trong một tập hợp các kết hợp. Ví dụ, khi lựa chọn 3 số 0-12, tôi sẽ tính toán một số giá trị cho mỗi một:

>>> for n in choose(range(13), 3): 
    print n, foo(n) 

(0, 1, 2) 78 
(0, 1, 3) 4 
(0, 1, 4) 64 
(0, 1, 5) 33 
(0, 1, 6) 20 
(0, 1, 7) 64 
(0, 1, 8) 13 
(0, 1, 9) 24 
(0, 1, 10) 85 
(0, 1, 11) 13 
etc... 

Tôi muốn để lưu trữ các giá trị trong một mảng để cho sự kết hợp, tôi có thể tính toán của mình và nhận được giá trị. Ví dụ:

>>> a = [78, 4, 64, 33] 
>>> a[magic((0,1,2))] 
78 

Điều gì sẽ magic?

Ban đầu tôi nghĩ chỉ lưu trữ dưới dạng ma trận 3 chiều có kích thước 13 x 13 x 13, vì vậy tôi có thể dễ dàng lập chỉ mục theo cách đó. Trong khi điều này là tốt cho 13 chọn 3, điều này sẽ có cách quá nhiều chi phí cho một cái gì đó như 13 chọn 7.

Tôi không muốn sử dụng một dict vì cuối cùng mã này sẽ được trong C, và một mảng sẽ được hiệu quả hơn nhiều.

CẬP NHẬT: Tôi cũng có vấn đề tương tự, nhưng sử dụng kết hợp với lặp lại, vì vậy bất kỳ câu trả lời nào về cách xếp hạng thứ hạng sẽ được đánh giá cao =).

CẬP NHẬT: Để làm rõ, tôi đang cố gắng tiết kiệm không gian. Mỗi kết hợp này thực sự lập chỉ mục vào một thứ chiếm nhiều không gian, giả sử 2 kilobyte. Nếu tôi sử dụng một mảng 13x13x13, đó sẽ là 4 megabyte, trong đó tôi chỉ cần 572 kilobyte sử dụng (13 chọn 3) điểm.

Answer 1

Dưới đây là câu trả lời khái niệm và mã dựa trên cách thức hoạt động của lệnh lex. (Vì vậy, tôi đoán câu trả lời của tôi giống như "moron", ngoại trừ việc tôi nghĩ rằng anh ấy có quá ít chi tiết và liên kết của anh ấy quá nhiều.) Tôi đã viết một hàm unchoose(n,S) cho bạn range(n). Ý tưởng: Hoặc S chứa 0 hoặc không. Nếu có, hãy xóa 0 và tính chỉ mục cho tập con còn lại. Nếu không, sau đó nó đưa ra sau khi binomial(n-1,k-1) tập con nào chứa 0.

def binomial(n,k): 
    if n < 0 or k < 0 or k > n: return 0 
    b = 1 
    for i in xrange(k): b = b*(n-i)/(i+1) 
    return b 

def unchoose(n,S): 
    k = len(S) 
    if k == 0 or k == n: return 0 
    j = S[0] 
    if k == 1: return j 
    S = [x-1 for x in S] 
    if not j: return unchoose(n-1,S[1:]) 
    return binomial(n-1,k-1)+unchoose(n-1,S) 

def choose(X,k): 
    n = len(X) 
    if k < 0 or k > n: return [] 
    if not k: return [[]] 
    if k == n: return [X] 
    return [X[:1] + S for S in choose(X[1:],k-1)] + choose(X[1:],k) 

(n,k) = (13,3) 
for S in choose(range(n),k): print unchoose(n,S),S 

Bây giờ, nó cũng là sự thật mà bạn có thể cache hoặc các giá trị hash của cả hai chức năng, nhị thức và unchoose. Và điều tốt đẹp về điều này là bạn có thể thỏa hiệp giữa tất cả mọi thứ và precomputing precomputing không có gì. Ví dụ: bạn chỉ có thể tính toán trước cho len(S) <= 3.

Bạn cũng có thể tối ưu hóa bỏ chọn để nó thêm các hệ số nhị thức với vòng lặp nếu S[0] > 0, thay vì giảm và sử dụng đệ quy đuôi.

Answer 2

Bạn có thể thử sử dụng chỉ mục từ điển của tổ hợp. Có thể trang này sẽ giúp: http://saliu.com/bbs/messages/348.html

Trang MSDN này có thêm chi tiết: Generating the mth Lexicographical Element of a Mathematical Combination.

Để cụ thể hơn một chút:

Khi được coi như một bộ, bạn có thể đặt các kết hợp theo từ điển.

Vì vậy, (0,1,2) < (0,1,3) < (0,1,4), vv

Giả sử bạn đã có số từ 0 đến n-1 và chọn k ra khỏi những .

Bây giờ nếu phần tử đầu tiên bằng không, bạn biết rằng nó là một trong số n-1 đầu tiên chọn k-1.

Nếu phần tử đầu tiên là 1, thì đó là một trong số các phần tử tiếp theo n-2 chọn k-1.

Bằng cách này bạn có thể tính toán đệ quy vị trí chính xác của kết hợp đã cho trong thứ tự từ điển và sử dụng để ánh xạ nó với số của bạn.

Điều này hoạt động ngược lại và trang MSDN giải thích cách thực hiện điều đó.

Answer 3

Sử dụng bảng băm để lưu trữ kết quả. Một hàm băm phong nha có thể là một cái gì đó như:

h(x) = (x1*p^(k - 1) + x2*p^(k - 2) + ... + xk*p^0) % pp

đâu x1 ... xk là những con số trong sự kết hợp của bạn (ví dụ (0, 1, 2) có x1 = 0, x2 = 1, x3 = 2) và p và pp là số nguyên tố.

Vì vậy, bạn sẽ lưu trữ Hash[h(0, 1, 2)] = 78 và sau đó bạn sẽ truy xuất nó theo cùng một cách.

Lưu ý: bảng băm chỉ là một mảng có kích thước pp, không phải là dict.

Answer 4

Tôi sẽ đề xuất một bảng băm chuyên dụng. Hàm băm cho một kết hợp phải là độc quyền hoặc của các băm cho các giá trị. Dấu gạch ngang cho các giá trị về cơ bản là các mẫu bit ngẫu nhiên.

Bạn có thể mã bảng để đối phó với các va chạm, nhưng sẽ khá dễ dàng để lấy được lược đồ băm hoàn hảo tối thiểu - một nơi không có hai kết hợp ba mục cho cùng giá trị băm và vị trí của bảng băm và bảng -size được giữ ở mức tối thiểu.

Điều này về cơ bản là Zobrist hashing - hãy nghĩ đến việc "di chuyển" khi thêm hoặc xóa một mục của kết hợp.

EDIT

Lý do để sử dụng một bảng băm là O thực hiện tra cứu (n) trong đó n là số mục trong sự kết hợp (giả sử không có va chạm). Tính toán các chỉ mục từ điển vào các kết hợp chậm hơn đáng kể, IIRC.

Nhược điểm rõ ràng là công việc tiên tiến được thực hiện để tạo bảng.

Answer 5

Hiện tại, tôi đã thỏa hiệp: Tôi có một mảng 13x13x13 chỉ ánh xạ tới chỉ số của kết hợp, chiếm 13x13x13x2 byte = 4 kilobyte (sử dụng ints ngắn) cộng với kích thước bình thường (13 chọn 3) * 2 kilobyte = 572 kilobyte, tổng cộng 576 kilobyte. Tốt hơn 4 megabyte, và cũng nhanh hơn tính toán xếp hạng!

Tôi đã làm điều này một phần khiến tôi không thể có được câu trả lời của Moron để làm việc. Điều này cũng có thể mở rộng hơn - tôi có một trường hợp mà tôi cần sự kết hợp với sự lặp lại, và tôi chưa tìm ra cách tính toán thứ hạng của những thứ đó.

Answer 6

Điều bạn muốn được gọi là combinadics.Dưới đây là thực hiện của tôi về khái niệm này, bằng Python:

def nthresh(k, idx): 
    """Finds the largest value m such that C(m, k) <= idx.""" 
    mk = k 
    while ncombs(mk, k) <= idx: 
    mk += 1 
    return mk - 1 


def idx_to_set(k, idx): 
    ret = [] 
    for i in range(k, 0, -1): 
    element = nthresh(i, idx) 
    ret.append(element) 
    idx -= ncombs(element, i) 
    return ret 


def set_to_idx(input): 
    ret = 0 
    for k, ck in enumerate(sorted(input)): 
    ret += ncombs(ck, k + 1) 
    return ret 

Answer 7

Tôi đã viết một lớp học để xử lý các chức năng phổ biến để làm việc với các hệ số nhị thức, đó là loại vấn đề mà vấn đề của bạn thuộc. Nó thực hiện các tác vụ sau:

1. Xuất tất cả chỉ mục K ở định dạng đẹp cho bất kỳ N nào chọn K thành tệp. Chỉ số K có thể được thay thế bằng nhiều chuỗi hoặc chữ mô tả hơn. Phương pháp này giúp giải quyết loại vấn đề này khá tầm thường.

2. Chuyển đổi chỉ mục K thành chỉ mục thích hợp của mục nhập trong bảng hệ số nhị thức được sắp xếp. Kỹ thuật này nhanh hơn nhiều so với các kỹ thuật cũ được công bố dựa trên sự lặp lại và nó không sử dụng nhiều bộ nhớ. Nó thực hiện điều này bằng cách sử dụng một thuộc tính toán học vốn có trong Tam giác của Pascal. Bài báo của tôi nói về điều này. Tôi tin rằng tôi là người đầu tiên khám phá và xuất bản kỹ thuật này, nhưng tôi có thể sai.

3. Chuyển đổi chỉ mục trong bảng hệ số nhị thức đã sắp xếp thành chỉ mục K tương ứng.

4. Sử dụng phương pháp Mark Dominus để tính hệ số nhị thức, ít có khả năng tràn và hoạt động với số lớn hơn.

5. Lớp học được viết bằng .NET C# và cung cấp cách quản lý các đối tượng liên quan đến sự cố (nếu có) bằng cách sử dụng danh sách chung. Hàm khởi tạo của lớp này nhận giá trị bool được gọi là InitTable, khi đúng sẽ tạo một danh sách chung để giữ các đối tượng được quản lý. Nếu giá trị này là sai, thì nó sẽ không tạo bảng. Bảng không cần phải được tạo ra để thực hiện 4 phương pháp trên. Các phương thức Accessor được cung cấp để truy cập vào bảng.

6. Có một lớp thử nghiệm được liên kết hiển thị cách sử dụng lớp và các phương pháp của lớp. Nó đã được thử nghiệm rộng rãi với 2 trường hợp và không có lỗi nào được biết đến.

Để đọc về lớp này và tải xuống mã, hãy xem Tablizing The Binomial Coeffieicent.

Không khó để chuyển đổi lớp này thành C++.