2

I have a list of strings. I have a set of numbers:

{1, 2, 3, 4}

and I need to generate all combinations(?) (strings) to check against my list, Combinations:

(1, 2, 3, 4), (1234), (1, 2, 3, 4), (123, 4), (12, 34), (1, 2, 34), (1, 234), (1, 23, 4), (1, 23), (1, 2, 3), (1 2), ((1 2), (3 4))...etc.

This problem grows larger as my set of numbers gets larger. Is it right that this is a bad problem to use recursion for? (that is what I have now) However, aren't the space requirements stricter for an iterative solution, such as the maximum size of lists?

At termination, I need to look at the number of matches, for each result, with my list, and then the number of component parts for each result.. ex. (1) = 1; (1, 2) = 2.

My computer was running out of memory (this is an abstraction of a problem with larger objects)

EDIT: so my question was in a significantly larger context, such as graphics, comparing pixels in a 700 x 500 matrix... My way cannot be the most efficient way to do this..? I need to know the nested structure of the objects and how many pre-exisiting components that comprise them (that are in my list of strings)

EDIT2: The full problem is described here.

Community
  • 1
  • 1
user2827214
  • 1,191
  • 1
  • 13
  • 32
  • 3
    For a set of size 4, you're going to do 24 such combinations. For a set of size 5, you do 120. For a set of size *n*, you do *n!*. Recursion is ***not*** this problem's best friend. Not by a long shot. – Makoto Jun 05 '14 at 01:56
  • Is it really necessary to generate all the combinations in order to count how many would match your list? – Patricia Shanahan Jun 05 '14 at 02:23
  • @PatriciaShanahan It is a dynamic programming problem, yes I need to compare them based on a couple factors – user2827214 Jun 05 '14 at 02:45
  • It's generally a very bad idea to generate all combinations. If your problem is what I think it is, then I'm thinking there's a linear if not polynomial time solution. Since you actually only need to count the number of solutions rather than obtain a list of all possible solutions. I suspect you can limit it O(N^2) where N is the size of the set of numbers. Your probably better off asking another question about what you are actually trying to do rather than asking a question about why your attempt at doing it is inefficient, with a link to this question to show you tried solving it already. – Nuclearman Jun 06 '14 at 23:40
  • IE: If you treat your list of strings as a set of strings, you can probably avoid the need to generate every combination. Since you can quickly and efficiently check if a string is in the set. Likewise if you treat your string as a set of characters, you can quickly and efficiently determine if a character (or number) is in that string. The performance then could be as low as O(N*m) where N is the size of the list of strings and m is the average size of the strings within that list. Though it depends on what you actually need to do rather than how you are doing it, which still isn't clear. – Nuclearman Jun 06 '14 at 23:54
  • @Nuclearman I linked the full problem description in my edit – user2827214 Jun 09 '14 at 20:15

4 Answers4

1

If this is the only way to solve your problem (generating all combinations) then it's going to be slow, it doesn't necessarily have to take up a bunch of memory though.

When doing recursion, you'll want to use tail-recursion to optimize memory usage. Or just switch over to an iterative approach.

If you need to save the combinations that match, make sure you only save the combination not copies of the objects themselves.

As a last resort you could always append each matching combination to a file to read in later, then you wouldn't be using much memory at all.

All these things could help with your memory problems.

kyldvs
  • 61
  • 3
  • Could you be a little more clear on exactly what problem you're trying to solve? Are you trying to check if another image appears within another? Are you trying to cluster pixels groups in an image that look similar? – kyldvs Jun 05 '14 at 03:06
  • Yes, I am checking if an image contains another image, then using that knowledge to create a set of each combination of nested images, and then look at the properties of each final combination. Final combination meaning it contains each element of the set 1, 2, 3, 4 in some combination – user2827214 Jun 05 '14 at 03:32
1

If you're getting stackoverflow then it is indeed related to using a recursive routine. This can be alleviated by either increasing the stack depth (see this SO question:What is the maximum depth of the java call stack?) or using an iterative method.

However, if you simply ran out of memory then you will need to store the solution to disk as you go or figure out a way to store the combinations in a more compact data-structure.

Community
  • 1
  • 1
bcorso
  • 45,608
  • 10
  • 63
  • 75
1

As a general rule: do not use recursion when iteration is sufficient.

Recursion uses a stack, and when that stack is full you have stack overflow. If you're performing something with a factorial expansion the stack will seldom be big enough for a recursive solution to be viable.

If you can accomplish something by a loop, or a nested loop use that instead.

Furthermore, if you're simply checking each combination against something, you do not need to store the result of all combinations (which will take up enormous memory), instead compare against each combination then throw that generated combination away.

Matt Coubrough
  • 3,739
  • 2
  • 26
  • 40
  • Thanks for your answer, that makes sense. About the last part though, I am checking each combination, but along the way while generating, I am checking each one, checking to replace that string/substring or 'a field of that object' with it's match, for example, (12) = match in list, replace (12) with letter 'A'... and continue construction of the combinations using that 'A' instead of (12) – user2827214 Jun 05 '14 at 03:03
  • @user2827214 you'll need to be much more specific about your actual problem for more detailed help. If you're block-matching pixels in an image there are quite a few well-known solutions in this domain. If you're actually matching Strings, there are domain specific solutions to that too. – Matt Coubrough Jun 05 '14 at 03:50
  • Do you have any links? I'll update when I change my solution to iteration, but yes it sounds familiar to block-matching, grouped block-matching. I will investigate . – user2827214 Jun 05 '14 at 04:11
0

My computer was running out of memory (this is an abstraction of a problem with larger objects)

If your program is running out of stack memory, then you will be getting a StackOverflowError. If you see that, it indicates that your recursive algorithm is either the wrong approach ... or you have a bug in it. (Probably the latter. Your maximum depth of recursion should be the base set size N if your algorithm is correct.)

If your program is running out of heap memory, then you will be getting an OutOfMemoryError. If that is what you see, then the chances are that the problem is that you don't have enough heap memory to hold the set of combinations that you are generating.

I don't think we have enough information to tell you the best way to solve this. If N is going to be large, then it may be that your entire computational approach is intractable.

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216