Thread: Help with C combinatronics problem

1. Just another question regarding this problem, would it be possible to apply memoization to this algorithm ( or to a different algorithm solving this problem)? If so how? 2. How high are the inputs likely to go?

With inputs of 100 100 100 100 there are four hundred million unique potential calls (since last is also a parameter and has 4 values). That's a lot of memoization. Input of 1000 1000 1000 1000 has a four billion unique potential calls.

If you really want to speed the problem up you could do it non-recursively. This could be thousands of times faster. 3. Originally Posted by john.c How high are the inputs likely to go?

With inputs of 100 100 100 100 there are four hundred million unique potential calls (since last is also a parameter and has 4 values). That's a lot of memoization. Input of 1000 1000 1000 1000 has a four billion unique potential calls.

If you really want to speed the problem up you could do it non-recursively. This could be thousands of times faster.
20 is the max number each number will be. I'm just trying to figure out what a memoization strategy would look like on this problem. 4. Originally Posted by ihaterecursion 20 is the max number each number will be. I'm just trying to figure out what a memoization strategy would look like on this problem.
It would really help me if anybody could help me with this. 5. Does this qualify...

Code:
int my_memorized_func(int a, int b, int c, int d) {
static int results = {0};
if(results[a][b][c][d] == 0)
results[a][b][c][d] = my_actual_func(a,b,c,d);
return results[a][b][c][d];
} 6. Originally Posted by ihaterecursion Hi, I'm learning combinatronics and algorithms in C at uni and stumbled upon this problem which I'm struggling to solve. I'm posting here after trying for 3 days to write a decent solution, but the only one that works is basically a recursive brute force, which is less than ideal. I would really appreciate any help, especially with the recursive function.
Combinatorics was a new term to me so I had to look it up but from my understanding the rules require that you throw away some gems sometimes prior to calculating the max length of the necklace, for starters you would need something like this before any attempt to calculate the max length without brute force:

Code:
potential_zpairs = (z+r) % z
potential_rpairs = (t + s) % r
potential_tpairs = (z + r) % t
potential_spairs = (t + s) % s
potential_maxlen = potential_zpairs + potential_rpairs + potential_tpairs + potential_spairs
... Popular pages Recent additions algorithms c, code, immediately, problem, recursion 