Декартово изделие с определенными критериями

Question

Я пытаюсь найти декартовую продукцию и добавить конкретные критерии.

У меня есть четыре бассейна по 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 

      } 
     } 
    }  
}  

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

Answer 1

Несколько вещей, чтобы отметить ваш подход здесь. Говоря строго с точки зрения математики, вы вычисляете больше перестановок, чем на самом деле необходимо для получения окончательного ответа.

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

1. Имеет ли значение вопрос? (для вашего случая это не так)
2. Возможно ли повторение? (Для случая, не надо повторять)

Поскольку ответ на оба этих вопроса нет, вам нужно лишь часть итераций вы в настоящее время делают с вложенным циклом. В настоящее время вы делаете, pow(25, 4) перестановок, то есть 390625. Вам действительно нужен только n!/r! (n-r)! или gmp_fact(25)/(gmp_fact(4) * gmp_fact(25 - 4)) который всего 12650 дополнительных подстановок.

Вот простой пример функции, которая производит комбинацию без повторений (и где порядок не имеет значения), используя генератор в PHP (взятый из this SO answer).

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, результат, несомненно, будет одинаковым в обеих перестановках. Поэтому вам нужно только добавить каждый уникальный набор один раз, чтобы установить все возможные суммы.

Answer 2

Как указано Barmar, сортировка людей в каждом бассейне позволяет остановить петли раньше, когда общая стоимость превышает предел и, следовательно, уменьшает количество случаев, которые необходимо проверить. Однако асимптотическая сложность для применения этого улучшения по-прежнему равна O (n) (где n - количество людей в пуле).

я перечислю альтернативный подход с более асимптотической сложности следующим образом:

1. Построить бассейн X, который содержит все пары людей с одним из бассейна A, а другой из бассейна B.
2. Построить бассейн Y который содержит все пары людей с одним из пула C, а другой из бассейна D.
3. Сортировка пар в бассейне X по общей цене. Затем для любых пар с одинаковой ценой сохраните ту, которая имеет самый высокий балл, и отбросьте оставшиеся пары.
4. Сортировка пар в пуле Y общей стоимостью. Затем для любых пар с одинаковой ценой сохраните ту, которая имеет самый высокий балл, и отбросьте оставшиеся пары.
5. Сделайте петлю с двумя указателями, чтобы проверить на все возможные комбинации, которые удовлетворяют цену ограничение, где 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 (n) и сложность этапов 3 и 4 может быть выполнено в O (n log (n)) с использованием сбалансированного двоичного дерева. А шаг 5 представляет собой, по существу, линейное сканирование над n элементов, поэтому сложность также O (n). Поэтому общая сложность этого подхода - O (n log (n)).

Answer 3

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

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

Если существует какой-либо член, который превышает допустимую цену товара самостоятельно, они могут быть устранены спереди.

Если вы закажете 4 группы по убыванию, и вы найдете решение abcd, где сумма цены является законной, вы нашли оптимальное решение для заданного набора символов abc.

Answer 4

Репоны здесь помогли мне найти лучший способ для меня сделать это.

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

Я сохранил комбинированную зарплату -> комбинацию баллов в новом массиве, и если зарплата уже существовала, я бы сравнил баллы и удалю нижнюю.

$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 петля между $ Результатов и $ poolC.

foreach($results as $R) { 
    foreach($poolC as $C) { 

и, наконец, я делаю это в последний раз для $ poolD.

Я работаю над оптимизацией кода, поставив все четыре петли foreach в один.

Спасибо всем за вашу помощь, я смог прокрутить 9 списков с 25 + людьми в каждом и найти лучший результат в невероятно быстром времени обработки!