Recursion problem with limited results

Question

I am having trouble resolving this issue; it haunted me from yesterday (sorry, I posted it earlier and then deleted it because I decided I decided, but it turned out to be another mistake that I fixed). I'm trying to just take a list of elements and a range and find combinations that allow all elements to be used.

Here is an example: imagine that you have 4 items (apple, pear, peach and orange) and want a minimum of 20% of the basket to contain their maximum and 60%. For example, you can have 25%, 25%, 25%, 25% of each item or 30%, 30%, 20%, 20%, etc., but 0%, 0%, 50%, 50% because the specified minus% is 20%.

The program works fine, but it uses elements less than the entire list (instead of 4 elements in each solution, some solutions contain 2 or 3 elements, which is not what I want). If I send a list of 4 items, I want the combinations to be used for all 4 items and no less. I do not want this because I plan to use large lists, and I want the size to be an element that was used only for everyone, and not less than min%. Here is an example of using the above information (4 elements, range 20-60%):

good: apples = 22 pears = 24 peach = 25 orange = 29 total: 100% bad: apples = 0 pears = 0 peach = 40 orange = 60 total: 100% // Although total is correct, the example fails because // the minimum of 20% per item was not obeyed. 

I am really confused why this is happening, but if I had to bet, I would have thought that my recursion takes the number of elements in the list and subtracts them before sending them back. Its in the recursion_part method:

 private static void recursion_part(int k, int sum, int[] coeff) { //k is number of items in the list(in this example its 4(0-3), sum is the remaining total percent to break down, coeff is the template to store values //this recursively takes the sum and tries to find lower values of it until it equals zero using the bounds given for (int c = low_bound[k]; c <= high_bound[k]; c++) { coeff[k] = c; int[] newcoeff = Arrays.copyOf(coeff, coeff.length); if (c - sum == 0) { results.add(newcoeff); printresults(newcoeff); break; } else if (k > 0) { recursion_part(k - 1, sum - c, newcoeff); } } } 

I want to work on larger lists, and I think this will be a problem if it calculates a lot of results that I don't need. How can I redo this to handle all the items in the list and stay within the range?

I thought about putting a method that checks how many zeros are in the list, and then breaks if it goes below the size of the list, but the fact that I get empty results means that its processing elements are smaller than my list and I I think it’s better to develop a program so that it does not waste resources.

Here's the whole code (it works as described, but gives zero results, as indicated):

 import java.util.ArrayList; import java.util.Arrays; public class recursion_percent_returner { static final int target_percent = 100; static final String[] names = new String[] {"apples", "pears", "peach", "orange" }; static int[] low_bound = new int[names.length]; static int[] high_bound = new int[names.length]; static ArrayList results = new ArrayList(); //queue to store results static int[] default_coeff = new int[names.length]; public static void main(String[] args) { System.out.println("starting.."); System.out.println("list size " + names.length); Arrays.fill(low_bound, 20); //fills the min list with default value Arrays.fill(high_bound, 60); //fills the max list with default value recursion_part(names.length-1,target_percent,default_coeff); System.out.println("total size of results are " + results.size()); } private static void recursion_part(int k, int sum, int[] coeff) { //k is number of items in the list(in this example its 4(0-3), sum is the remaining total percent to break down, coeff is the template to store values //this recursively takes the sum and tries to find lower values of it until it equals zero using the bounds given for (int c = low_bound[k]; c <= high_bound[k]; c++) { coeff[k] = c; int[] newcoeff = Arrays.copyOf(coeff, coeff.length); if (c - sum == 0) { results.add(newcoeff); printresults(newcoeff); break; } else if (k > 0) { recursion_part(k - 1, sum - c, newcoeff); } } } private static void printresults(int[] newcoeff) { for (int x = 0; x<newcoeff.length; x++) { System.out.println(names[x] + " = " + newcoeff[x]); } System.out.println("*********"); } } 

Thank you, and if there is a better way to achieve the result I'm looking for, please let me know.

ps this is not homework, and I am not a student; I just have a tendency to find strange problems with proxies.

Change I have included all the code, but here is also the output . This is a fragment of solutions 2653 that generates more than I need. If you look at this briefly, you will see that most of them are correct, but as you get lower, you will see that not all values ​​are used; I need only solutions that use all values; there should not be 0 record values.

Answer 1

 import java.util.*; public class Distributor { private ArrayList<int[]> result = new ArrayList <int[]> (); public Distributor (final String [] names, int [] low, int [] high) { final int rest = 10; int minimum = 0; for (int l : low) minimum += l; int [] sizes = new int [names.length]; distribute (0, low, high, rest - minimum, sizes); System.out.println ("total size of results are " + result.size ()); for (int [] ia : result) show (ia, low); } public static void main (String [] args) { final String [] names = new String [] {"a", "b", "c"}; int [] low = new int [] {2, 2, 1}; int [] high = new int [] {3, 4, 6}; new Distributor (names, low, high); } /* distribute the rest of values over the elements in sizes, beginning with index i. */ void distribute (int i, int [] low, int [] high, final int rest, int [] sizes) { // System.out.println (i + " " + rest + " " + sizes); if (i == sizes.length - 1) { if (rest < high [i]) { sizes[i] = rest; result.add (Arrays.copyOf (sizes, sizes.length)); } } else for (int c = 0; c <= java.lang.Math.min (high [i] - low [i], rest); ++c) { sizes [i] = c; distribute (i + 1, low, high, rest - c, sizes); } } private static void show (int [] arr, int [] low) { for (int x = 0; x < arr.length; x++) { System.out.print (" " + (arr [x] + low[x])); } System.out.println (); } } 

Long variable names are better if they are clearer than short ones. But they are no more valuable in themselves.

Also: stick with namingConventions, which are CamelCase in Java, not_funky_underlines.

Good - why should there be a low and high static? I did not work in this direction for “names” and “results”. Remains as an exercise to remove the static modifier.

Well, I got the impression that the amount should always be 100, no less than no more than 100. So if 4x20% is the minimum, a maximum of 60% is impossible. But I understand that the values ​​are variables, and in other settings you can have a minimum of 4x10%, and then a maximum of 60% will make sense. I have not tested the code for this purpose.

But I subtract a minimum (4 * 20%) from the rest to distribute, so you need to add these values ​​for the final result.

The recursive distribution function begins with the termination condition: The last element is reached. Now the rest - how much it can be - needs to be placed for this last element.

Otherwise, you take all possible values ​​for this element and distribute the rest.

update:

I changed the code to take care of the upper limit, and simplified the example on the one hand, since now it uses only 3 elements and a maximum of 10 instead of 100. The output shows the real values ​​(min + variable part), and the algorithm only adds solutions that Do not violate the restriction from above.

Output Example:

  2 2 6 2 3 5 2 4 4 3 2 5 3 3 4 3 4 3 total size of results are 6