1
\$\begingroup\$

I was trying to solve a problem on de-arrangements (Number of partial derangement such that exactly prime number discs are found away from their natural positions? (Any number of non-prime K disks may also be found in or out of their natural positions)).

Somehow solved it using recursion but my code fails (taking long time to show output sometimes it gets freezes) on larger inputs for parameter move like (1000, 1000000), working fine for smaller inputs. Any approach to optimize this recursive function with Dynamic Programming with better time complexity.

static BigDecimal derangements(int move, int dontCare) {

        if (move < 1)
            return factorial(dontCare);

        // recursion
        move--;
        BigDecimal result = derangements(move, dontCare).multiply(BigDecimal.valueOf(dontCare));
        if (move > 0) {
            result = (derangements(move - 1, dontCare + 1).multiply(BigDecimal.valueOf(move))).add(result);
        }

        return result;
}

I tried something like this but failed to correctly implement it. I know it's wrong. Any correct approach or implementation would do.

static BigDecimal derangements(int move, int dontCare) {
  BigDecimal[] moveResult = new BigDecimal[move + 1];

  moveResult[0] = factorial(dontCare);

  for (int i = 1; i < move; i++) {
      moveResult[i] = moveResult[i - 1].multiply(BigDecimal.valueOf(dontCare));
  }

  while ( move  > 1) {
      int i = 1;
      moveResult[i] = moveResult[i - 1].multiply(BigDecimal.valueOf(dontCare))

              .multiply(BigDecimal.valueOf(move)).add(moveResult[i]);
      move--;
      i++;
  }

  return moveResult[move-1];
}
\$\endgroup\$

closed as off-topic by πάντα ῥεῖ, dfhwze, Mast, pacmaninbw, ferada Sep 15 at 14:15

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." – πάντα ῥεῖ, dfhwze, pacmaninbw, ferada
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    \$\begingroup\$ If your code fails to do what's intended, it's not ready for code review here. \$\endgroup\$ – πάντα ῥεῖ Sep 15 at 8:47
  • 3
    \$\begingroup\$ Also note that cross-posting is frowned upon in the SE network. \$\endgroup\$ – πάντα ῥεῖ Sep 15 at 9:51
  • 3
    \$\begingroup\$ At least here your question seems to be off-topic. We're not going to provide you with working code. I am not that sure that you'll get better results at Stack Overflow, unless you put some more efforts in debugging and profiling the code in question. Generally SE sites aren't meant as personal help desks. \$\endgroup\$ – πάντα ῥεῖ Sep 15 at 10:34
  • 1
    \$\begingroup\$ I completely disagree @πάνταῥεῖ. The code works for small inputs. OP is looking to improve their code by making it handle large inputs. \$\endgroup\$ – RubberDuck Sep 15 at 11:16
  • 1
    \$\begingroup\$ @RubberDuck Let's agree to disagree ;-). \$\endgroup\$ – πάντα ῥεῖ Sep 15 at 11:50