title: Reducing the time complexity of this algorithm
body: <p>I'm playing a game that has a weapon-forging component, where you combine two weapons to get a new one.  The sheer number of weapon combinations (see "6.1. Blade Combination Tables" at <a href="http://www.gamefaqs.com/ps/914326-vagrant-story/faqs/8485">http://www.gamefaqs.com/ps/914326-vagrant-story/faqs/8485</a>) makes it difficult to figure out what you can ultimately create out of your current weapons through repeated forging, so I tried writing a program that would do this for me.  I give it a list of weapons that I currently have, such as:</p>
  
  <ul>
  <li>francisca</li>
  <li>tabarzin</li>
  <li>kris</li>
  </ul>
  
  <p>and it gives me the list of all weapons that I can forge:</p>
  
  <ul>
  <li>ball mace</li>
  <li>chamkaq</li>
  <li>dirk</li>
  <li>francisca</li>
  <li>large crescent</li>
  <li>throwing knife</li>
  </ul>
  
  <p>The problem is that I'm using a brute-force algorithm that scales extremely poorly; it takes about 15 seconds to calculate all possible weapons for seven starting weapons, and a few minutes to calculate for eight starting weapons.  I'd like it to be able to calculate up to 64 weapons (the maximum that you can hold at once), but I don't think I'd live long enough to see the results.</p>
  
  <pre><code>function find_possible_weapons(source_weapons)
  {
      for (i in source_weapons)
      {
          for (j in source_weapons)
          {
              if (i != j)
              {
                  result_weapon = combine_weapons(source_weapons[i], source_weapons[j]);
  
                  new_weapons = array();
                  new_weapons.add(result_weapon);
                  for (k in source_weapons)
                  {
                      if (k != i &amp;&amp; k != j)
                          new_weapons.add(source_weapons[k]);
                  }
                  find_possible_weapons(new_weapons);
              }
          }
      }
  }
  </code></pre>
  
  <p>In English:  I attempt every combination of two weapons from my list of source weapons.  For each of those combinations, I create a new list of all weapons that I'd have following that combination (that is, the newly-combined weapon plus all of the source weapons except the two that I combined), and then I repeat these steps for the new list.</p>
  
  <p>Is there a better way to do this?</p>
  
  <p>Note that combining weapons in the reverse order can change the result (Rapier + Firangi = Short Sword, but Firangi + Rapier = Spatha), so I can't skip those reversals in the <code>j</code> loop.</p>
  
  <p><strong>Edit:</strong> Here's a breakdown of the test example that I gave above, to show what the algorithm is doing.  A line in brackets shows the result of a combination, and the following line is the new list of weapons that's created as a result:</p>
  
  <pre><code>francisca,tabarzin,kris
  [francisca + tabarzin = chamkaq]
      chamkaq,kris
      [chamkaq + kris = large crescent]
          large crescent
      [kris + chamkaq = large crescent]
          large crescent
  [francisca + kris = dirk]
      dirk,tabarzin
      [dirk + tabarzin = francisca]
          francisca
      [tabarzin + dirk = francisca]
          francisca
  [tabarzin + francisca = chamkaq]
      chamkaq,kris
      [chamkaq + kris = large crescent]
          large crescent
      [kris + chamkaq = large crescent]
          large crescent
  [tabarzin + kris = throwing knife]
      throwing knife,francisca
      [throwing knife + francisca = ball mace]
          ball mace
      [francisca + throwing knife = ball mace]
          ball mace
  [kris + francisca = dirk]
      dirk,tabarzin
      [dirk + tabarzin = francisca]
          francisca
      [tabarzin + dirk = francisca]
          francisca
  [kris + tabarzin = throwing knife]
      throwing knife,francisca
      [throwing knife + francisca = ball mace]
          ball mace
      [francisca + throwing knife = ball mace]
          ball mace
  </code></pre>
  
  <p>Also, note that duplicate items in a list of weapons are significant and can't be removed.  For example, if I add a second kris to my list of starting weapons so that I have the following list:</p>
  
  <ul>
  <li>francisca</li>
  <li>tabarzin</li>
  <li>kris</li>
  <li>kris</li>
  </ul>
  
  <p>then I'm able to forge the following items:</p>
  
  <ul>
  <li>ball mace</li>
  <li>battle axe</li>
  <li>battle knife</li>
  <li>chamkaq</li>
  <li>dirk</li>
  <li>francisca</li>
  <li>kris</li>
  <li>kudi</li>
  <li>large crescent</li>
  <li>scramasax</li>
  <li>throwing knife</li>
  </ul>
  
  <p>The addition of a duplicate kris allowed me to forge four new items that I couldn't before.  It also increased the total number of forge tests to 252 for a four-item list, up from 27 for the three-item list.</p>
  
  <p><strong>Edit:</strong> I'm getting the feeling that solving this would require more math and computer science knowledge than I have, so I'm going to give up on it.  It seemed like a simple enough problem at first, but then, so does the Travelling Salesman.  I'm accepting David Eisenstat's answer since the suggestion of remembering and skipping duplicate item lists made such a huge difference in execution time and seems like it would be applicable to a lot of similar problems.</p>