Декартово произведение с конкретными критериями
Я пытаюсь найти декартово произведение и добавить определенные критерии.
У меня есть четыре бассейна по 25 человек в каждом. У каждого человека есть оценка и цена. Каждый человек в каждом бассейне выглядит таковым.
[0] => array(
"name" => "jacob",
"price" => 15,
"score" => 100
),
[1] => array(
"name" => "daniel",
"price" => 22,
"score" => 200
)
Я хочу найти лучшую комбинацию людей, по одному человеку из каждого пула. Однако существует предельная цена, при которой никакая группировка не может превышать определенную цену.
Я возился с картезианцами и перестановочными функциями и не могу понять, как это сделать. Единственный способ, которым я знаю, как закодировать это, чтобы иметь вложенный foreach петли, но это невероятно тяжело.
Этот код ниже, как вы можете видеть, невероятно неэффективен. Особенно если бассейны увеличатся!
foreach($poolA as $vA) {
foreach($poolb as $vB) {
foreach($poolC as $vC) {
foreach($poolD as $vD) {
// calculate total price and check if valid
// calculate total score and check if greatest
// if so, add to $greatest array
}
}
}
}
Я также думал, что смогу найти способ рассчитать соотношение цена / результат и использовать его в своих интересах, но я не знаю, что мне не хватает.
Решение
Как указано Barmar, сортировка людей в каждом пуле позволяет рано останавливать циклы, когда общая цена превышает лимит, и, следовательно, сокращает количество проверяемых случаев. Тем не менее, асимптотическая сложность применения этого улучшения по-прежнему составляет O (n4) (где n количество людей в бассейне).
Я выделю альтернативный подход с лучшей асимптотической сложностью следующим образом:
- Построить бассейн
Xкоторый содержит все пары людей с одним из пулаAа другой из пулаB, - Построить бассейн
Yкоторый содержит все пары людей с одним из пулаCа другой из пулаD, - Сортировка пар в бассейне
Xпо общей цене. Затем для любых пар с одинаковой ценой оставьте ту, которая набрала наибольшее количество очков, и отбросьте оставшиеся пары. - Сортировка пар в бассейне
Yпо общей цене. Затем для любых пар с одинаковой ценой оставьте ту, которая набрала наибольшее количество очков, и отбросьте оставшиеся пары. - Выполните цикл с двумя указателями, чтобы проверить все возможные комбинации, которые удовлетворяют ценовому ограничению, где
headуказатель начинается с первого элемента в пулеXиtailуказатель начинается с последнего элемента в пулеY, Пример кода приведен ниже, чтобы проиллюстрировать, как работает этот цикл:
================================================== ========================
$head = 0;
$tail = sizeof($poolY) - 1;
while ($head < sizeof($poolX) && $tail >= 0) {
$total_price = $poolX[$head].price + $poolY[$tail].price;
// Your logic goes here...
if ($total_price > $price_limit) {
$tail--;
} else if ($total_price < $price_limit) {
$head++;
} else {
$head++;
$tail--;
}
}
for ($i = $head; $i < sizeof($poolX); $i++) {
// Your logic goes here...
}
for ($i = $tail; $i >= 0; $i--) {
// Your logic goes here...
}
================================================== ========================
Сложность шагов 1 и 2 составляет O (n2), а сложность шагов 3 и 4 можно выполнить за O (n2 log (n)) используя сбалансированное двоичное дерево. И шаг 5 по сути линейное сканирование по п2 предметы, поэтому сложность также O (n2). Поэтому общая сложность этого подхода составляет O (n2 войти (п)).
Другие решения
Несколько вещей, чтобы отметить о вашем подходе здесь. Говоря строго с математической точки зрения, вы рассчитываете больше перестановок, чем фактически необходимо для получения окончательного ответа.
В комбинаторике нужно задать два важных вопроса, чтобы получить точное число перестановок, необходимых для получения всех возможных комбинаций.
- Имеет ли значение порядок? (для вашего случая это не так)
- Разрешено ли повторение? (для вашего случая повторять не обязательно)
Поскольку ответ на оба эти вопроса нет, вам нужна только часть итераций, которые вы сейчас выполняете со своим вложенным циклом. В настоящее время вы делаете, pow(25, 4) перестановки, которая является 390625, Вам нужно только на самом деле n! / r! (n-r)! или же gmp_fact(25) / (gmp_fact(4) * gmp_fact(25 - 4)) который только 12650 Всего перестановок необходимо.
Вот простой пример функции, которая создает комбинации без повторений (и где порядок не имеет значения), используя генератор в PHP (взят из этот так ответ).
function comb($m, $a) {
if (!$m) {
yield [];
return;
}
if (!$a) {
return;
}
$h = $a[0];
$t = array_slice($a, 1);
foreach(comb($m - 1, $t) as $c)
yield array_merge([$h], $c);
foreach(comb($m, $t) as $c)
yield $c;
}
$a = range(1,25); // 25 people in each pool
$n = 4; // 4 pools
foreach(comb($n, $a) as $i => $c) {
echo $i, ": ", array_sum($c), "\n";
}
Было бы довольно легко изменить функцию генератора, чтобы проверить, соответствует ли сумма цен / превышает желаемую пороговую величину, и возвращать оттуда только действительные результаты (т.е. отказываться рано, где это необходимо).
Повторение и порядок не важны здесь для вашего варианта использования, потому что не имеет значения, добавляете ли вы $price1 + $price2 или же $price2 + $price1результат, несомненно, будет одинаковым в обеих перестановках. Таким образом, вам нужно сложить каждый уникальный набор только один раз, чтобы определить все возможные суммы.
Подобно решениям chiwangs, вы можете исключить каждого члена группы, если существует другой член группы в этой группе, с таким же или более высоким баллом за более низкую цену.
Может быть, вы можете устранить много членов в каждой группе с этим подходом.
Затем вы можете либо использовать эту технику, чтобы построить две пары и повторить фильтрацию (исключить пары, где существует другая пара, с более высоким счетом при тех же или меньших затратах), а затем объединить пары таким же образом, или добавить элемент пошагово. шаг (одна пара, тройка, квартет).
Если существует какой-либо участник, который самостоятельно превышает разрешенную сумму, он может быть исключен заранее.
Если вы упорядочите 4 группы по убыванию оценки, и вы найдете решение abcd, в котором цена суммы является законной, вы нашли оптимальное решение для данного набора abc.
Ответы здесь помогли мне найти лучший способ сделать это.
Я еще не оптимизировал функцию, но по сути я просматривал каждый результат по два за раз, чтобы найти комбинированные зарплаты / оценки для каждой комбинации в двух пулах.
Я сохранил комбинированную комбинацию зарплата -> баллы в новом массиве, и если зарплата уже существовала, я сравнил бы баллы и удалил нижнюю.
$results = array();
foreach($poolA as $A) {
foreach($poolB as $B) {
$total_salary = $A['Salary'] + $B['Salary'];
$total_score = $A['Score'] + $B['Score'];
$pids = array($A['pid'], $B['pid']);
if(isset($results[$total_salary]) {
if($total_score > $results[$total_salary]['Score']) {
$results[$total_salary]['Score'] => $total_score;
$results[$total_salary]['pid'] => $pids;
} else {
$results[$total_salary]['Score'] = $total_score;
$results[$total_salary]['pid'] = $pids;
}
}
}
После этого цикла у меня есть другой, который идентичен, за исключением того, что мои циклы foreach находятся между $ results и $ poolC.
foreach($results as $R) {
foreach($poolC as $C) {
и, наконец, я делаю это в последний раз за $ poolD.
Я работаю над оптимизацией кода, объединяя все четыре цикла foreach в один.
Спасибо всем за помощь, мне удалось просмотреть 9 списков по 25+ человек в каждом и найти лучший результат за невероятно быстрое время обработки!