Getting every combination of X numbers given Y numbers?

Question

I've come to a mathematical problem which for I can't program the logic.

Let me explain it with an example:

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.

I need to get every posible ORDERED combination:

ABC4
AB3C
A2BC
1ABC

This is very simple, but what if the number of holes changes? Let's say now I have 5 holes.

ABC45
AB3C5
A2BC5
1ABC5
AB34C
A2B4C
1AB4C
A23BC
1A3BC
12ABC

Now let's say we have 5 holes and 4 marbles.

ABCD5
ABC4D
AB3CD
A2BCD
1ABCD

And this can be any number of holes and any number of marbles.

The number of combinations is given by:

$combinations = factorial($number_of_holes)/(factorial($number_of_marbles)*factorial($number_of_holes-$number_of_marbles)))

(Here it is the factorial function in case you need it)

function factorial($number) { 
    if ($number < 2) { 
        return 1; 
    } else { 
        return ($number * factorial($number-1)); 
    } 
}

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.

For first example it would be: [[4],[3],[2],[1]], for second: [[4,5],[2,5],[1,5],[3,4],[2,4],[1,5],[2,3],[1,3],[1,2]], for third: [[5],[4],[3],[2],[1]].

It doesn't have to be returned in order, I just need all the elements.

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.

Examples for the 2nd approach:

Given an array=[1,2,3,4], return every combination for sets of 2 and 3.

Sets of 2

[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Sets of 3

[[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

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.

The function would receive the array and the set size and would return the array of sets:

function getCombinations($array,$setize){
    //magic code which I can't figure out
    return array(sets);
}

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.

This post, PHP algorithm to generate all combinations of a specific size from a single set, 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.

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.

Answer 1

Here's a recursive solution in PHP:

function getCombinations($array, $setsize){  
    if($setsize == 0)
        return [[]];

    // generate combinations including the first element by generating combinations for 
    // the remainder of the array with one less element and prepending the first element:
    $sets = getCombinations(array_slice($array, 1), $setsize - 1);
    foreach ($sets as &$combo) {
        array_unshift($combo, $array[0]);
    }

    // generate combinations not including the first element and add them to the list:
    if(count($array) > $setsize)
        $sets = array_merge($sets, getCombinations(array_slice($array, 1), $setsize));

    return $sets;
}

// test:
print_r(getCombinations([1, 2, 3, 4], 3));

Algorithm works like this:

• If setsize is 0 then you return a single, empty combination
• Otherwise, generate all combinations that include the first element, by recursively generating all combinations off the array excluding the first element with setsize - 1 elements, and then prepending the first element to each of them.
• Then, if the array size is greater than setsize (meaning including the first element is not compulsory), generate all the combinations for the rest of the list and add them to the ones we generated in the second step.

So basically at each step you need to consider whether an element will be included or excluded in the combination, and merge together the set of combinations representing both choices.