title: Getting every combination of X numbers given Y numbers?
body: <p>I've come to a mathematical problem which for I can't program the logic.</p>
  
  <p>Let me explain it with an example:</p>
  
  <p>Let's say I have 4 holes and 3 marbles, the holes are in order and my marbles are A,B and C and also in order.</p>
  
  <p>I need to get every posible ORDERED combination:</p>
  
  <pre><code>ABC4
  AB3C
  A2BC
  1ABC
  </code></pre>
  
  <p>This is very simple, but what if the number of holes changes? Let's say now I have 5 holes.</p>
  
  <pre><code>ABC45
  AB3C5
  A2BC5
  1ABC5
  AB34C
  A2B4C
  1AB4C
  A23BC
  1A3BC
  12ABC
  </code></pre>
  
  <p>Now let's say we have 5 holes and 4 marbles.</p>
  
  <pre><code>ABCD5
  ABC4D
  AB3CD
  A2BCD
  1ABCD
  </code></pre>
  
  <p>And this can be any number of holes and any number of marbles.</p>
  
  <p>The number of combinations is given by:</p>
  
  <pre><code>$combinations = factorial($number_of_holes)/(factorial($number_of_marbles)*factorial($number_of_holes-$number_of_marbles)))
  </code></pre>
  
  <p>(Here it is the factorial function in case you need it)</p>
  
  <pre><code>function factorial($number) { 
      if ($number &lt; 2) { 
          return 1; 
      } else { 
          return ($number * factorial($number-1)); 
      } 
  }
  </code></pre>
  
  <p>What I need and can't figure out how to program, is a function or a loop or something, that returns an array with the position of the holes, given X numbers of holes and Y number of marbles.</p>
  
  <p>For first example it would be: <code>[[4],[3],[2],[1]]</code>, for second: <code>[[4,5],[2,5],[1,5],[3,4],[2,4],[1,5],[2,3],[1,3],[1,2]]</code>, for third: <code>[[5],[4],[3],[2],[1]]</code>.</p>
  
  <p>It doesn't have to be returned in order, I just need all the elements.</p>
  
  <p>As you can see, another approach is the complementary or inverse or don't know how to call it, but the solution is every combinations of X number of free holes given Y number of holes, so, If I have 10 holes, and 5 marbles, there would be 5 free holes, the array returned would be every combination of 5 that can be formed with (1,2,3,4,5,6,7,8,9,10), which are 252 combinations, and what I need is the 252 combinations.</p>
  
  <p>Examples for the 2nd approach:</p>
  
  <p>Given an <code>array=[1,2,3,4]</code>, return every combination for sets of 2 and 3.</p>
  
  <p>Sets of 2</p>
  
  <pre><code>[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
  </code></pre>
  
  <p>Sets of 3</p>
  
  <pre><code>[[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
  </code></pre>
  
  <p>What I need is the logic to do this, I'm trying to do it in PHP, but I just can't figure out how to do it.</p>
  
  <p>The function would receive the array and the set size and would return the array of sets:</p>
  
  <pre><code>function getCombinations($array,$setize){
      //magic code which I can't figure out
      return array(sets);
  }
  </code></pre>
  
  <p>I hope this is clear enough and someone can help me, I've been stuck for several days now, but it seems to be just too much for me to handle by myself.</p>
  
  <p>This post, <a href="https://stackoverflow.com/questions/19067556/php-algorithm-to-generate-all-combinations-of-a-specific-size-from-a-single-set">PHP algorithm to generate all combinations of a specific size from a single set</a>, is for all possible combinations, repeating the elements and order doesn't matter, its a good lead, I did read it, but it doesn't solve my problem, it's very different. I need them without repeating the elements and ordered as explained.</p>
  
  <p>Let's say if I have already a set of [3,4] in my array, I don't want [4,3] as an other set.</p>