Получение каждой комбинации номеров X, заданных Y-цифрами?

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]].

Его не нужно возвращать по порядку, мне просто нужны все элементы.

Как вы можете видеть, другой подход является дополняющим или обратным или не знает, как его называть, но решение представляет собой любую комбинацию из X числа свободных отверстий при заданном Y числе отверстий, поэтому, если у меня есть 10 отверстий и 5 мраморов, было бы 5 свободных отверстий, возвращаемая матрица была бы каждой комбинацией из 5, которая может быть сформирована с (1,2,3,4,5,6,7,8,9,10), что являются 252 комбинациями, и мне нужны 252 комбинации.

Примеры для 2-го подхода:

дан array=[1,2,3,4], возвращающие каждую комбинацию для наборов 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, но я просто не могу понять, как это сделать.

Функция получит массив и множество размеров и возвратит массив множеств:

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, а затем добавляя первый элемент к каждому из них.
• Тогда, если размер массива больше, чем набор (значение, включающее первый элемент, не является обязательным), сгенерируйте все комбинации для остальной части списка и добавьте их к тем, которые мы сгенерировали на втором шаге.

Таким образом, в основном на каждом шаге вам необходимо рассмотреть вопрос о том, будет ли элемент включен или исключен в комбинацию и объединить вместе набор комбинаций, представляющих оба варианта.