得到给定 Y 数的 X 数的每个组合？

Question

我遇到了一个数学问题，因为我无法编写逻辑程序。

我举个例子解释一下：

假设我有 4 个孔和 3 个弹珠，孔是按顺序排列的，我的弹珠是 A、B 和 C，也是按顺序排列的。

我需要得到所有可能的有序组合：

ABC4
AB3C
A2BC
1ABC

这个很简单，但是如果孔数变了怎么办？假设现在我有 5 个洞。

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

现在假设我们有 5 个洞和 4 个弹珠。

ABCD5
ABC4D
AB3CD
A2BCD
1ABCD

这可以是任意数量的孔和任意数量的弹珠。

组合数由下式给出：

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

（这里是阶乘函数，以备不时之需）

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

我需要但无法弄清楚如何编程的是一个函数或循环或其他东西，return是一个带有孔位置的数组，给定 X 个孔和 Y弹珠数量。

对于第一个示例，它将是：[[4],[3],[2],[1]]，对于第二个示例：[[4,5],[2,5],[1,5],[3,4],[2,4],[1,5],[2,3],[1,3],[1,2]]，对于第三个示例：[[5],[4],[3],[2],[1]].

不需要按顺序return编辑，我只需要所有的元素。

如您所见，另一种方法是互补或逆或不知道如何称呼它，但解决方案是给定 Y 个孔的 X 个自由孔的每个组合，所以，如果我有10 个孔和 5 个弹珠，将有 5 个空闲孔，数组 returned 将是可以由 (1,2,3,4,5,6,7,8, 9,10),就是252个组合，我需要的就是这252个组合。

第二种方法的示例：

给定一个 array=[1,2,3,4]，return 每组 2 和 3 的组合。

2 套

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

3 套

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

我需要的是执行此操作的逻辑，我正在尝试在 PHP 中执行此操作，但我不知道该怎么做。

该函数将接收数组和集合大小，并将 return 集合数组：

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

我希望这足够清楚并且有人可以帮助我，我已经被困了好几天了，但我自己处理起来似乎太多了。

这个post，PHP algorithm to generate all combinations of a specific size from a single set，是针对所有可能的组合，重复元素和顺序没关系，很好的引导，我看过了，但是没有解决我的问题，这是非常不同的。我需要它们而不重复元素并按说明订购。

假设我的数组中已经有一组 [3,4]，我不想将 [4,3] 作为另一组。

Answer 1

这是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));

算法是这样工作的：

如果 setsize 为 0，那么您 return 一个单一的空组合
否则，生成包含第一个元素的所有组合，方法是递归地生成数组之外的所有组合，不包括具有 setsize - 1 个元素的第一个元素，然后将第一个元素添加到每个组合之前。
然后，如果数组大小大于 setsize（意味着包括第一个元素不是强制性的），则生成列表其余部分的所有组合，并将它们添加到我们在第二步中生成的组合中。

所以基本上在每一步你都需要考虑一个元素是包含还是排除在组合中，并将代表这两种选择的组合集合并在一起。

得到给定 Y 数的 X 数的每个组合？

Getting every combination of X numbers given Y numbers?

php

arrays

math

logic

mathematical-expressions