title: Reduce time complexity of a program (in Java)?
body: <p>This question is quite a long shot. It could take quite long, so if you haven't the time I understand.</p>
  
  <p>Let me start by explaining what I want to achieve:
  Me and some friends play this math game where we get 6 random numbers out of a pool of possible numbers: 1 to 10, 25, 50, 75 and 100. 6 numbers are chosen out of these and no duplicates are allowed. Then a goal number will be chosen in the range of [100, 999]. With the 6 aforementioned numbers, we can use only basic operations (addition, subtraction, multiplication and division) to reach the goal. Only integers are allowed and not all 6 integers are required to reach the solution.</p>
  
  <p>An example: We start with the numbers 4,8,6,9,25,100 and need to find 328.
  A possible solution would be: ((4 x 100) - (9 x 8)) = 400 - 72 = 328. With this, I have only used 4 out of the 6 initial numbers and none of the numbers have been used twice. This is a valid solution. </p>
  
  <p>We don't always find a solution on our own, that's why I figured a program would be useful. I have written a program (in Java) which has been tested a few times throughout and it had worked. It did not always give all the possible solutions, but it worked within its own limitations. Now I've tried to expand it so all the solutions would show.</p>
  
  <p>On to the main problem:
  The program that I am trying to execute is running incredibly long. As in, I would let it run for 15 minutes and it doesn't look like it's anywhere near completion. So I thought about it and the options are indeed quite endless. I start with 6 numbers, I compare the first with the other 5, then the second with the other 5 and so on until I've done this 6 times (and each comparison I compare with every operator, so 4 times again). Out of the original one single state of 6 numbers, I now have 5 times 6 times 4 = 120 states (with 5 numbers each). All of these have to undergo the same ritual, so it's no wonder it's taking so long.</p>
  
  <p>The program is actually too big to list here, so I will upload it for those interested:
  <a href="http://www.speedyshare.com/ksT43/MathGame3.jar" rel="nofollow">http://www.speedyshare.com/ksT43/MathGame3.jar</a>
  (Click on the MathGame3.jar title right next to download)</p>
  
  <p>Here's the general rundown on what happens:</p>
  
  <pre><code>-6 integers + goal number are initialized
  -I use the class StateNumbers that are acting as game states
    -&gt; in this class the remaining numbers (initially the 6 starting numbers)
       are kept as well as the evaluated expressions, for printing purposes
  </code></pre>
  
  <p>This method is where the main operations happen:</p>
  
  <pre><code>StateNumbers stateInProcess = getStates().remove(0);
  ArrayList&lt;Integer&gt; remainingNumbers = stateInProcess.getRemainingNumbers();
  for(int j = 0; j &lt; remainingNumbers.size(); j++){
    for(int i = 0; i &lt; remainingNumbers.size(); i++){
      for(Operator op : Operator.values()){       // Looping over different operators
         if(i == j) continue;
             ...
  
      }
    }
  }
  </code></pre>
  
  <p>I evaluate for the first element all the possible operations with all the remaining numbers for that state. I then check with a self written equals to see if it's already in the arraylist of states (which acts as a queue, but the order is not of importance). If it's not there, then the state will be added to the list and then I do the same for the other elements. After that I discard the state and pick another out of the growing list.</p>
  
  <p>The list grows in size to 80k states in 10 minutes and grows slower and slower. That's because there is an increasing amount of states to compare to when I want to add a new state. It's making me wonder if comparing with other states to prevent duplicates is such a good idea.</p>
  
  <p>The completion of this program is not really that important, but I'd like to see it as a learning experience. I'm not asking anyone to write the code for me, but a friendly suggestion on what I could have handled better would be very much appreciated. This means if you have something you'd like to mention about another aspect of the program, please do. I'm unsure if this is too much to ask for on this forum as most topics handle a specific part of a program. While my question is specific as well, the causes could be many.</p>
  
  <p>EDIT: I'm not trying to find the fastest single solution, but every solution. So if I find a solution, my program will not stop. It will however try to ignore doubles like:
  ((4+5)<em>7) and (7</em>(5+4)).  Only one of the two is accepted because the equals method in addition and multiplication do not care about the positioning of the operands.</p>