aspose file tools*
The moose likes Java in General and the fly likes creating a list of subsets from N elements Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "creating a list of subsets from N elements" Watch "creating a list of subsets from N elements" New topic
Author

creating a list of subsets from N elements

luc comeau
Ranch Hand

Joined: Jan 20, 2005
Posts: 97
Hi everyone, first time posting in this particular forum, hope i chose the right place

Ok so i have this problem; I am given a vector containing Strings in them say for example,"name","Telephone","address"..etc (personal information bascially).
To simplify the problem i think maybe ill just make each string in the array correspond to a letter in the alphabet ie.name=a,telephone=b,address=c.

Ok so say i am passed a vector with "a","b","c", i need to be able to create all the sets of these, without repeating any letters in a set.So basically my answer to this should just be;
a,b,c,ab,ac,bc,abc

But my method to do this must also be able to handle any amount of inputs, not just three, so i could have a,b,c,d,e...then must be able to find all the sets of those as well.

I started this using for loops but i think i began to realize that it didnt work for N inputs, because each time i wanted more inputs i needed more for loops, so its bascially useless what ive done so far.Maybe recursion or something might be useful, anyone have any ideas?

Thanks for patiently reading, hope to hear some suggestions!


National Research Council<br />Internet Logic Department
Stephen Huey
Ranch Hand

Joined: Jul 15, 2003
Posts: 618
Sounds like a school assignment...yeah, I'd say go for recursion. If you need to double check your work (make sure you haven't added the same thing twice to a set), you might try using the java.util.Set class (or rather, maybe java.util.HashSet or something like that).
luc comeau
Ranch Hand

Joined: Jan 20, 2005
Posts: 97
hey,
lol, its not a school assignment at all, haha, i wish it was, im actually writing a program at work, this is a minor part to it but its essential for forward progress in the project.I asked a few people here at work and they say they may have some notes from their Algorithms and Data structures classes that might be able to help me, but we'll see i supose.

I infact am not a huge fan of recursion, cause it actually requires more effort to think up the logic for it,(poor me eh) haha but i guess i can give it a try.As for the java.util.set class and the hashSet, ill give them a looking at, still any other ideas would be much appreciated!
thanks again
[ February 21, 2005: Message edited by: luc comeau ]
Igor Stojanovic
Ranch Hand

Joined: Feb 18, 2005
Posts: 58
Hi luc,

I think you should use Varargs (Methods That Allow Variable-Length Parameter Lists)


The following class defines a method that accepts a vararg, and invokes the same method passing it first several arguments and then fewer arguments. The arguments come in as an array.




When combined with the for each loop, varargs are very easy to use.


Note that varargs are new to SDK 5.0, so you need to compile for that version of Java to use them.



kind regards
Igor
[ February 21, 2005: Message edited by: Igor Stojanovic ]
Michael Dunn
Ranch Hand

Joined: Jun 09, 2003
Posts: 4632
luc comeau
Ranch Hand

Joined: Jan 20, 2005
Posts: 97
hi everyone

Igor, thanks for the effort with the Varargs, i should have mentioned before that i am not using 1.5, i have started this project before it was released so im using 1.4.2, but it i cant figure something out i will consider that, thanks

Michael,I gave your code a run and the only thing that appears wrong withit is that it is writing out all "permutations" of the String "abcd"(well its not really wrong but in my situation it is),i infact need the combinations of "abcd" where ordering doesnt matter.So where your program counts ab,ba as two different elements, i infact would only count them as one, like i wouldnt consider them at all as being different.

Im going to try and trace through your code and see if i can figure out how to change this, but if its easy to fix and repost please feel free, but thanks for the time u took to post that in the first place, much appreciated !
P.s- has anyone ever heard of the "Banker's Sequence"
iv done a little research and aparently this sequence is the fastest way to approach this problem, but iv yet to find any implementation of it in java.
It does the subsets int he way you would suspect
if you had abcd, its would orde them like this
{a,b,c,d},{ab,ac,ad},{bc,bd},{cd},{abc,abd},{acd},{bcd},{abcd}
just a thought, maybe this might strike some more ideas.
[ February 22, 2005: Message edited by: luc comeau ]
Michael Dunn
Ranch Hand

Joined: Jun 09, 2003
Posts: 4632
try this one then

David Harkness
Ranch Hand

Joined: Aug 07, 2003
Posts: 1646
If it helps, realize that what you're effectively doing is counting in binary. Each element in the original list is a bit representing whether it is in or out of any given subset, so you're writing out all possible bit combinations. If there were three elements, the subsets would beYou could use a recursive algorithm if the number of elements is small enough, but you can certainly rewrite it non-recursively.

Sorry, I only have time for that much right now, but hopefully it can give you enough to solve it.
luc comeau
Ranch Hand

Joined: Jan 20, 2005
Posts: 97
hi everyone again,

David, i first would like to say thats exactly what i was working on yesterday, seems that i always come up with the same ideas as you as u post them, I wrote up some code that does the binary representation of them, for the sake of helping others wanting to do this ill post the code, or if you were intrested;



I havn't yet decided what i want to do with these binary representations, but for the most part this thread has accomplished what i asked !! Thanks

As for Michael, ill give your code a try and see if maybe i can find some way to incorporate your idea it may be useful for a later stage of my coding, non the less, thanks so much !
[ February 23, 2005: Message edited by: luc comeau ]
Luke Nezda
Greenhorn

Joined: Jun 23, 2008
Posts: 1
Last solution offered is basically a copy/paste from the C++ code from the December 2000 academic paper "Efficiently Enumerating the Subsets of a Set" by J. Loughry, J.I. van Hemert, and L. Schoofs if anyone is interested in more details on the Banker's Sequence and this implementation by its original authors.
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: creating a list of subsets from N elements