Получение каждой комбинации чисел X с данными числами Y?

Я пришел к математической проблеме, которая не может программировать логику.

Позвольте мне объяснить это на примере:

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

Скажем, если у меня уже есть набор [3,4] в моем массиве, я не хочу [4,3] в качестве другого набора.

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

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

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]