獲取給定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)); 
    } 
} 

我需要什麼，不能弄清楚如何程序，是一個函數或循環或其他東西，返回一個陣列的孔的位置，給定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]]。

它不必按順序返回，我只需要所有的元素。

正如您所看到的，另一種方法是互補或反轉或不知道如何稱呼它，但解決方案是給定Y個孔的X個自由孔的每個組合，因此，如果我有10個洞和5個彈珠，會有5個自由洞，返回的數組將會是每個可以與（1,2,3,4,5,6,7,8,9,10）形成的5個組合，是252種組合，我需要的是252種組合。

對於第二方法

實例：

給定一個array=[1,2,3,4]，返回套2和每一個組合3.

的3

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

2個

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

集集

我需要的是這樣做的邏輯，我試圖用PHP來完成，但我無法弄清楚如何去做。

功能將接收陣列和集的大小和將返回將數組：

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

我希望這是不夠清楚，有人能幫助我，我已經堅持了好幾天了，但對我來說似乎太過於自負。

這個帖子，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，則返回一個空組合
• 否則，生成所有組合是包括第一個元素，通過遞歸生成除了第一個具有setsize - 1元素的元素之外的數組的所有組合，然後將第一個元素預先添加到它們中的每一個。
• 然後，如果數組大小大於setsize（意思是包括第一個元素不是強制的），則爲列表的其餘部分生成所有組合，並將它們添加到我們在第二步中生成的組合中。

所以基本上在每一個步驟，你需要考慮的因素是否會被納入或排除在組合和合並在一起組表示兩個備選項的組合。