Integer partition (#24)

Ethienne Graveline · Eti · web-flow · commit 2881b3f18dc8 · 2020-05-22T19:06:17.000-04:00
* Fixed error in Integer Partition returns the wrong total for some values of n e.g. when n is 6 returns 14 instead of 11 This more closely resembles the code from referenced in the README: https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/integer-partition * added some simple comments * fixed error in Integer Partition on some values it would print wrong partitions e.g. when n is 6 [3,3,1] is printed but is not a valid output * fixed a typo Co-authored-by: Eti <ethiennegraveline@gmail.com>
diff --git a/Dynamic Programming/Integer Partition/code.js b/Dynamic Programming/Integer Partition/code.js
@@ -8,48 +8,61 @@ const logger = new LogTracer();
 Layout.setRoot(new VerticalLayout([tracer, logger]));
 const integer = Randomize.Integer({ min: 5, max: 14 });
 const D = [];
-const A = [];
+const A = "";
 for (let i = 0; i <= integer; i++) {
   D.push([]);
-  D[0][i] = 1;
-  D[i][1] = 1;
-  for (let j = 0; j <= integer; j++) D[i][j] = 0;
+  D[i][0] = 1
+  for (let j = 1; j <= integer; j++) D[i][j] = 0;
 }
 tracer.set(D);
 Tracer.delay();
 // }
 
 function partition(A, n, p) {
-  // logger {
-  if (n === 0) logger.println(`[${A.join(', ')}]`);
-  // }
-  else {
-    let end = n;
-    if (p !== 0 && A[p - 1] < n) end = A[p - 1];
-    for (let i = end; i > 0; i--) {
-      A[p] = i;
-      partition(A, n - i, p + 1);
+    // logger {
+    if (p == 0) logger.println(`[${A.split('').join(', ')}]`);
+    // }
+    else {
+        if (n > 1) partition(A, n - 1, p);
+        if (n <= p) partition(n + A, n, p - n);
     }
-  }
 }
 
 function integerPartition(n) {
-  // Calculate number of partitions for all numbers from 1 to n
-  for (let i = 2; i <= n; i++) {
-    // We are allowed to use numbers from 2 to i
-    for (let j = 1; j <= i; j++) {
-      // Number of partitions without j number + number of partitions with max j
-      // visualize {
-      tracer.select(i, j);
-      Tracer.delay();
-      // }
-      D[i][j] = D[i][j - 1] + D[i - j][Math.max(j, i - j)];
-      // visualize {
-      tracer.patch(i, j, D[i][j]);
-      Tracer.delay();
-      tracer.depatch(i, j);
-      tracer.deselect(i, j);
-      // }
+
+  // cycle through each cell of matrix
+  for (let i = 1; i <= n; i++) {
+    for (let j = 1; j <= n; j++) {
+      if (i > j)  {
+        // visualize {
+        tracer.select(i, j);
+        Tracer.delay();
+        // }
+        // set cell to cell above it
+        D[i][j] = D[i - 1][j];
+        // visualize {
+        tracer.patch(i, j, D[i][j]);
+        Tracer.delay();
+        tracer.depatch(i, j);
+        tracer.deselect(i, j);
+        // }
+      }
+      else {
+        // visualize {
+          tracer.select(i, j);
+          Tracer.delay();
+        // }
+        // grab above cell and add it to previous cell
+        const above = D[i - 1][j];
+        const left = D[i][j - i];
+        D[i][j] = above + left;
+        // visualize {
+          tracer.patch(i, j, D[i][j]);
+          Tracer.delay();
+          tracer.depatch(i, j);
+          tracer.deselect(i, j);
+        // }
+      }
     }
   }
   return D[n][n];
@@ -58,7 +71,7 @@ function integerPartition(n) {
 // logger {
 logger.println(`Partitioning: ${integer}`);
 // }
-partition(A, integer, 0);
+partition(A, integer, integer);
 const part = integerPartition(integer);
 // logger {
 logger.println(part);
