sahtaridis 122 Report post Posted June 8, 2007 I am trying to break x integers (lets say 9 numbers) in groups of y (call it 3) mutually disjoint sets (therefore, each set contains x/y integers). For example (1 3 4) (2 7 8) (5 6 9) (1 5 8) (3 7 9) (2 4 6) etc are acceptable, whereas, say (1 5 7) (3 6 9) (4 6 8) is not, because both the second and the third set ('list' in Lisp) contain number 6. How can I generate all such distinct groups, for arbitrary x and y? Is there any technique or software etc available for that, or (better) any Lisp library functions that accepts those integers and yields the desired output? Thank you in advance. Nikolaos sahtaridis@the.forthnet.gr 0 Share this post Link to post Share on other sites
Darkstrike 206 Report post Posted June 8, 2007 Recursively? And beware, the number of such partitions grows exponentially (x!/((x/y)!)^y). 0 Share this post Link to post Share on other sites
TheAdmiral 1122 Report post Posted June 8, 2007 It's difficult to know what implicit constraints you've applied here. In particular, do the sets need to span the source set?Your counterexample doesn't satisfy the second condition as it doesn't contain 2. If adapted it so that it does contain 1 through 9, then you'd either have to drop the duplicated 6 or increase the size of one of the sets. Obviously, the problem is impossible for general x & y (take y > x).Assuming that x is always a multiple of y, then you can easily iterate or recurse and fill the sets in order. We're not going to give you any code, 'cause this all sounds very homeworky, but I think I'm allowed to tell you there are ^{9}C_{3}*^{6}C_{3} ways to do it, in the 9-3 case. Can you generalise that to x-y?Admiral 0 Share this post Link to post Share on other sites
sahtaridis 122 Report post Posted June 8, 2007 Homeworky? For a 42-year-old businessman like me?!? I wish I were 22 instead, and let all the world's homework come to me!Now seriously, the motivation behind that posting is to save some time on a business application of mine. If this code is available (it shouldn't be more than a dozen of lines in Lisp), why not just use it? I could always program it myself, but, alas, 20 years since my last class project on Lisp is a long time and oblivion gets in the way (not to mention newer versions of Lisp)...So, if you have that small piece of code in store, I would be very thankfull indeed if you could send it to my email.Thanks.Nikolaossahtaridis@the.forthnet.grPS: Yes, x will always be a multiple of y. 0 Share this post Link to post Share on other sites
Zipster 2377 Report post Posted June 8, 2007 If you sort the numbers first to group duplicates, the problem should be easier to solve. Letting q_{i} be the number of instances of integer i, you can sort all the q_{i} values from largest to smallest, and the problem turns into something that resembles a recursive knapsack problem. You start by filling up the sets with the largest groups, and recursing down to the smaller groups until each set is filled, and outputting the results along each branch.The only catch is that if any q_{i} is greater than y, there is no solution due to the pigeonhole principle. 0 Share this post Link to post Share on other sites
Daerax 1207 Report post Posted June 9, 2007 Quote:Original post by TheAdmiralIt's difficult to know what implicit constraints you've applied here. In particular, do the sets need to span the source set?Your counterexample doesn't satisfy the second condition as it doesn't contain 2. If adapted it so that it does contain 1 through 9, then you'd either have to drop the duplicated 6 or increase the size of one of the sets. Obviously, the problem is impossible for general x & y (take y > x).Assuming that x is always a multiple of y, then you can easily iterate or recurse and fill the sets in order. We're not going to give you any code, 'cause this all sounds very homeworky, but I think I'm allowed to tell you there are ^{9}C_{3}*^{6}C_{3} ways to do it, in the 9-3 case. Can you generalise that to x-y?AdmiralIs this certain? I would have thought that you create a set from all possible 3 number combinations of 9 then count how many combinations of 3 are possible from this set.So something like: combination(combination(x,y), x/y), which is 95,284 for numbers taken 3 at a time then grouped by 3 from a set [1,9]. --- sahtaridis, is it required that you list all possible partitions of [1..x]? I can think of a way based on cosets of cyclic subgroups in Z_{x} but these would not exhaust all possibilities. So if you require all then I can be of no help. 0 Share this post Link to post Share on other sites
Darkstrike 206 Report post Posted June 10, 2007 Quote:Original post by DaeraxI would have thought that you create a set from all possible 3 number combinations of 9 then count how many combinations of 3 are possible from this set.So something like: combination(combination(x,y), x/y), which is 95,284 for numbers taken 3 at a time then grouped by 3 from a set [1,9]. That would count all size x/y subsets of the set of all y-lets in x. The vast majority of those are not partitions of x, and the OP asks for partitions. 0 Share this post Link to post Share on other sites
Daerax 1207 Report post Posted June 10, 2007 Quote:Original post by DarkstrikeQuote:Original post by DaeraxI would have thought that you create a set from all possible 3 number combinations of 9 then count how many combinations of 3 are possible from this set.So something like: combination(combination(x,y), x/y), which is 95,284 for numbers taken 3 at a time then grouped by 3 from a set [1,9]. That would count all size x/y subsets of the set of all y-lets in x. The vast majority of those are not partitions of x, and the OP asks for partitions.I agree but as TheAdmiral noted, his examples seem to stress disjointedness over actual partitions. The union of his counterexample is not the original set. In fact I do not see how it can be while still matching his criteria. Assuming I understand it at all. As I noted i have a simple method that can generate many partitions on the original set based on group theory but I cannot guarantee that it will all of them. 0 Share this post Link to post Share on other sites
Zipster 2377 Report post Posted June 10, 2007 I believe the OP did indeed mean partitions, since in his first post he clarified that for x numbers and y sets there should be x/y integers per set, and in his second post he states that y divides x. He didn't go so far as to say that the union of all the subsets equals the original set, however that's one of the assumptions I'm working with.I've managed to come up with an algorithm that could find all such partitions, however it's a bit nasty and as far as I can tell implementation would be a PITA. Like I mentioned before the idea is to group numbers into n-buckets, where each n-bucket holds a list of numbers with n instances in the list. For instance, the 1-bucket would hold all numbers that have 1 instances in the list, the 2-bucket would hold all numbers with 2 instances in the list, etc. Then you try and find combinations of instance sums that add up to the set size recursive combinations across the different buckets. Or something like that. It's hard to describe, maybe I'll spend some time tonight working on a bit of code to test. 0 Share this post Link to post Share on other sites
Barius 325 Report post Posted June 10, 2007 I think it would help to use a sorted list of sorted lists for representing a partition. Then the first sublist would need to start with 1, the second one with the smallest number not in the first one, etc. 0 Share this post Link to post Share on other sites