Thread: Help with C combinatronics problem

  1. #16
    Registered User
    Join Date
    Nov 2021
    Posts
    9
    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. #17
    Registered User
    Join Date
    Dec 2017
    Posts
    1,238
    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.
    Your logic makes me feel like a dick. - Bob Fossil

  3. #18
    Registered User
    Join Date
    Nov 2021
    Posts
    9
    Quote Originally Posted by john.c View Post
    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.
    Last edited by ihaterecursion; 11-29-2021 at 04:54 PM.

  4. #19
    Registered User
    Join Date
    Nov 2021
    Posts
    9
    Quote Originally Posted by ihaterecursion View Post
    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. #20
    Registered User
    Join Date
    Sep 2020
    Posts
    301
    Does this qualify...

    Code:
    int my_memorized_func(int a, int b, int c, int d) {
        static int results[20][20][20][20] = {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. #21
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,459
    Quote Originally Posted by ihaterecursion View Post
    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 subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 02-09-2014, 06:46 PM
  2. Problem passing argument into function, basic problem
    By tsdad in forum C++ Programming
    Replies: 7
    Last Post: 05-22-2013, 12:09 PM
  3. Replies: 2
    Last Post: 01-06-2013, 07:49 AM
  4. Replies: 1
    Last Post: 12-07-2012, 10:00 AM
  5. Replies: 4
    Last Post: 10-16-2008, 07:30 PM

Tags for this Thread