Win a copy of Murach's Python Programming this week in the Jython/Python forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Set Combination Algorithm  RSS feed

 
Roshan Lal
Ranch Hand
Posts: 64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi everybody,

I have a problem on which some pointers can be very useful
and would appreciate some help.

The problem can be formulated like this:

There are members like, A,B,C...L, M, N,O (15 members).

These members are grouped together by some criteria and we get
get groups(sets) like (A,B), (C,D), (J,K,L), (B,D,I), (B,C,D), (A,K)
,(J,K,M,N,O) and so forth. There will be dozens and in worse cases
hundreds of such groups.

These groups have some properties which makes a group better than the other. First is the size. The larger size group is better.
Second, color.can be be green or yellow. If
there are two groups the same size say G(A,B) and Y(A,B) then G(A,B) is considered better than Y(A,B).

The goal is to combine these groups into arrangements(set of groups)
and find the best arrangement so that in an arrangement of groups,

i)none of the member in the combined group arrangement is repeated
ie [Y(A,B), G(B,C)] is invalid arrangement becuase B appears twice here.

ii) an arrangement with larger number of member is considered better
ie Y(A,B,C) is superior to G(A,B).

iii) if two arrangement have same number of members, then the one with
fewer group is considered better. eg [Y(A,B,C,D)] is better than [Y(A,B), G(C,D)].


Finding the best arrangement is proving to be an expensive operation.


My initial logic would be:
a) remove all the yellow groups who have a corresponding
sized green group as they are guarnteed to be inferior in the presence of green
group. That is if both G(A,B) and Y(A,B) exist keep only G(A,B)

b)Then partition groups into two categories the ones which don't have any of its member in any other groups and the others which may have at least one of its member present in any other group.

c) Then for each group which have at least of one of its member in common with others, we generate an arrangement by adding that group and all the disjoint groups. Compare this arrangement with the last one and keep the better one.

I hope I'm making the problem understandble. Any help, suggestion is
highly appreciated.

Thanks
Roshan
 
Frank Carver
Sheriff
Posts: 6920
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is really an algorithm performance question rather than one about servlets, so I have moved it to our Performance and Algorithms forum where you may get a better answer.
 
YuenLian Wu
Ranch Hand
Posts: 73
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
nice move man
 
Lear nable
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Roshan Lal:
Hi everybody,
These groups have some properties which makes a group better than the other. First is the size. The larger size group is better.
Second, color.can be be green or yellow. If
there are two groups the same size say G(A,B) and Y(A,B) then G(A,B) is considered better than Y(A,B).


How do you color groups? Does it serve any practical purpose?
 
William Brogden
Author and all-around good cowpoke
Rancher
Posts: 13078
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That sounds like a job for a genetic algorithm since you appear to be able to define a fitness function.

A google search for "java genetic algorithm" just turned up some great sounding toolkits.

Let us know how it works out.
Bill
 
Stefan Wagner
Ranch Hand
Posts: 1923
Linux Postgres Database Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I would start with smallest groups, because they tend to have the smallest intersections.

When I understood correctly, a supergroup of 8 Groups with a total of 16 elements is better than a supergroup of one group with 15 elements.

Then I would try to reach the maximal number of elements.
Then I would try to replace groups with larger groups of the same elements.
X (A, B) + Y (C, D) -> Z (A, B, C, D)

This would still be a hard job, and I guess it is not guaranteed to find the best combination.

It reminds me of the backpacker problem.

Are groups of 1 element possible groups? X (A)
 
Lear nable
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

b)Then partition groups into two categories the ones which don't have any of its member in any other groups and the others which may have at least one of its member present in any other group.

c) Then for each group which have at least of one of its member in common with others, we generate an arrangement by adding that group and all the disjoint groups. Compare this arrangement with the last one and keep the better one.


If I understand correctly, an optimal and valid arrangement is one in which all 15 members are included, there is NO duplication of members, and better groups prefered over worse groups. Is that correct? By "no duplication", do you mean "minimize duplication"?

Can you end up with a set of groups in partition 2 (the one with groups that have at least one member in common with another group) such that you can never form an arrangement with no duplication AND include all 15 members?

For e.g.
Partition 1: G{A,B,C,D,E,F,G}, G{H, I, J, K, L}
Partition 2: G{M, O}, G{N, O}

What would you do in this case?

Also, take a loop at Set Cover Problem
 
Roshan Lal
Ranch Hand
Posts: 64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


If I understand correctly, an optimal and valid arrangement is one in which all 15 members are included, there is NO duplication of members, and better groups prefered over worse groups. Is that correct? By "no duplication", do you mean "minimize duplication"?


You are right, Lear.
But to be considered "best" it doesn't have to have all
the members in it. In many cases, it is not even possible to have an arrangement which will cover all the members.
Best here simply will mean there is no other better arrangement. That
is, if there are 15 members and we could make only 3 arrangements with
10, 12, 13 total members then the arrangement with 13 is best.

Absolutely no duplication. Even if a single member is common amongs
groups inside the arrangement, the whole arrangement is invalid.

I'll do more search on Set Cover problem. That wiki link just gives definition.
 
Roshan Lal
Ranch Hand
Posts: 64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Stefan Wagner:
I would start with smallest groups, because they tend to have the smallest intersections.

When I understood correctly, a supergroup of 8 Groups with a total of 16 elements is better than a supergroup of one group with 15 elements.

Then I would try to reach the maximal number of elements.
Then I would try to replace groups with larger groups of the same elements.
X (A, B) + Y (C, D) -> Z (A, B, C, D)

This would still be a hard job, and I guess it is not guaranteed to find the best combination.

It reminds me of the backpacker problem.

Are groups of 1 element possible groups? X (A)


Thanks Stefan.
1. The input groups are unsorted, if we start with smallest then
we have to sort them first.
2. "a supergroup of 8 Groups with a total of 16 elements is better than a supergroup of one group with 15 elements". Yes, any arrangement with more total member is better.

I guess, the harder part is finding the intersecting sets efficiently as there could be hundreds of sets.

A naive solution could be like this.

Set findBestArrangement(Group[] groups) {
Set best = = new HashSet();;
for (int i=0; i < groups.length; i++) {
Set arrangement = new HashSet();
Group g = groups[i];
arrangement.add(g);
for (int j=0; j < groups.length; j++) {
if (i != j) {
Group g1 = groups[j];
if (!g.intersects(g1)) {
arrangement.add(g1);
}
}
}
if (arrangement.compareTo(best) > 0) {
best = arrangement;
}
}
return best;
}

We may improve upon this, say by storing the intersecting groups found so
far and so may have to sacrifice some memory for speed.

Thanks everybody for your input
Roshan
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Roshan Lal:
Thanks Stefan.
1. The input groups are unsorted, if we start with smallest then
we have to sort them first.


Sorting is relatively inexpensive - it can typically be done in O(n log n).
 
Roshan Lal
Ranch Hand
Posts: 64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Lear nable:


How do you color groups? Does it serve any practical purpose?


Lear,

There are business rules whereby groups can be in different "color"/catagories. The "color" word is used for
illustrated purpose only.
There is practical purpose for assigning these catagories.
This is one of the parameter in maximization function for the
arrangements.

Thanks
Roshan
 
Roshan Lal
Ranch Hand
Posts: 64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Lear nable:

Also, take a loop at Set Cover Problem



Lear,

I'm searching the web. Yes, looks like my problem is somewhat similar to Set Cover/Set Packing problem. So far, I have not found an implementation though.
 
Roshan Lal
Ranch Hand
Posts: 64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Stefan Wagner:
Are groups of 1 element possible groups? X (A)


Yes, they are.
 
Randall Kippen
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Someone at forums.java.sun.com was looking for a set cover algorithm. It doesn't involve the color and group size restrictions though. I programmed a simple GA that you may want to look at and modify to fit your purpose.

sun java forum - simple genetic algorithm for set cover
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!