tag:blogger.com,1999:blog-1806360094658697411.post579732869948510119..comments2022-12-04T08:59:01.682-05:00Comments on The Lowly Programmer: Indexing and enumerating subsets of a given sizeEric Burnetthttp://www.blogger.com/profile/10741882872804697111noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-1806360094658697411.post-25156691338433371602012-08-07T18:21:20.607-04:002012-08-07T18:21:20.607-04:00Thanks very much for this - I was running into per...Thanks very much for this - I was running into performance issues with trying to generate large Kneser's graphs due to the requirement for enumerating subsets - this has sped up it up massively.<br /><br />I ported it to PHP and added an "all" method - seems to be running very fast! It's listed at http://richardlyon.co.uk/enum.php - feel free to add it to the github repo if you want!Richard Lyonnoreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-73548872975830545382012-01-15T00:48:18.178-05:002012-01-15T00:48:18.178-05:00Sorry for the long delay Corin, and thanks for the...Sorry for the long delay Corin, and thanks for the code! I've added it to the post :).Eric Burnetthttps://www.blogger.com/profile/10741882872804697111noreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-71452446103370107742011-12-20T05:25:53.334-05:002011-12-20T05:25:53.334-05:00Great article! Here's my implementation in C (...Great article! Here's my implementation in C (sorry, no big int):<br />unsigned int compute (unsigned int n, unsigned int k, unsigned int i){ unsigned int binom, b = 0; do { if (i == 0 || (binom = choose(n - 1, k - 1)) > i) k--, b |= 1; else i -= binom; b <<= 1; } while (--n && k && ((b <<= 1) || 1)); b <<= n; return b;}<br /><br />Complete code here: https://github.com/au-phiware/bankers<br />I also have an implementation that doesn't use nCk (but it's not as efficient).Corin Lawsonnoreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-39185465506596748512011-02-01T21:43:14.419-05:002011-02-01T21:43:14.419-05:00Thanks again Richard, the PHP code and the JavaScr...Thanks again Richard, the PHP code and the JavaScript version you sent me are both up on GitHub now :).Eric Burnetthttp://www.thelowlyprogrammer.comnoreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-52457938402726502812010-08-28T10:21:38.641-04:002010-08-28T10:21:38.641-04:00How many ways can one choose a k-tuple of disjoint...How many ways can one choose a k-tuple of disjoint subsets of an n element set A?Celethianoreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-14846422639310167292010-06-30T17:08:25.683-04:002010-06-30T17:08:25.683-04:00Hi Alex,
I figure that a *maximal subset* that IS...Hi Alex,<br /><br />I figure that a *maximal subset* that IS selected is the same as a *minimal subset* that is NOT selected.. In other words, invert the bits in the boolean vector.. This reflects the symmetry of the C(n, k) function, so your function can count either UP or DOWN..<br /><br />-- Cal in LouisvilleCalvin Miraclenoreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-83703988998282276262010-05-05T16:51:32.070-04:002010-05-05T16:51:32.070-04:00That'd be great, sure. You can send it to me h...That'd be great, sure. You can send it to me however you like, and I'll add it to the repository with the other languages. Thanks!Eric Burnetthttp://www.thelowlyprogrammer.comnoreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-36657812842100989752010-05-05T15:15:18.785-04:002010-05-05T15:15:18.785-04:00Hacked together a version in Python, it's your...Hacked together a version in Python, it's yours if you want it.Josiahhttp://chouyu-31.livejournal.comnoreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-60553611167542929752010-04-27T23:07:33.111-04:002010-04-27T23:07:33.111-04:00Interesting article, thanks! I plan to use this te...Interesting article, thanks! I plan to use this technique in the future, to iterate over subsets. I played around with writing some Haskell code to implement this an I blogged about it at http://alexstangl.wordpress.com/2010/04/27/finding-minimum-qualified-subset-in-haskell/<br /><br />I just reviewed the comments and noticed Calvin's application is to find a maximal, not minimal subset. I'll add that capability into the Haskell code.alexstanglnoreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-70002881155678502192010-04-24T08:57:50.321-04:002010-04-24T08:57:50.321-04:00Good catch, thanks.Good catch, thanks.Eric Burnetthttp://www.thelowlyprogrammer.comnoreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-72026986761835131802010-04-24T08:38:46.006-04:002010-04-24T08:38:46.006-04:00> in a stateless manor
Probably, "in a st...> in a stateless manor<br />Probably, "in a stateless manner"kankowskinoreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-77208872021908341492010-04-23T20:21:59.412-04:002010-04-23T20:21:59.412-04:00What really attracted me to Banker's was the w...What really attracted me to Banker's was the way it enumerated subsets *monotonically*. My application was to find a maximal clique in an undirected graph. In a graph of 100 nodes (say), Banker's allowed me to eliminate all sets of size 100, then all sets of size 99, then all of 98, and so on. Banker's made *steady progress* to find a maximal clique, which no other count would do. <br /><br />As I related to Eric, I was just surprised not to find Banker's as a standard recipe in all of the algorithm cookbooks that are out there. I credit Eric with being the smartest guy in the room for figuring out a static method for Banker's, and I hope Banker's becomes much better known and used. <br /><br />-- Calvin Miracle, Louisville KYCalvin Miraclenoreply@blogger.com