Algorithm Complexity and Efficiency, Exponential o

Question

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.

Answer 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.

Answer 2

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.

Answer 3

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.

Answer 4

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.