Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit2881b3f

Browse files
Ethienne GravelineEti
Ethienne Graveline
and
Eti
authored
Integer partition (#24)
* Fixed error in Integer Partitionreturns the wrong total for some values of ne.g. when n is 6 returns 14 instead of 11This 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 Partitionon some values it would print wrong partitionse.g. when n is 6 [3,3,1] is printed but is not a valid output* fixed a typoCo-authored-by: Eti <ethiennegraveline@gmail.com>
1 parent6a80b21 commit2881b3f

File tree

1 file changed

+44
-31
lines changed
  • Dynamic Programming/Integer Partition

1 file changed

+44
-31
lines changed

‎Dynamic Programming/Integer Partition/code.js

Lines changed: 44 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -8,48 +8,61 @@ const logger = new LogTracer();
88
Layout.setRoot(newVerticalLayout([tracer,logger]));
99
constinteger=Randomize.Integer({min:5,max:14});
1010
constD=[];
11-
constA=[];
11+
constA="";
1212
for(leti=0;i<=integer;i++){
1313
D.push([]);
14-
D[0][i]=1;
15-
D[i][1]=1;
16-
for(letj=0;j<=integer;j++)D[i][j]=0;
14+
D[i][0]=1
15+
for(letj=1;j<=integer;j++)D[i][j]=0;
1716
}
1817
tracer.set(D);
1918
Tracer.delay();
2019
// }
2120

2221
functionpartition(A,n,p){
23-
// logger {
24-
if(n===0)logger.println(`[${A.join(', ')}]`);
25-
// }
26-
else{
27-
letend=n;
28-
if(p!==0&&A[p-1]<n)end=A[p-1];
29-
for(leti=end;i>0;i--){
30-
A[p]=i;
31-
partition(A,n-i,p+1);
22+
// logger {
23+
if(p==0)logger.println(`[${A.split('').join(', ')}]`);
24+
// }
25+
else{
26+
if(n>1)partition(A,n-1,p);
27+
if(n<=p)partition(n+A,n,p-n);
3228
}
33-
}
3429
}
3530

3631
functionintegerPartition(n){
37-
// Calculate number of partitions for all numbers from 1 to n
38-
for(leti=2;i<=n;i++){
39-
// We are allowed to use numbers from 2 to i
40-
for(letj=1;j<=i;j++){
41-
// Number of partitions without j number + number of partitions with max j
42-
// visualize {
43-
tracer.select(i,j);
44-
Tracer.delay();
45-
// }
46-
D[i][j]=D[i][j-1]+D[i-j][Math.max(j,i-j)];
47-
// visualize {
48-
tracer.patch(i,j,D[i][j]);
49-
Tracer.delay();
50-
tracer.depatch(i,j);
51-
tracer.deselect(i,j);
52-
// }
32+
33+
// cycle through each cell of matrix
34+
for(leti=1;i<=n;i++){
35+
for(letj=1;j<=n;j++){
36+
if(i>j){
37+
// visualize {
38+
tracer.select(i,j);
39+
Tracer.delay();
40+
// }
41+
// set cell to cell above it
42+
D[i][j]=D[i-1][j];
43+
// visualize {
44+
tracer.patch(i,j,D[i][j]);
45+
Tracer.delay();
46+
tracer.depatch(i,j);
47+
tracer.deselect(i,j);
48+
// }
49+
}
50+
else{
51+
// visualize {
52+
tracer.select(i,j);
53+
Tracer.delay();
54+
// }
55+
// grab above cell and add it to previous cell
56+
constabove=D[i-1][j];
57+
constleft=D[i][j-i];
58+
D[i][j]=above+left;
59+
// visualize {
60+
tracer.patch(i,j,D[i][j]);
61+
Tracer.delay();
62+
tracer.depatch(i,j);
63+
tracer.deselect(i,j);
64+
// }
65+
}
5366
}
5467
}
5568
returnD[n][n];
@@ -58,7 +71,7 @@ function integerPartition(n) {
5871
// logger {
5972
logger.println(`Partitioning:${integer}`);
6073
// }
61-
partition(A,integer,0);
74+
partition(A,integer,integer);
6275
constpart=integerPartition(integer);
6376
// logger {
6477
logger.println(part);

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp