5

I have an array of Card instances.

Card[] allCards;

I am supposed to get all the possible combinations of these cards, under the following conditions:

  • All of the combinations must have a minimum of 3 cards.
  • A combination has no card limit (so if there are a total of 15 cards, you know there can be a combination of 15 cards, others of 13, 10, etc).

For college purposes, I am not supposed to use any fancy library capable of doing this job easier.

I've done it with pairs, sure, but considering that there is no limit, the algorithm I would usually do would not work.

It is pretty much what they ask here for python: Find all possible combinations

Any ideas? I don't want code or anything - I'm just lost with the algorithm/idea.

My Problem (more detailed)

I can make pairs by making two loops (one within the other). I can make triplets by having three loops (one within another within another).

But I don't know how to do this specific problem because:

  • What if the array has 15 cards? I can't write 15 loops...
  • And then of course I need to go down to 14, 13, 12 loops... (because all the combinations are not of 15 elements each, there can be combinations of 14, 13, 12 elements when working with this 15-elements-array)

I can find some combinations, but not dynamically.

Community
  • 1
  • 1
Saturn
  • 17,888
  • 49
  • 145
  • 271
  • I suggest you start by getting something that works (at least with small input arrays) before worrying about efficiency. If you can generate all pairs, can you use that to generate all triples? – Code-Apprentice Oct 31 '12 at 21:18
  • Not sure what you're looking for if not code. You've already mentioned what you need: "A list of all combinations" which turns over multiple results on google and Stack Overflow. Is there a specific reason why your problem cannot be resolved using those? – Grambot Oct 31 '12 at 21:19
  • 1
    What exactly is meant by `get all possible combinations of these cards`? As in you must output the results, or simple display a count? There's a big difference there. – sampson-chen Oct 31 '12 at 21:19
  • @sampson-chen: An array (the result) containing arrays (the combinations) that contain the cards. – Saturn Oct 31 '12 at 21:20
  • @Omega think about how to generate a powerset: http://stackoverflow.com/questions/4630670/time-complexity-of-a-powerset-generating-function – Kiril Oct 31 '12 at 21:22
  • 1
    You should start with idea of giving us some code that we may suggest how to improve. – Roman C Oct 31 '12 at 21:24
  • I've added more about why am I not able to do it. – Saturn Oct 31 '12 at 21:30
  • 1
    Here's a good place to start for these algorithms: http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n. – Robert Cooper Oct 31 '12 at 21:35
  • Related: http://en.wikipedia.org/wiki/Recursion_%28computer_science%29 – Brendan Long Oct 31 '12 at 21:41

1 Answers1

1

Paper and Pencil exercise:

Let's back away from the Java syntax for a minute. Take an example of 5 cards, say the Ace through 10 of diamonds. Now list out every possible pair. (Hint: there are 10 of them)

Now using your list of pairs, list every possible triple.

Now using the list of triples, list every possible combination of 4.

Now let's code it:

Since you don't know the maximum length of a combination at compile time, using loops will not solve the problem. On the other hand, this problem lends itself to recursion. Let's start by assuming that we have a function Card[][] getCombinations(Card[] cards) which returns an array of arrays of Cards. So if we call

Card[] cards = new Card[15];
// initialize individual Card objects
Card[][] combinations = getCombinations(cards);

combinations[i] contains one of the combinations generated.

Now, to make things easy, let's say that getCombinations() only returns pairs. How can you use these pairs to create all possible triples?

Code-Apprentice
  • 81,660
  • 23
  • 145
  • 268
  • I... Am a bit lost. *getCombinations()* returns a matrix of all pairs, okay. But, well, I still don't see how should I employ that :( – Saturn Oct 31 '12 at 22:11
  • @Omega See my edited answer. Try working out other examples with pencil and paper. This should give you a better understanding of the steps it takes to solve the problem. – Code-Apprentice Oct 31 '12 at 22:17
  • Got it working. Perhaps not as you had in mind (because it is slow as hell XD) – Saturn Nov 04 '12 at 00:46
  • 1
    @Omega That sounds about right. There are `O(n!)` combinations of `n` objects, so for large `n`, it will take a long time. – Code-Apprentice Nov 04 '12 at 22:13