/** * Copyright 2002 & 2003 Henry Bottomley (henry.bottomley@btinternet.com). * Partitions 2002, Compositions 2003 * All rights reserved */ import java.applet.Applet; import java.awt.*; import java.math.BigInteger; // could be some very large numbers public class PartitionChoice extends Applet { protected Choice distinctChoice, termNumberChoice, termMaxChoice; // choose constraints protected TextField totalSumField, termNumberField, termMaxField, messageField; // I/O (3/1) protected Button calculateButton; // start calculations protected String distinctString, termNumberString, termMaxString; // record constraints protected int totalSum, termNumber, termMax; // numbers to enter the calculations //////////////////////////////////////////////////// // init() method used to set up the visual interface // public void init() // setting up the visual interface { distinctChoice = new Choice(); // 2 choices: any terms or distinct terms distinctChoice.addItem("Partitions of:"); distinctChoice.addItem("Partitions with distinct terms of:"); distinctChoice.addItem("Compositions of:"); distinctChoice.addItem("Compositions with distinct terms of:"); add(distinctChoice); distinctString="Partitions of:"; totalSumField = new TextField(7); // number to be partitioned add (totalSumField); termNumberChoice = new Choice(); // 3 choices: no restriction on number of terms, // exact number of terms, or maximum number termNumberChoice.addItem("Any number of terms"); termNumberChoice.addItem("Exact number of terms:"); termNumberChoice.addItem("Maximum number of terms:"); add(termNumberChoice); termNumberString="Any number of terms"; termNumberField = new TextField(7); // exact or maximum number of terms add (termNumberField); termMaxChoice = new Choice(); // 3 choices: no restriction on size of terms, // exact largest value, or maximum permitted value termMaxChoice.addItem("Any values for terms"); termMaxChoice.addItem("Largest term exactly:"); termMaxChoice.addItem("Each term no more than:"); add(termMaxChoice); termMaxString="Any values for terms"; termMaxField = new TextField(7); // exact or maximum value of largest term add (termMaxField); calculateButton = new Button("Calculate partitions"); add (calculateButton); messageField = new TextField(40); add (messageField); } ////////////////////////////////////////////////////////////////////////////// // action(Event,Object) method handle choices and buttons. // Java 1.0 way of doing things // Not very OOP public boolean action (Event evt, Object arg) { if (evt.target == distinctChoice) // record choice: Distinct terms or not? {distinctString = (String) arg; } else if (evt.target == termNumberChoice) // record choice: Constrain number of terms? {termNumberString = (String) arg; } else if (evt.target == termMaxChoice) // record choice: Constrain largest term? {termMaxString = (String) arg; } // now collect the numbers and check if all OK ... else if (evt.target == calculateButton) { try // check an integer {totalSum=Integer.parseInt(totalSumField.getText().trim()); if (totalSum<0) // check if negative {messageField.setText("Cannot calculate that"); return false; } } catch (Exception e) // if not an integer {messageField.setText("Cannot calculate that"); return false; } if (termNumberString=="Any number of terms") {termNumberField.setText(""); // blank if no restriction } else {try // check an integer {termNumber=Integer.parseInt(termNumberField.getText().trim()); if (termNumber<0) // check if negative {messageField.setText("Cannot calculate that"); return false; } } catch (Exception e) // if not an integer {messageField.setText("Cannot calculate that"); return false; } } if (termMaxString=="Any values for terms") {termMaxField.setText(""); // blank if no restriction } else {try // check an integer {termMax=Integer.parseInt(termMaxField.getText().trim()); if (termNumber<0) // check if negative {messageField.setText("Cannot calculate that"); return false; } } catch (Exception e) // if not an integer {messageField.setText("Cannot calculate that"); return false; } } // ... only reach here if all OK // then discover which of three choices chosen, 2x3x3=18 possibilities // then apply formulae (6 different methods) and return message if (distinctString=="Partitions of:") {if (termNumberString=="Any number of terms") {if (termMaxString=="Any values for terms") {messageField.setText(simpleQuickPartitions( totalSum)); return true; } else if (termMaxString=="Largest term exactly:") // can remove largest term {messageField.setText(oneConstraintPartitions( totalSum-termMax,termMax)); return true; } else if (termMaxString=="Each term no more than:") {messageField.setText(oneConstraintPartitions( totalSum,termMax)); return true; } } else if (termNumberString=="Exact number of terms:") // can subtract 1 from each term {if (termMaxString=="Any values for terms") {messageField.setText(oneConstraintPartitions( totalSum-termNumber,termNumber)); return true; } else if (termMaxString=="Largest term exactly:") {messageField.setText(twoConstraintPartitions( totalSum-termMax-termNumber+1, termNumber-1,termMax-1)); return true; } else if (termMaxString=="Each term no more than:") {messageField.setText(twoConstraintPartitions( totalSum-termNumber, termNumber,termMax-1)); return true; } } else if (termNumberString=="Maximum number of terms:") {if (termMaxString=="Any values for terms") {messageField.setText(oneConstraintPartitions( totalSum,termNumber)); return true; } else if (termMaxString=="Largest term exactly:") // can remove largest term {messageField.setText(twoConstraintPartitions( totalSum-termMax, termNumber-1,termMax)); return true; } else if (termMaxString=="Each term no more than:") {messageField.setText(twoConstraintPartitions( totalSum,termNumber,termMax)); return true; } } } else if (distinctString=="Partitions with distinct terms of:") {if (termNumberString=="Any number of terms") {if (termMaxString=="Any values for terms") {messageField.setText(oneConstraintTermsDistinctPartitions( totalSum,deTriangle(totalSum))); return true; } else if (termMaxString=="Largest term exactly:") // can remove largest term {messageField.setText(oneConstraintLimitDistinctPartitions( totalSum-termMax,termMax-1)); return true; } else if (termMaxString=="Each term no more than:") {messageField.setText(oneConstraintLimitDistinctPartitions( totalSum,termMax)); return true; } } else if (termNumberString=="Exact number of terms:") // can subtract termNumber,...,3,2,1 from terms {if (termMaxString=="Any values for terms") {messageField.setText(oneConstraintPartitions( totalSum-triangle(termNumber),termNumber)); return true; } else if (termMaxString=="Largest term exactly:") // can remove largest term {messageField.setText(twoConstraintPartitions( totalSum-termMax-triangle(termNumber-1), termNumber-1,termMax-termNumber)); return true; } else if (termMaxString=="Each term no more than:") {messageField.setText(twoConstraintPartitions( totalSum-triangle(termNumber), termNumber,termMax-termNumber)); return true; } } else if (termNumberString=="Maximum number of terms:") {if (termMaxString=="Any values for terms") {messageField.setText(oneConstraintTermsDistinctPartitions( totalSum,termNumber)); return true; } else if (termMaxString=="Largest term exactly:") // can remove largest term {messageField.setText(twoConstraintDistinctPartitions( totalSum-termMax,termNumber-1,termMax-1)); return true; } else if (termMaxString=="Each term no more than:") {messageField.setText(twoConstraintDistinctPartitions( totalSum,termNumber,termMax)); return true; }// end of else if (termMaxString=="Each term no more than:") } // end of else if (termNumberString=="Maximum number of terms:") } // end of else if (distinctString== // "Partitions with distinct terms of:") else if (distinctString=="Compositions of:") {if (termNumberString=="Any number of terms") {if (termMaxString=="Any values for terms") // powers of 2 {messageField.setText(simpleCompositions( totalSum)); return true; } else if (termMaxString=="Largest term exactly:") // use difference {BigInteger first=new BigInteger(oneConstraintLimitCompositions( totalSum,termMax)); BigInteger second=new BigInteger(oneConstraintLimitCompositions( totalSum,termMax-1)); messageField.setText(first.subtract(second).toString()); return true; } else if (termMaxString=="Each term no more than:") {messageField.setText(oneConstraintLimitCompositions( totalSum,termMax) ); return true; } } else if (termNumberString=="Exact number of terms:") {if (termMaxString=="Any values for terms") // Combinations {messageField.setText(oneConstraintTermsCompositions( totalSum,termNumber)); return true; } else if (termMaxString=="Largest term exactly:") // use differences {BigInteger first=new BigInteger(twoConstraintCompositions(totalSum, termNumber,termMax,true)); BigInteger second=new BigInteger(twoConstraintCompositions(totalSum, termNumber,termMax-1,true)); messageField.setText(first.subtract(second).toString()); return true; } else if (termMaxString=="Each term no more than:") {messageField.setText(twoConstraintCompositions( totalSum,termNumber,termMax,true)); return true; } } else if (termNumberString=="Maximum number of terms:") {if (termMaxString=="Any values for terms") // Combinations partial sum {messageField.setText(oneConstraintTermsCompositionsSum( totalSum,termNumber)); return true; } else if (termMaxString=="Largest term exactly:") // use differences {BigInteger first=new BigInteger(twoConstraintCompositions(totalSum, termNumber,termMax,false)); BigInteger second=new BigInteger(twoConstraintCompositions(totalSum, termNumber,termMax-1,false)); messageField.setText(first.subtract(second).toString()); return true; } else if (termMaxString=="Each term no more than:") {messageField.setText(twoConstraintCompositions( totalSum,termNumber,termMax,false)); return true; }// end of else if (termMaxString=="Each term no more than:") } // end of else if (termNumberString=="Maximum number of terms:") } // end of else if (distinctString=="Compositions of:") else if (distinctString=="Compositions with distinct terms of:") {if (termNumberString=="Any number of terms") {if (termMaxString=="Any values for terms") // powers of 2 {messageField.setText(oneConstraintTermsDistinctCompositions( totalSum,deTriangle(totalSum))); return true; } else if (termMaxString=="Largest term exactly:") {messageField.setText(twoConstraintDistinctCompositions(totalSum, deTriangle(totalSum),termMax,true)); return true; } else if (termMaxString=="Each term no more than:") {messageField.setText(twoConstraintDistinctCompositions(totalSum, deTriangle(totalSum),termMax,false)); return true; } } else if (termNumberString=="Exact number of terms:") // can subtract termNumber,...,3,2,1 from terms // and multiply by factorial of termNumber {if (termMaxString=="Any values for terms") {BigInteger first=new BigInteger(oneConstraintPartitions( totalSum-triangle(termNumber),termNumber)); messageField.setText(first.multiply(factBI(termNumber)).toString()); return true; } else if (termMaxString=="Largest term exactly:") // can remove largest term {BigInteger first=new BigInteger(twoConstraintPartitions( totalSum-termMax-triangle(termNumber-1), termNumber-1,termMax-termNumber)); messageField.setText(first.multiply(factBI(termNumber)).toString()); return true; } else if (termMaxString=="Each term no more than:") {BigInteger first=new BigInteger(twoConstraintPartitions( totalSum-triangle(termNumber), termNumber,termMax-termNumber)); messageField.setText(first.multiply(factBI(termNumber)).toString()); return true; } } else if (termNumberString=="Maximum number of terms:") {if (termMaxString=="Any values for terms") // Combinations partial sum {messageField.setText(oneConstraintTermsDistinctCompositions( totalSum,termNumber)); return true; } else if (termMaxString=="Largest term exactly:") // use differences {messageField.setText(twoConstraintDistinctCompositions(totalSum, termNumber,termMax,true)); return true; } else if (termMaxString=="Each term no more than:") {messageField.setText(twoConstraintDistinctCompositions(totalSum, termNumber,termMax,false)); return true; }// end of else if (termMaxString=="Each term no more than:") } // end of else if (termNumberString=="Maximum number of terms:") } // end of else if (distinctString== // "Compositions with distinct terms of:") } // end of calculateBotton return false; // if reach here then nothing interesting happening } // end of action (Event evt, Object arg) method //////////////////////////////////////////////////////////// // Simple method to save typing ... // public int triangle(int x) {return ((x*(x+1))/2); } ////////////////////////////////////////////////////////////// // ... and its inverse method since x==deTriangle(triangle(x)) // public int deTriangle(int x) {return (int) (((int) Math.sqrt(8*x+1)-1)/2); // overkill on the (int)? //return (int) (((int) Math.sqrt(8*x+1)+1)/2); // overkill on the (int)? } ////////////////////////////////////////////////////////////// // BigInteger factorial method // public BigInteger factBI(int terms) {if (terms<0) {return BigInteger.valueOf(0l); } BigInteger factorial=BigInteger.valueOf(1l); for (int j=1; j<=terms; j++) {factorial=factorial.multiply(BigInteger.valueOf(j)); } return factorial; } ////////////////////////////////////////////////////////////////////////// // First of the key methods: // simpleQuickPartitions(int) // uses recurrance on generalised pentagonal numbers // to calculate ordinary partition numbers quickly // public String simpleQuickPartitions (int total) {if (total<0) // no partitions in such a useless case {return "0"; } int dePent = (int) Math.sqrt(1.0d+total); int signArray[] = new int[2*dePent+2]; int pentArray[] = new int[2*dePent+2]; signArray[0]=-1; signArray[1]=1; pentArray[0]=0; pentArray[1]=1; for (int i=1; i<=depent; i++) {signArray[2*i]=-signArray[2*i-2]; signArray[2*i+1]=-signArray[2*i-1]; pentArray[2*i]=(i*(3*i+1))/2; pentArray[2*i+1]=((i+1)*(3*i+2))/2; } BigInteger partitionArray[] = new BigInteger[total+1]; partitionArray[0]=BigInteger.valueOf(1l); for (int j=1; j<=total; j++) {BigInteger partSum=BigInteger.valueOf(0l); for (int k=1; pentArray[k]<=j; k++) {if (signArray[k]==1) {partSum = partSum.add(partitionArray[j-pentArray[k]]); } else {partSum = partSum.subtract(partitionArray[j-pentArray[k]]); } } messageField.setText(Integer.toString(j)); partitionArray[j] = partSum; } // end of j loop return partitionArray[total].toString(); } // end of simpleQuickPartitions ////////////////////////////////////////////////////////////////////////// // Second of the key methods: // oneConstraintPartitions(int,int) // to calculate ordinary partition numbers if there is a constraint // (either all terms less than or equal to "limit" // or no more than "limit" number of terms) // public String oneConstraintPartitions (int total, int limit) {if (limit>=total) // can save some time especially if total is big {return simpleQuickPartitions(total); } if (total<0 || limit<0) // useless total or limit {return "0"; } BigInteger partitionArray[] = new BigInteger[total+1]; partitionArray[0]=BigInteger.valueOf(1l); for (int k=1; k<=total; k++) {partitionArray[k]=BigInteger.valueOf(0l); } for (int j=1; j<=limit; j++) {for (int k=j; k<=total; k++) // note the subtle differences {partitionArray[k]=partitionArray[k].add(partitionArray[k-j]); } // end of k loop messageField.setText(Integer.toString(j)); } // end of j loop return partitionArray[total].toString(); } // end of oneConstraintPartitions method ////////////////////////////////////////////////////////////////////////// // Third of the key methods: // twoConstraintPartitions(int,int,int) // to calculate ordinary partition numbers if there are two constraints // (both all terms less than or equal to "limit" // and no more than "terms" number of terms) // public String twoConstraintPartitions (int total, int terms, int limit) {if (total<0 || limit<0 || terms<0 || limit*terms=total) // limit not really a constraint {return oneConstraintPartitions(total,terms); } if (terms>=total) // terms not really a constraint {return oneConstraintPartitions(total,limit); } if (2*total>limit*terms) // result is symmetric about limit*terms/2 // so save time and memory {total=limit*terms-total; } if (terms=0; k--) {partitionArray[j][k]=BigInteger.valueOf(0l); } } partitionArray[0][0]=BigInteger.valueOf(1l); //... except for a single one. for (int i=0; i<=terms; i++) //Iteration starts here {for (int j=1; j<=limit; j++) //Need to increase to use previous values {for (int k=total; k>=i; k--) //Need to decrease to use previous values, //but does not change if k=j) {partitionArray[j][k]=partitionArray[j-1][k].add( partitionArray[j][k-j]); //the recurrence: //partitionArray[j-1][k] is new while //partitionArray[j][k-j] is old } else {partitionArray[j][k]=partitionArray[j-1][k]; // partitionArray[j][k-j] does not exist if j>k } // end of else } // end of k loop } // end of j loop messageField.setText(Integer.toString(i)); // to see what is going on } // end of i loop return partitionArray[limit][total].toString(); } // end of twoConstraintPartitions method ////////////////////////////////////////////////////////////////////////// // First of the methods for partitions into distinct terms: // oneConstraintTermsDistinctPartitions(int,int) // to calculate distinct partition numbers if there is a particular constraint // (no more than "terms" number of terms) // and can be used (with terms=deTriangle(total)) if no constraint // public String oneConstraintTermsDistinctPartitions (int total, int terms) {if (total<0 || terms<0) // useless total or terms {return "0"; } if (total==0) // simple, but will return 0 otherwise {return "1"; } if (triangle(terms)>total) // terms is in fact not a constraint // so make as small as possible {terms=deTriangle(total); } BigInteger partitionArray[] = new BigInteger[total+1]; partitionArray[0]=BigInteger.valueOf(1l); for (int k=1; k<=total; k++) {partitionArray[k]=BigInteger.valueOf(0l); } BigInteger partsumDistinct=BigInteger.valueOf(0l); for (int j=1; j<=terms; j++) {int jTriangle=triangle(j); for (int k=j; k<=total-jtriangle; k++) {partitionArray[k]=partitionArray[k].add(partitionArray[k-j]); } // end of k loop if (triangle(j)<=total) {partsumDistinct=partsumDistinct.add(partitionArray[total-jTriangle]); } // for some of the distinct terms calculations messageField.setText(Integer.toString(j)); } // end of j loop return partsumDistinct.toString(); } // end of oneConstraintTermsDistinctPartitions method ////////////////////////////////////////////////////////////////////////// // Second of the methods for partitions into distinct terms: // oneConstraintLimitDistinctPartitions(int,int) // to calculate distinct partition numbers if there is a particular constraint // (all terms less than or equal to "limit") // public String oneConstraintLimitDistinctPartitions (int total, int limit) {if (total<0 || limit<0 || triangle(limit)=total) // limit is in fact not a constraint {return oneConstraintTermsDistinctPartitions(total,deTriangle(total)); } BigInteger partitionArray[] = new BigInteger[total+1]; partitionArray[0]=BigInteger.valueOf(1l); for (int k=1; k<=total; k++) {partitionArray[k]=BigInteger.valueOf(0l); } for (int j=1; j<=limit; j++) {int ktop=triangle(j); if (total=j; k--) // note the subtle differences {partitionArray[k]=partitionArray[k].add(partitionArray[k-j]); } // end of k loop messageField.setText(Integer.toString(j)); } // end of j loop return partitionArray[total].toString(); } // end of oneConstraintLimitDistinctPartitions method ////////////////////////////////////////////////////////////////////////// // Third of the methods for partitions into distinct terms: // twoConstraintDistinctPartitions(int,int,int) // to calculate distinct partition numbers if there are two constraints // (both all terms less than or equal to "limit" // and no more than "terms" number of terms) // public String twoConstraintDistinctPartitions (int total, int terms, int limit) {if (triangle(terms)>=total || terms>=limit) // terms is in fact not a constraint {return oneConstraintLimitDistinctPartitions(total,limit); } if (limit>=total) // limit is in fact not a constraint {return oneConstraintTermsDistinctPartitions(total,terms); } if (total<0 || limit<0 || terms<0 || triangle(limit)-triangle(limit-terms)=0; k--) {partitionArray[j][k]=BigInteger.valueOf(0l); //start with all zero, ... } } partitionArray[0][0]=BigInteger.valueOf(1l); //... except for a single one. BigInteger partsumDistinct=BigInteger.valueOf(0l); // to start a sum for (int i=0; i<=terms; i++) //Iteration starts here {for (int j=1; j<=limit-i; j++) //Need to increase to use //previous values {for (int k=total-triangle(i); k>=i; k--) //Need to decrease to use //previous values, //but does not change if k=j) {partitionArray[j][k]=partitionArray[j-1][k].add( partitionArray[j][k-j]); //the recurrence: // partitionArray[j-1][k] is new // while partitionArray[j][k-j] is old } else {partitionArray[j][k]=partitionArray[j-1][k]; // partitionArray[j][k-j] does not exist if j>k } // end of else } // end of k loop } // end of j loop partsumDistinct=partsumDistinct.add( partitionArray[limit-i][total-triangle(i)]); //what we are aiming for messageField.setText(Integer.toString(i)); // to see what is going on } // end of i loop return partsumDistinct.toString(); } // end of twoConstraintDistinctPartitions method ////////////////////////////////////////////////////////////////////////// // First of the Composition methods: // simpleCompositions(int) // uses powers of 2 // public String simpleCompositions (int total) {if (total<0) // no compositions in such a useless case {return "0"; } if (total==0) {return "1"; } return BigInteger.valueOf(2l).pow(total-1).toString(); } // end of simpleCompositions method ////////////////////////////////////////////////////////////////////////// // Second of the Composition methods: // oneConstraintLimitCompositions(int,int) // number of Compositions of total each term no more than limit // uses Multi-nacci // public String oneConstraintLimitCompositions(int total,int limit) {if (total<0) // no compositions in such a useless case {return "0"; } if (total==0) // empty composition in such a case {return "1"; } if (limit<=0) // no compositions in such a useless case {return "0"; } if (limit>=total) // limit is in fact not a constraint {return simpleCompositions(total); } BigInteger compositionArray[] = new BigInteger[total+1]; compositionArray[0]=BigInteger.valueOf(1l); for (int k=1; k<=limit; k++) {compositionArray[k]=BigInteger.valueOf(2l).pow(k-1); } for (int k=limit+1; k<=total; k++) {compositionArray[k]=compositionArray[k-1].add( compositionArray[k-1].subtract( compositionArray[k-1-limit] )); messageField.setText(Integer.toString(k)); // to see what is going on } return compositionArray[total].toString(); } // end of oneConstraintLimitCompositions method ////////////////////////////////////////////////////////////////////////// // Third of the Composition methods: // oneConstraintTermsCompositions(int,int) // number of Compositions of total with exact number of terms // essentially combinations C(total-1,terms-1) // public String oneConstraintTermsCompositions(int total,int terms) {if (total<0) // no compositions in such a useless case {return "0"; } if (total==terms) // single composition in such a case {return "1"; } if (terms*2>total) // combinations are symmetric {terms=1+total-terms; } if (terms<=0) // no compositions in such useless cases {return "0"; } if (terms==1) // single composition in such a case {return "1"; } BigInteger combination=BigInteger.valueOf(1l); for (int k=1; k=0) // single composition in such a case {return "1"; } if (terms>=total) // terms is in fact not a constraint {return simpleCompositions(total); } if (terms<=0) // no compositions in such useless cases {return "0"; } if (terms==1) // single composition in such a case {return "1"; } BigInteger combination=BigInteger.valueOf(1l); BigInteger combinationSum=BigInteger.valueOf(1l); for (int k=1; k 0 ) || (total> terms*limit) || (terms>total && exactTerms==true)) // no compositions in such a useless case {return "0"; } if ((total==0 && terms==0 && exactTerms==true && limit>=0 ) || (total==0 && terms>=0 && exactTerms==false && limit>=0 ) || (total==terms && exactTerms==true && limit>=1 ) || (total==terms*limit) ) // single composition {return "1"; } if (limit>=total) // limit is in fact not a constraint {if (exactTerms==true) {return oneConstraintTermsCompositions(total,terms); } else {return oneConstraintTermsCompositionsSum(total,terms); } } if (terms>=total) // terms is not in fact a constraint (and we have exactTerms false) {return oneConstraintLimitCompositions(total,limit); } BigInteger compositionArray[][] = new BigInteger[total+limit+1][terms+1]; for (int i=0; itotal) // terms is in fact not a constraint // so make as small as possible {terms=deTriangle(total); } BigInteger compositionArray[] = new BigInteger[total+1]; compositionArray[0]=BigInteger.valueOf(1l); for (int k=1; k<=total; k++) {compositionArray[k]=BigInteger.valueOf(0l); } BigInteger partsumDistinct=BigInteger.valueOf(0l); BigInteger factorial=BigInteger.valueOf(1l); for (int j=1; j<=terms; j++) {int jTriangle=triangle(j); factorial=factorial.multiply(BigInteger.valueOf(j)); for (int k=j; k<=total-jtriangle; k++) {compositionArray[k]=compositionArray[k].add(compositionArray[k-j]); } // end of k loop if (triangle(j)<=total) {partsumDistinct=partsumDistinct.add( compositionArray[total-jTriangle].multiply( factorial )); } // for some of the distinct terms calculations messageField.setText(Integer.toString(j)); } // end of j loop return partsumDistinct.toString(); } // end of oneConstraintTermsDistinctCompositions method ////////////////////////////////////////////////////////////////////////// // Second of the methods for compositions into distinct terms: // twoConstraintDistinctCompositions(int,int,int,boolean) // to calculate distinct compositions numbers if there are two constraints // (no more than "terms" number of terms and no term bigger than or equal to "limit") // and can be used (with terms=deTriangle(total)) if no terms constraint // based on partitions equivalent but rewritten // public String twoConstraintDistinctCompositions (int total,int terms,int limit, boolean exactLimit) {if (terms>limit) // for distinct parts, cannot have more parts than max term {terms=limit; } if (total<0 || limit<0 || terms<0 || triangle(limit)-triangle(limit-terms)=total) {if (exactLimit==true) {if (limit==total) {return "1"; } return "0"; } return oneConstraintTermsDistinctCompositions(total,terms); } if (triangle(terms)>total) {terms=deTriangle(total); } if (total==0) {return "1"; } BigInteger compositionArray[][] = new BigInteger[limit+1][total+1]; // this is large and growing and a potential memory problem for (int j=0; j<=limit; j++) {for (int k=total; k>=0; k--) {compositionArray[j][k]=BigInteger.valueOf(0l); //start with all zero, ... } } compositionArray[0][0]=BigInteger.valueOf(1l); //... except for a single one. BigInteger factorial=BigInteger.valueOf(1l); BigInteger partsumDistinct=BigInteger.valueOf(0l); // to start a sum for (int i=0; i<=terms; i++) //Iteration starts here {if (i>0) {factorial=factorial.multiply(BigInteger.valueOf(i)); } for (int j=1; j<=limit-i; j++) //Need to increase to use //previous values {for (int k=total-triangle(i); k>=i; k--) //Need to decrease to use //previous values, //but does not change if k=j) {compositionArray[j][k]=compositionArray[j-1][k].add( compositionArray[j][k-j]); //the recurrence: // compositionArray[j-1][k] is new // while compositionArray[j][k-j] is old } else {compositionArray[j][k]=compositionArray[j-1][k]; // compositionArray[j][k-j] does not exist if j>k } // end of else } // end of k loop } // end of j loop partsumDistinct=partsumDistinct.add( compositionArray[limit-i][total-triangle(i)].multiply( factorial)); //what we are aiming for if (exactLimit==true && i

AltStyle によって変換されたページ (->オリジナル) /