Win a copy of Learning Regular Expressions this week in the General Computing forum!

since Aug 20, 2011

Fullerton, CA

Cows and Likes

Cows

Total received

3

In last 30 days

0

Total given

0

Likes

Total received

17

Received in last 30 days

0

Total given

16

Given in last 30 days

0

Forums and Threads

Scavenger Hunt

Ranch Hand Scavenger Hunt

Greenhorn Scavenger Hunt

Stephan van Hulst wrote:

You could pass an action from the main method that you want to perform on every combination, but because your algorithm walks through the tree of partial combinations breadth-first, it still needs to keep all partial combinations in memory, which again will crash your application. The fact of the matter is that you can't solve this problem inӨ(n)space complexity (nbeing the number of sets in the input, the size of those sets being of no consequence) without using recursion or a stack machine.

I see.

6 months ago

Stephan van Hulst wrote:You can convert recursive solutions to iterative solutions by making the recursion stack explicit. However, the code for that usually isn't pretty and the recursive solution is much easier to understand. If you're not comfortable with recursion, I strongly recommend that you practice because it's an incredibly important tool.

Let me practice recursion. Will post the solution here.

Stephan van Hulst wrote:How are you going to return every combination? [/quote

I mean when I am making combinations, I will put my action in there to perform a task for the combinations. For example

6 months ago

Piet Souris wrote:

But what I meant was: if you have N lists, with sizes S(1), ...., S(N), then you can convert easily each long L into the N-tuple (i1, i2, ..., iN), and the corresponging product would then be simply List(1).get(i1) + ... +List(N).get(iN).

so you can't have a more compact representation then just the input lists.

I still didn't get it.

Any example, please.

6 months ago

Piet Souris wrote:

Well, I wondered why you would need the full Cartesian Product.

What I was thinking was, I will have all the combinations in memory and whenever I need one, I will get it from memory but it's inappropriate.

Piet Souris wrote:

Can you give a use case where you need to have available the full Cartesian Product?

Not really sure because I just picked this problem randomly.

6 months ago

Liutauras Vilda wrote:@OP If that's for an interview, avoid such writings as:

if (input.length <= 0), how that can ever be less than 0?

Yeah, it will never be less than 0.

6 months ago

Stephan van Hulst wrote:

prefixes.forEach(prefix ->

forEachCombination(remainingInput, smallerCombination -> {

List<T> combination = smallerCombination;

combination.add(0, prefix);

action.accept(combination);

})

);

}

[/code]

Okay. I am totally lost here. So its recursively calling

6 months ago

Stephan van Hulst wrote:You still haven't given requirements. Questions about performance are meaningless as long as it's unknown what a correct program should output.

It should output all the combinations of given input (4 sets of String). Basically instead of

6 months ago

Okay so here are some requirements/questions:

Following is my code:

Following is the output:

`Total time took: 0.006
`

Total combinations in memory: 3888

Total space (bytes): 342992

I understand above output is not the time and space complexity in terms of Big O. In terms of Big O, the worst case space complexity would be O (mⁿ) as Stephan also mentioned is in his answer. The time complexity would also be same.

Questions:

1.) Is there a way to improve the performance? Would there be a better data structure for this?

2.) Is there a way to improve the Big O?

3.) I have three nested loops in my code. Can they be reduced?

Note: To get the space I am just doing some simple computation. Space is approximate.

Following is my code:

Following is the output:

Total combinations in memory: 3888

Total space (bytes): 342992

I understand above output is not the time and space complexity in terms of Big O. In terms of Big O, the worst case space complexity would be O (mⁿ) as Stephan also mentioned is in his answer. The time complexity would also be same.

Questions:

1.) Is there a way to improve the performance? Would there be a better data structure for this?

2.) Is there a way to improve the Big O?

3.) I have three nested loops in my code. Can they be reduced?

Note: To get the space I am just doing some simple computation. Space is approximate.

6 months ago

Paul Clapham wrote:

Punit Jain wrote:Okay. my bad I should have written this earlier. I don't have exact requirements. I just picked a random problem wrote some code and now trying to optimize it for my own understanding.

Yes, I suspected that was the case. Working on "random problems" is a useful way to improve your skills, but when you don't have any requirements then you can't really ask what you should do.

Okay. Let me add specific questions.

6 months ago

Paul Clapham wrote:

Piet Souris wrote:I don't know your requirements...

I don't know your requirements either. I only know that the fact is that you can't store all of the data in memory, and you don't have enough time to store it all somewhere else. So computing relevant subsets as they are needed might be a good strategy. Which subsets are the relevant ones, I can't tell.

Okay. my bad I should have written this earlier. I don't have exact requirements. I just picked a random problem wrote some code and now trying to optimize it for my own understanding. Will be helpful for me to crack interviews as well as I am about to graduate.

6 months ago

Paul Clapham wrote:

Punit Jain wrote:But eventually, I will need the full cartesian product. In order to have all the combinations, I will have to have all the sets. Can you please elaborate?

Do you need the full cartesian product, in memory, all at the same time?

Remember that there are about 35,000,000,000 vectors in that full cartesian product. We've already established that they don't all fit into memory. So perhaps you don't need them all at the same time. Maybe you don't actually expect to use all 35 billion of them, so you could just calculate the ones you actually use, at the time you use them.

Let say I have 12 sets. Out of those 12, I want the cartesian product of only 2 sets, so I will compute only for those 2. Now tomorrow I want for another 2 then compute for another 2. Basically filtering my data based on my need. Is that what you mean? Correct me if I am wrong,

6 months ago

If I reduce the number of sets to 3-4 in my input data. Can this code be optimized?

6 months ago

Stephan van Hulst wrote:The Big Theta expression I gave expresses an order of growth, it's not a function you can use to calculate the actual memory requirements.

The input you used has a set of 9 elements, a set of 6 elements a set of 8 elements, and repeats this 4 times.

The number of times that the inner loop is executed is (9*8*6)^4. That's also the number of vectors stored. Multiply by 4 to get the number of bytes, and divide by 1024^3 to get the number of gigabytes.

Cool. Thanks so much.

6 months ago

Campbell Ritchie wrote:. . . Stephan said assuming 4 bytes per reference, which makes 1,129,718,145,924, which is approx.

My bad. Got it now.

Campbell Ritchie wrote:Since that amount of storage is only feasible in a linked list or deeply nested arrays, that will increase the storage requirement yet again. I shall let you work out how long it would take to iterate a 280GB linked list; have you got a few days to spare?

Since my system RAM is just 6 GB, it will never run on my system.

6 months ago

Piet Souris wrote:I don't know your requirements, but must you store the full Cartesian Product? For any quadruple (x, y, z, w) it is easy to calculate the corresponding cp.

But eventually, I will need the full cartesian product. In order to have all the combinations, I will have to have all the sets. Can you please elaborate?

6 months ago