StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I realize that everyone's beaten me to the punch at this point, but here's a dumb Java algorithm (pretty close to C# syntactically that you can try out).</p> <pre><code>import java.util.ArrayList; import java.util.List; /** * The operational complexity of this is pretty poor and I'm sure you'll be able to optimize * it, but here's something to get you started at least. */ public class Recurse { /** * Base method to set up your recursion and get it started * * @param start The total number that digits from all the days will sum up to * @param days The number of days to split the "start" value across (e.g. 5 days equals * 5 columns of output) */ private static void getNumber(int start,int days) { //start recursing printOrderings(start,days,new ArrayList<Integer>(start)); } /** * So this is a pretty dumb recursion. I stole code from a string permutation algorithm that I wrote awhile back. So the * basic idea to begin with was if you had the string "abc", you wanted to print out all the possible permutations of doing that * ("abc","acb","bac","bca","cab","cba"). So you could view your problem in a similar fashion...if "start" is equal to "5" and * days is equal to "4" then that means you're looking for all the possible permutations of (0,1,2,3,4,5) that fit into 4 columns. You have * the extra restriction that when you find a permutation that works, the digits in the permutation must add up to "start" (so for instance * [0,0,3,2] is cool, but [0,1,3,3] is not). You can begin to see why this is a dumb algorithm because it currently just considers all * available permutations and keeps the ones that add up to "start". If you want to optimize it more, you could keep a running "sum" of * the current contents of the list and either break your loop when it's greater than "start". * * Essentially the way you get all the permutations is to have the recursion choose a new digit at each level until you have a full * string (or a value for each "day" in your case). It's just like nesting for loops, but the for loop actually only gets written * once because the nesting is done by each subsequent call to the recursive function. * * @param start The total number that digits from all the days will sum up to * @param days The number of days to split the "start" value across (e.g. 5 days equals * 5 columns of output) * @param chosen The current permutation at any point in time, may contain between 0 and "days" numbers. */ private static void printOrderings(int start,int days,List<Integer> chosen) { if(chosen.size() == days) { int sum = 0; for(Integer i : chosen) { sum += i.intValue(); } if(sum == start) { System.out.println(chosen.toString()); } return; } else if(chosen.size() < days) { for(int i=0; i < start; i++) { if(chosen.size() >= days) { break; } List<Integer> newChosen = new ArrayList<Integer>(chosen); newChosen.add(i); printOrderings(start,days,newChosen); } } } public static void main(final String[] args) { //your equivalent of GetNumber4(5) getNumber(5,4); //your equivalent of GetNumber5(5) getNumber(5,5); } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload