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\$
  • 4
    \$\begingroup\$ If your code fails to do what's intended, it's not ready for code review here. \$\endgroup\$ – πάντα ῥεῖ Sep 15 '19 at 8:47
  • 3
    \$\begingroup\$ Also note that cross-posting is frowned upon in the SE network. \$\endgroup\$ – πάντα ῥεῖ Sep 15 '19 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 '19 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 '19 at 11:16
  • 1
    \$\begingroup\$ @RubberDuck Let's agree to disagree ;-). \$\endgroup\$ – πάντα ῥεῖ Sep 15 '19 at 11:50