StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I am not a C# expert so I will give you a purely mathematical solution, and hopefully you will be able to translate it in your language.</p> <p>Basically your task consists of two separate parts: choose b groups i to j elements each, and randomness. The second should be easy - just random shuffle the elements initially and then do the group splitting. Lets get down to the interesting part:</p> <p>How to split n elements in <code>b</code> groups containing <code>i</code> to <code>j</code> elements each? A straight forward solution will be to take random number between <code>i</code>and <code>j</code> for the number of elements of the first group, then the second etc. However, there will be no guarantee, that doing so you will not be left with the last group having element number not between <code>i</code> and <code>j</code>. Also such solution is not doing pure random distribution.</p> <p>The correct approach will be to get the number of elements of the first group, respecting the probability of solution of the overall group splitting when you take as many elements - you basically are interested how many solutions are overall for the <code>task(n, b, i, j)</code> and how many will exist for the <code>task(n-k, b-1, i, j)</code> if we assume we take <code>k</code> elements in the first group. If we are able to calculate just the number of solutions, you can take each k with its respective probability and do random sampling of k for the first group, then the second and so on...</p> <p>So now the question is: how many solutions are there for <code>task(n, b, i, j)</code>? Noting the fact that <code>task(n, b, i, j) = sum(k=i to j) task(n-k, b - 1, i, j)</code> you can find these numbers easily using recursion (use dynamic optimization, so that you need not calculate the values more than once).</p> <p>PS: There might be a closed form solution for the number of solutions, but I can't figure it out right away and as long as <code>n * b</code> is kept relatively small (< 10^6) recursive solution should work.</p> <p><strong>EDIT</strong><br/> PS2: actually the numbers in <code>task(n, b, i, j)</code> might get pretty large very fast, so consider using big integers.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload