Combinations of disjoint sets
Author
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
Recursively? And beware, the number of such partitions grows exponentially (x!/((x/y)!)^y).
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 9C3*6C3 ways to do it, in the 9-3 case. Can you generalise that to x-y?
Admiral
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 9C3*6C3 ways to do it, in the 9-3 case. Can you generalise that to x-y?
Admiral
Author
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.
Nikolaos
sahtaridis@the.forthnet.gr
PS: Yes, x will always be a multiple of y.
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.
Nikolaos
sahtaridis@the.forthnet.gr
PS: Yes, x will always be a multiple of y.
If you sort the numbers first to group duplicates, the problem should be easier to solve. Letting qi be the number of instances of integer i, you can sort all the qi 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 qi is greater than y, there is no solution due to the pigeonhole principle.
The only catch is that if any qi is greater than y, there is no solution due to the pigeonhole principle.
Quote:Original post by TheAdmiral
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 9C3*6C3 ways to do it, in the 9-3 case. Can you generalise that to x-y?
Admiral
Is 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 Zx but these would not exhaust all possibilities. So if you require all then I can be of no help.
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.
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.
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
