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