Cách hiệu quả để tạo các bảng dự phòng ngẫu nhiên?

Cách hiệu quả để tạo bảng dự phòng ngẫu nhiên là gì? Bảng dự phòng được định nghĩa là ma trận hình chữ nhật sao cho tổng của mỗi hàng được cố định và tổng của mỗi cột được cố định, nhưng các phần tử riêng lẻ có thể là bất cứ điều gì miễn là tổng của mỗi hàng và cột là chính xác.Cách hiệu quả để tạo các bảng dự phòng ngẫu nhiên?

Lưu ý rằng việc tạo các bảng ngẫu nhiên ngẫu nhiên rất dễ dàng, nhưng tôi đang tìm kiếm thứ gì đó hiệu quả hơn thuật toán ngây thơ.

Nguồn

2009-06-04 dsimcha

Nhìn vào mã của gói networksis cho R có thể hữu ích. Tôi tin rằng tính toán hiệu quả đòi hỏi các kỹ thuật ưa thích Markov Chain sequential importance resampling, vì vậy bạn có thể muốn tránh thực hiện lại điều này nếu bạn có thể tránh được nó.

Chỉnh sửa: Giấy liên quan là Chen, Diaconis, Holmes, and Liu (2005). Theo lời của các tác giả, "[o] phương pháp ur so sánh thuận lợi với các thuật toán dựa trên Monte Carlo- hiện có khác, và đôi khi là một vài đơn đặt hàng có cường độ cao hơn."

Nguồn

2009-06-04 06:05:02 othercriteria

Cảm ơn. Đây chính xác là câu trả lời tôi không muốn nghe - điều gì đó cực kỳ phức tạp. Tôi cần biết điều này vì tôi đang làm việc trên một số liệu thống kê mã nguồn mở nhỏ cho ngôn ngữ lập trình D. Biết điều này, tôi đoán tôi sẽ không bao gồm tính năng này. – dsimcha

Bạn có thể tóm tắt thuật toán của bài báo không? Hoặc bao gồm một ví dụ về giải pháp này? – Jon

Điều này nghe có vẻ như là constraint satisfaction problem (CSP) đối với tôi.

Về cơ bản bạn sẽ bắt đầu tại một số điểm và chọn giá trị của ô một cách ngẫu nhiên từ tập hợp các giá trị được phép. Sau đó, bạn cập nhật tập hợp các giá trị đủ điều kiện cho tất cả các ô trong cùng một hàng/cột và chọn ô tiếp theo (theo CSP heuristic bạn đang sử dụng) để (ngẫu nhiên) gán giá trị cho, một lần nữa từ tập hợp các giá trị đủ điều kiện. Một lần nữa, bạn cũng phải cập nhật bộ giá trị đủ điều kiện cho tất cả các ô trong cùng một hàng/cột. Trong trường hợp bạn gặp phải một ô có tập hợp các giá trị đủ điều kiện trống, bạn phải làm ngược lại.

Tuy nhiên, khái niệm 'tập hợp các giá trị đủ điều kiện' có thể khó đại diện trong cấu trúc dữ liệu, tùy thuộc vào phạm vi giá trị bạn đang cho phép.

Nguồn

2009-06-04 05:06:34

Tôi không chắc thuật toán na ï của bạn là gì. Đây là điều đầu tiên tôi nghĩ đến:

$m\cdot n$ biến với $m+n$ hạn chế tuyến tính dẫn đến kỳ vọng rằng không gian giải pháp có $(m-1)\cdot(n-1)-1$ mức độ tự do.

Giả sử chúng tôi chỉ chọn nhiều số ngẫu nhiên để bắt đầu.

 
    a11  a12 ... a1[n-1] b 
    a21  a22 ... a2[n-1] x2-x1+b 
    ...  ... ... ... ... 
a[m-1]1 a[m-1]2 ... d f 
    c y2-y1+c ... g e

Xác định các hằng số $x_i=\sum_{j=1}^{n-1}a_{i,j}$ và $y_j=\sum_{i=1}^{m-1}a_{i,j}$ .

Điều này dẫn đến những hạn chế sau đây về các biến b, c, d, e, f, g:

$x_1+b=\sum_{j=1}^{n-2}a_{m-1,j}+d+f=(m-2)\cdot(c-y_1)+\sum_{\i=1}^{m-2}y_i+g+e$
$y_1+c=\sum_{i=1}^{m-2}a_{j,n-1}+d+g=(n-2)\cdot(c-x_1)+\sum_{j=1}^{n-2}x_j+f+e$

này là một hệ thống tuyến tính gồm 6 biến. Nó có lẽ có một giải pháp duy nhất & hellip; Tôi sẽ làm việc vào ngày mai. (Thiếu Maple hoặc các hệ thống đại số máy tính khác tại thời điểm này.)

Nguồn

2009-06-04 06:02:34 ephemient

Giải pháp cho vấn đề này và được triển khai trong R, là Thuật toán AS159.Đây là giấy

Patefield, W. M. (1981) Thuật toán AS159. Một phương pháp hiệu quả để tạo các bảng r x c với tổng số hàng và cột đã cho. Thống kê ứng dụng 30, 91–97.

Bạn có thể theo dõi link này để triển khai thuật toán. Nếu bạn đang sử dụng để làm việc với R, bạn chỉ có thể sử dụng chức năng r2dtable cho việc này.

Thuật toán này có thể được sử dụng để tạo giá trị p Monte Carlo cho các phép thử Chi bình phương như được tạo trong hàm chisq.test của R. Lưu ý rằng chisq.test không gọi r2dtable, nhưng là trực tiếp phiên bản C của thuật toán AS159.

Nguồn

2017-08-02 19:22:56 Jon

Cách hiệu quả để tạo các bảng dự phòng ngẫu nhiên?

Trả lời

Các vấn đề liên quan