Tạo tất cả các kết quả có thể có của quả bóng k trong n thùng (tổng các kết quả đa thức/phân loại)

Question

Giả sử chúng ta có các thùng n trong đó chúng tôi đang ném k quả bóng. nhanh (tức là sử dụng mã numpy/scipy thay vì mã python) để tạo ra tất cả các kết quả có thể có như ma trận là gì?

Ví dụ, nếu n = 4 và k = 3, chúng tôi muốn sau numpy.array:

3 0 0 0 
2 1 0 0 
2 0 1 0 
2 0 0 1 
1 2 0 0 
1 1 1 0 
1 1 0 1 
1 0 2 0 
1 0 1 1 
1 0 0 2 
0 3 0 0 
0 2 1 0 
0 2 0 1 
0 1 2 0 
0 1 1 1 
0 1 0 2 
0 0 3 0 
0 0 2 1 
0 0 1 2 
0 0 0 3 

Xin lỗi nếu có hoán vị được bỏ qua, nhưng đây là ý tưởng chung. Các hoán vị được tạo ra không cần phải theo bất kỳ thứ tự cụ thể nào, nhưng danh sách trên đã thuận tiện cho việc phân loại lặp đi lặp lại thông qua chúng một cách tinh thần.

Tốt hơn, có cách nào để ánh xạ mọi số nguyên từ 1 đến multiset number (danh mục của danh sách này) trực tiếp đến một hoán vị nhất định không?

Câu hỏi này có liên quan đến những người sau đây, được thực hiện trong R với cơ sở vật chất rất khác nhau:

• Generating all permutations of N balls in M bins
• Generate a matrix of all possible outcomes for throwing n dice (ignoring order)

tài liệu tham khảo Cũng liên quan:

• https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
• https://en.wikipedia.org/wiki/Multiset#Counting_multisets
• https://en.wikipedia.org/wiki/Combinatorial_number_system

Answer 1

Dưới đây là một giải pháp máy phát điện sử dụng itertools.combinations_with_replacement, không biết nếu nó sẽ phù hợp với nhu cầu của bạn.

def partitions(n, b): 
    masks = numpy.identity(b, dtype=int) 
    for c in itertools.combinations_with_replacement(masks, n): 
     yield sum(c) 

output = numpy.array(list(partitions(3, 4))) 
# [[3 0 0 0] 
# [2 1 0 0] 
# ... 
# [0 0 1 2] 
# [0 0 0 3]] 

Độ phức tạp của hàm này tăng theo cấp số nhân, do đó có ranh giới rời rạc giữa những gì khả thi và cái gì không.

Lưu ý rằng trong khi mảng numpy cần phải biết kích thước của chúng khi xây dựng, điều này có thể dễ dàng thực hiện được vì số nhiều lần được tìm thấy dễ dàng. Bên dưới có thể là một phương pháp tốt hơn, tôi đã không thực hiện bất kỳ thời gian nào.

from math import factorial as fact 
from itertools import combinations_with_replacement as cwr 

nCr = lambda n, r: fact(n)/fact(n-r)/fact(r) 

def partitions(n, b): 
    partition_array = numpy.empty((nCr(n+b-1, b-1), b), dtype=int) 
    masks = numpy.identity(b, dtype=int) 
    for i, c in enumerate(cwr(masks, n)): 
     partition_array[i,:] = sum(c) 
    return partition_array 

Answer 2

đây là một việc thực hiện ngây thơ với comprehensions danh sách, không chắc chắn về hiệu suất so với NumPy

def gen(n,k): 
    if(k==1): 
     return [[n]] 
    if(n==0): 
     return [[0]*k] 
    return [ g2 for x in range(n+1) for g2 in [ u+[n-x] for u in gen(x,k-1) ] ] 

> gen(3,4) 
[[0, 0, 0, 3], 
[0, 0, 1, 2], 
[0, 1, 0, 2], 
[1, 0, 0, 2], 
[0, 0, 2, 1], 
[0, 1, 1, 1], 
[1, 0, 1, 1], 
[0, 2, 0, 1], 
[1, 1, 0, 1], 
[2, 0, 0, 1], 
[0, 0, 3, 0], 
[0, 1, 2, 0], 
[1, 0, 2, 0], 
[0, 2, 1, 0], 
[1, 1, 1, 0], 
[2, 0, 1, 0], 
[0, 3, 0, 0], 
[1, 2, 0, 0], 
[2, 1, 0, 0], 
[3, 0, 0, 0]] 

Answer 3

Đối với mục đích tham khảo, các mã sau đây sử dụng Ehrlich's algorithm để lặp qua tất cả các kết hợp có thể có của một MultiSet trong C++ , Javascript, và Python:

https://github.com/ekg/multichoose

Điều này có thể được chuyển đổi sang định dạng trên bằng cách sử dụng this method.Cụ thể,

for s in multichoose(k, set): 
    row = np.bincount(s, minlength=len(set) + 1) 

này vẫn không phải là NumPy tinh khiết, nhưng có thể được sử dụng để điền vào một preallocated numpy.array khá nhanh chóng.

Answer 4

Đây là giải pháp tôi đã đưa ra cho điều này.

import numpy, itertools 
def multinomial_combinations(n, k, max_power=None): 
    """returns a list (2d numpy array) of all length k sequences of 
    non-negative integers n1, ..., nk such that n1 + ... + nk = n.""" 
    bar_placements = itertools.combinations(range(1, n+k), k-1) 
    tmp = [(0,) + x + (n+k,) for x in bar_placements] 
    sequences = numpy.diff(tmp) - 1 
    if max_power: 
     return sequences[numpy.where((sequences<=max_power).all(axis=1))][::-1] 
    else: 
     return sequences[::-1] 

Lưu ý 1: [:: - 1] ở cuối chỉ đảo ngược thứ tự để khớp với kết quả ví dụ của bạn.

Lưu ý 2: Tìm các trình tự này tương đương với việc tìm mọi cách sắp xếp n sao và k-1 thanh (để điền các vị trí n + k-1) (xem stars and bars thm 2).

Lưu ý 3: Đối số max_power là cung cấp cho bạn tùy chọn chỉ trả về các chuỗi trong đó tất cả các số nguyên dưới mức tối đa.