3

I have 12 products at a blend plant (call them a - l) and need to generate varying percentages of them, the total obviously adding up to 100%.

Something simple such as the code below will work, however it is highly inefficient. Is there a more efficient algorithm?

*Edit: As mentioned below there are just too many possibilities compute, efficiently or not. I will change this to only having a maximum of 5 or the 12 products in a blend and then running it against the number of ways that 5 products can be chosen from the 12 products.

There is Python code that some of you have pointed to that seems to work out the possibilities from the combinations. However my Python is minimal (ie 0%), would one of you be able to explain this in Java terms? I can get the combinations in Java (http://www.cs.colostate.edu/~cs161/Fall12/lecture-codes/Subsets.java)

public class Main {


public static void main(String[] args) throws FileNotFoundException, UnsupportedEncodingException {


   for(int a=0;a<=100;a++){
        for(int b=0;b<=100;b++){
             for(int c=0;c<=100;c++){
                 for(int d=0;d<=100;d++){
                     for(int e=0;e<=100;e++){
                          for(int f=0;f<=100;f++){
                                for(int g=0;g<=100;g++){
                                   for(int h=0;h<=100;h++){
                                       for(int i=0;i<=100;i++){
                                            for(int j=0;j<=100;j++){
                                               for(int k=0;k<=100;k++){
                                                      for(int l=0;l<=100;l++){

                                                    if(a+b+c+d+e+f+g+h+i+j+k+l==100)

                                                      {

                                            System.out.println(a+" "+b+" "+c+" "+d+" "+e+" "+f+" "+g+" "+h+" "+i+" "+j+" "+k+" "+l);



       }}}}}}}}}}}}}

}

}

0idani0
  • 39
  • 3
  • 2
    I'm wondering how would this code produce `FileNotFoundException` and `UnsupportedEncodingException`. – devnull Aug 28 '13 at 17:01
  • for for for for for for for for for for for for – user1231232141214124 Aug 28 '13 at 17:01
  • 1
    Maybe this would help: http://en.wikipedia.org/wiki/Knapsack_problem – NeplatnyUdaj Aug 28 '13 at 17:03
  • Obviously you could skip some inner loops with checks like `if(a=100)` and 'if(a+b>=100)`, etc.. – lreeder Aug 28 '13 at 17:04
  • 1
    Not that I support 12 nested loops... `for(int b=0;b<=100-a;b++) for(int c=0;c<=100-a-b;c++) ...` (or something like that) – Bernhard Barker Aug 28 '13 at 17:07
  • 3
    By my count, there are about four hundred trillion ways to add up 12 numbers to get 100, assuming order matters. Are you sure you need to go through all of them? – Kevin Aug 28 '13 at 17:10
  • Can two or more products have the same percentage in one combination (e.g., `2%, 2%, 2%, 5%, 15%, 33%...etc.`)? – גלעד ברקן Aug 28 '13 at 18:15
  • http://en.wikipedia.org/wiki/Partition_(number_theory) – Lee Daniel Crocker Aug 28 '13 at 18:20
  • The FileNotFoundException and UnsupportedEncodingException are not needed, they are relics of when I was going to write all the combinations to a file so I would only have to run the nested loop once...Which I quickly gave up on as the file gets unfeasibly big fast I do not need to store all the results as I am only interested in the most efficient blend, however to calculate the most efficient blend I have to run through all combinations... – 0idani0 Aug 28 '13 at 18:32
  • Unfortunately some of the parameters such as flashpoint/viscosity are non-linear and Excels Solver which uses Newtons Method kept finding local minimums instead of the global minimum for cost. Hence I now want to try and brute force it. Groovy: yes they can have the same percentages. They can also be 0 so long as the total adds up to 100 – 0idani0 Aug 28 '13 at 18:33
  • Ummm... percentages are real numbers. That means there are an infinite number of combinations. Or is your plant only able to do whole-number percentages? That means there are 100^11 = 10 billion trillion combinations. No algorithm will ever enumerate all of them. I think you need to rethink your problem. – JoshG79 Aug 28 '13 at 18:36
  • Yes integer percentages. I agree, would it reduce the time considerably if we never used more than say 5 products in a blend? Then it would effectively become something like (12C5)*(That big for loop 5 layers deep)? – 0idani0 Aug 28 '13 at 18:56
  • @0idani0: Yes, reducing the number of products would greatly reduce runtime, since it's basically O(n^m), or O(100^12), it would be reduced to O(100^5) – Seth Moore Aug 28 '13 at 20:15

4 Answers4

1

Why make it so difficult. Think simple way.

To explain the scenario simpler, consider 5 numbers to be generated randomly. Pseudo-code should be something like below.

  1. Generate 5 random number, R1, R2 ... R5
  2. total = sum of those 5 random number.
  3. For all item to produce
    • produce1 = R1/total; // produce[i] = R[i]/total;
Kowser
  • 8,123
  • 7
  • 40
  • 63
  • How does generating random numbers guarantee all combinations? would you be able to elaborate? – 0idani0 Aug 28 '13 at 18:58
  • For `Independent Probability` it should follow 3 rule and which above does perfectly. You may want to google for [3 basic rules of probability][1] [1]: https://www.google.com/search?q=probability%20rule%203&oq=probability%203%20ru&aqs=chrome.1.69i57j0l3.13153j0&sourceid=chrome&ie=UTF-8&qscrl=1#fp=aa28161d8f351b8&q=3%20basic%20rules%20of%20probability&qscrl=1&safe=off – Kowser Aug 28 '13 at 20:38
  • It should easy to understand. – Kowser Aug 28 '13 at 20:40
  • Any reason for downvote? At least I can improve myself. – Kowser Aug 28 '13 at 22:50
0

Please, don't use nested for loops that deep! Use recursion instead:

public static void main(String[] args) {
    int N = 12;
    int goal = 100; 

    generate(N, 0, goal, new int[N]);
}

public static void generate(int i, int sum, int goal, int[] result) {
    if (i == 1) {
        // one number to go, so make it fit
        result[0] = goal - sum;
        System.out.println(Arrays.toString(result));
    } else {
        // try all possible values for this step
        for (int j = 0; j < goal - sum; j++) {
            // set next number of the result
            result[i-1] = j;
            // go to next step
            generate(i-1, sum + j , goal, result);
        }
    }
}

Note that I only tested this for N = 3 and goal = 5. It absolutely makes no sense to try generating all these possibilities (and would take forever to compute).

Vincent van der Weele
  • 12,927
  • 1
  • 33
  • 61
  • This algorithm violates the required probability constraint. It breaks while calculating last item. Last item is not randomly chosen. – Kowser Aug 28 '13 at 17:33
  • But recursion definitely would be a more elegant solution to the problem –  Aug 28 '13 at 17:35
  • @Kowser there is no probability at all in a deterministic algorithm. I generate **all** possible distributions, which is equivalent to the OP's code. Can you point out where it was mentioned that we need to generate one solution uniformly at random? – Vincent van der Weele Aug 28 '13 at 17:54
0
for(int a=0;a<=100;a++){
    for(int b=0;b<=50;b++){
         for(int c=0;c<=34;c++){
             for(int d=0;d<=25;d++){
                 for(int e=0;e<=20;e++){
                      for(int f=0;f<=17;f++){
                            for(int g=0;g<=15;g++){
                               for(int h=0;h<=13;h++){
                                   for(int i=0;i<=12;i++){
                                        for(int j=0;j<=10;j++){
                                           for(int k=0;k<=10;k++){
                                                  for(int l=0;l<=9;l++){

                                                if(a+b+c+d+e+f+g+h+i+j+k+l==100)

                                                  {

                                                // run 12 for loops for arranging the  
                                                // 12 obtained numbers at all 12 places      


   }}}}}}}}}}}}}

In Original approach(permutation based), the iterations were 102^12 = 1.268e24. Even though the 102th iteration was false, it did check the loop terminating condition for 102th time. So you had 102^12 condition checks in "for" loops, in addition to "if" condition checks 101^12 times, so in total, 2.4e24 condition checks.

In my solution(combination based),No of for loop checks reduces to 6.243e15 for outer 12 loops, &
if condition checks = 6.243e15. Now, the no of for loops(ie inner 12 for loops) for every true "if" condition, is 12^12 = 8.9e12. Let there be x number of true if conditions. so total condition checks

=no of inner for loops*x

= 8.9e12 * x + 6.243e15

I'm not able to find the value of x. however, I believe it wouldnt be large enough to make total conditon checks greater than 2.4e24

Sumedh
  • 404
  • 3
  • 11
  • But couldn't you have 0% for the first 11 products and 100% for the 12th "product"? – Seth Moore Aug 28 '13 at 18:24
  • Sorry, the answer was incorrect, so I've edited it. Pl check now Also, the range for a,b,c... is upto 100/1,100/2,100/3...& 100/12 – Sumedh Aug 28 '13 at 18:33
0

Let's take your comment that you can only have 5 elements in a combination, and the other 7 are 0%. Try this:

for (i = 0; i < (1<<12); ++i) {
    if (count_number_of_1s(i) != 5) { continue; }
    for (j = 0; j < 100000000; ++j) {
       int [] perc = new int[12];
       int val = j;
       int sum = 0;
       int cnt = 0;
       for (k = 0; k < 12; ++k) {
         if (i & (1 << k)) {
            cnt++;
            if (cnt == 5) {
              perc[k] = 100 - sum;
            }
            else {
              perc[k] = val % 100;
              val /= 100;
            }
            sum += perc[k];
            if (sum > 100) { break; }
         }
         else { perc[k] = 0; }
       }
       if (sum == 100) {
         System.out.println(perc[0] + ...);
       }
    }
}

The outer loop iterates over all possible combinations of using 12 items. You can do this by looping over all numbers from 1:2^12, and the 1s in the binary representation of that number are the elements you're using. The count_number_of_1s is a function that loops over all the bits in the parameter and returns the number of 1s. If this is not 5, then just skip this iteration because you said you only want at most 5 mixed. (There are 792 such cases).

The j loop is looping over all the combinations of 4 (not 5) items from 0:100. There are 100^4 such cases.

The inner loop is looping over all 12 variables, and for those that have a 1 in their bit-position in i, then it means you're using that one. You compute the percentage by taking the next two decimal digits from j. For the 5th item (cnt==5), you don't take digits, you compute it by subtracting from 100.

This will take a LONG time (minutes), but it won't be nearly as bad as 12 nested loops.

JoshG79
  • 1,685
  • 11
  • 14