StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<blockquote> <p>I need all possible solutions for these groups since it isn't hard to find one constellation.</p> </blockquote> <p>Normally, there 100! ways to permute 100 items, but since you're preserving order, you can reduce your problem size down <em>substantially</em>. What you're describing is an <a href="http://en.wikipedia.org/wiki/Partition_(number_theory)" rel="nofollow noreferrer">integer partitioning problem</a>. For example, let's say you were partitioning the number 5 into all possible integer subsets which add up to 5, you'd get the sets {5}, {4, 1}, {3, 2}, {3, 1, 1,}, {2, 2, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}.</p> <p>The number of integer partitions grows exponentially with the size of the integer, but the exponential growth is slow enough that you can enumerate through all partitions of n = 100, since there are only 190,569,292 of them. The additional constraint here is that you want to filter all of your partitions for sets containing exactly 10 items, which is easy to enumerate through using a Ferrer diagram.</p> <p>I can demonstrate a Ferrer diagram by partition the number 20 into 3 buckets: start with a 20 col x 3 row grid as follows:</p> <pre> 12345678901234567890 1****************** 2* 3* </pre> <p>So, the first partition is {18, 1, 1}</p> <p>Now move an item from the top of the stack into the next slot:</p> <pre> 12345678901234567890 1***************** 2** 3* </pre> <p>Our new partition is {17, 2, 1}. We can another item from one stack to the other:</p> <pre> 12345678901234567890 1**************** 2*** 3* </pre> <p>Now we have {16, 3, 1}. You continue in this fashion until you've enumerate all permutations (its up to you whether {17, 1, 2} is a distinct partition from {17, 2, 1}).</p> <p>From this point, you should be able to envision the general outline of the algorithm you need -- that is, if you'd like the challenge of writing this function from scratch. Other people have already <a href="http://home.att.net/~numericana/answer/numbers.htm#partitions" rel="nofollow noreferrer">written lots of efficient functions</a> to solve the problem easily.</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