Popular recipes tagged "combinatorics"http://code.activestate.com/recipes/tags/combinatorics/2016-02-21T06:00:46-08:00ActiveState Code Recipespick all combinations of items in buckets (Python)
2015-09-05T07:39:42-07:00yotahttp://code.activestate.com/recipes/users/4184815/http://code.activestate.com/recipes/579098-pick-all-combinations-of-items-in-buckets/
<p style="color: grey">
Python
recipe 579098
by <a href="/recipes/users/4184815/">yota</a>
(<a href="/recipes/tags/combinatorics/">combinatorics</a>).
</p>
<p>Let be a number of buckets, containing each, a variable number of items. This function return all combinations possible of one item picked out of each bucket</p>
<p>example, with three buckets {ba, be, bi}, {ka, ko, ku, ke} and {to, ty}, the function enumerate as such: </p>
<pre class="prettyprint"><code> 0. ba-ka-to
1. ba-ka-ty
2. ba-ko-to
3. ba-ko-ty
4. ba-ku-to
5. ba-ku-ty
6. ba-ke-to
7. ba-ke-ty
8. be-ka-to
9. be-ka-ty
10. be-ko-to
11. be-ko-ty
12. be-ku-to
13. be-ku-ty
14. be-ke-to
15. be-ke-ty
16. bi-ka-to
17. bi-ka-ty
18. bi-ko-to
19. bi-ko-ty
20. bi-ku-to
21. bi-ku-ty
22. bi-ke-to
23. bi-ke-ty
</code></pre>
Get the inversion number of a permutation (Python)
2016-02-21T06:00:46-08:00Samuel James Ericksonhttp://code.activestate.com/recipes/users/4187478/http://code.activestate.com/recipes/579051-get-the-inversion-number-of-a-permutation/
<p style="color: grey">
Python
recipe 579051
by <a href="/recipes/users/4187478/">Samuel James Erickson</a>
(<a href="/recipes/tags/combinatorics/">combinatorics</a>, <a href="/recipes/tags/discrete/">discrete</a>, <a href="/recipes/tags/inversion/">inversion</a>, <a href="/recipes/tags/math/">math</a>, <a href="/recipes/tags/permutations/">permutations</a>).
Revision 2.
</p>
<p>This function takes a permutation in the form of a list and returns the number of inversions in the permutation. </p>
Permutation and combination using recursive generator (Python)
2011-10-04T05:44:19-07:00Shao-chuan Wanghttp://code.activestate.com/recipes/users/4168519/http://code.activestate.com/recipes/577890-permutation-and-combination-using-recursive-genera/
<p style="color: grey">
Python
recipe 577890
by <a href="/recipes/users/4168519/">Shao-chuan Wang</a>
(<a href="/recipes/tags/combinatorics/">combinatorics</a>, <a href="/recipes/tags/generators/">generators</a>, <a href="/recipes/tags/permutation/">permutation</a>, <a href="/recipes/tags/recursion/">recursion</a>).
Revision 2.
</p>
<p>This recipes demonstrates how to use recursive generator to implement permutation and combination.</p>
Generate the partitions of a set, by index (Python)
2010-04-30T11:07:30-07:00Anton Vredegoorhttp://code.activestate.com/recipes/users/2667360/http://code.activestate.com/recipes/577211-generate-the-partitions-of-a-set-by-index/
<p style="color: grey">
Python
recipe 577211
by <a href="/recipes/users/2667360/">Anton Vredegoor</a>
(<a href="/recipes/tags/combinatorics/">combinatorics</a>, <a href="/recipes/tags/partition/">partition</a>).
</p>
<p>Sets of only a few items already have many ways they can be partitioned into subsets. Therefore it can be useful to generate these partitions by index, like the partition class were some large list where one can just access element "i". Of course one should not compute the whole list in advance but compute the partitions on the fly. This recipe was originally extracted form a book by Kreher and Stinson. Over the years I came back to my code from time to time creating a new and hopefully more pythonic version each time I understood it better. My current take on it is that the algorithm looks a lot like creating a Pascals triangle in order to compute combinations. One just tries to find a way down the triangle to a specific element, each time subtracting the amounts the different positions in the triangle account for. It is also similar to finding indexed permutations of a set with elements occurring more than once. One of these days I will perhaps understand how all of this fits together. Until then I'll post code solving specific situations. </p>