• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Looking for algorithm, to generate all combinations of a set

 
William Barnes
Ranch Hand
Posts: 1067
2
IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Not really a Java specific question, I know.

Given a set of something, how do I generate all combinations?  Is this a smart way of doing this?  My first attempt to would be to have a bunch of loops, I guess.

Example input: 1,2,3,4
Desired output (all pairs, all triplets, ...):
 12,13,14,21,31,41,23,24,32,34,42,43,
 123,...,
 ...,4321

I think I can handle duplicates by using a data structure which will just not allow you duplicates.  Something like this maybe?  

 
Carey Brown
Saloon Keeper
Posts: 10705
86
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think it would be better to come up with an algorithm that would guarantee no duplicates. This should be doable if the input is a Set (in the  Java sense), meaning, no duplicate entries.

If you want to go ahead with your approach:
Trying to filter out duplicates after a permutation is computed is best done with a HashSet<String> but you might run out of memory because of a combinatorial explosion as the set gets bigger. The key might be something like "1-2-3-4".
 
Liutauras Vilda
Marshal
Posts: 8857
637
Mac OS X VI Editor BSD Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@OP

Please clarify, are we talking about combinations or permutations? Topic subject insists combinations, however, in your example as desired output you showed permutations, as 12 and 21 are certainly different permutations, but if we were to talk about combinations, then these would have been considered as duplicates.

So which ones?
 
Piet Souris
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
There are quite some ways to generate all ordered subsets/sublists of some set/list.

One way that I liked very much is this one:

First: generate all possible subsets from the numbers 0...N. We are sure that we don't have any duplicates, and it is relatively easy to come up with all the subsets. Then, given any List<T> or Set<T>, map each of the integers 0...N to the elements of the List/Set, and we're done. To accept duplicates in the original List is up to you: either stick with them or eliminate these duplicates.

A way to get all the subsets and that I liked goes like this:

suppose we have a subset {1, 3, 6} as one of the subsets of the Set {1, 2, ..., 10}, and from this we generate the subsequent subsets of length 4. Now, the subset is ordered, so we make a loop from the highest element + 1 (7 in this example) to 10, getting the mapping {1, 3, 6} -> { {1, 3, 6, 7}, {1, 3, 6, 8}, {1, 3, 6, 9}, {1, 3, 6, 10} }.
I store that newly generated length-4 subsets in a Map<Integer, List<List<Integer>>. If the Map initially is empty, then we start with creating a List that contains an empty list, and put that in the map with map.put(0, startingList). (So we have the empty subset captured!)
Otherwise, if we want to generate all subsets of length K, we recursively get the list of subsets of length K-1, and for each of these subsets in that list we apply the algo as described above.

It can be done in just a few lines of code, but as said: there are many other ways to get a list of all the subsets.

 
S Fox
Rancher
Posts: 285
14
Eclipse IDE C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
the easiest way i found to do this was to use a library. I know of 3: guava, neoitertools, and combinatoricslib. one of those will work for you i'm sure.
there's also builtin functions for this in python if you want to use it.

there's a difference between combinations and permutations, and these libraries can do either, just make sure you understand the difference and use the correct methods.
 
S Fox
Rancher
Posts: 285
14
Eclipse IDE C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
P.S. I suggest just adding everything to a HashSet, it automatically removes the duplicates for you. Then if you need it as a list, create your list from that set.
 
Pete Letkeman
Bartender
Posts: 1868
81
Android IntelliJ IDE MySQL Database Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Quick question:
Is this homework?
If this is homework then please identify it as such as we try not to do homework for people on this site.
We do however try to help the person find the solution with hints and by asking questions.

Quick note:
I was able to find a solution to this problem which can be found here
https://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/
This site also has many different solutions for many different programming languages to this problem:
https://rosettacode.org/wiki/Combinations

If you want this in a math context then this posting may be for you
http://mathonline.wikidot.com/generating-all-combinations-of-a-set

Please do not let my posting dissuade you from using this site.
 
William Barnes
Ranch Hand
Posts: 1067
2
IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
> Is this homework?
Ha!  Ya, I wish.  
 
William Barnes
Ranch Hand
Posts: 1067
2
IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes!  This is what I was looking for.  Thanks!

https://github.com/dpaukov/combinatoricslib3

All the feedback was helpful, as always.  You guys/gals rock.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic