Расчет ограниченного декартова произведения - PHP

Извините, но это будет скорее логическая схема, чем код ...

Мне не совсем понятно, является ли массив (1,2,3,4) баллами для первого блюда или для первого приготовления, но я, вероятно, использовал бы такой массив, что

$array[$cook_id][$dish_number] = $score;

asort () каждый массив так, чтобы $ array [$ cook_id] = array ($ low_scored_dish, ..., $ high);

Считайте взвешенное предпочтение того или иного повара приготовить блюдо как разницу между оценкой лучшего блюда и другого.

В качестве очень простого примера готовим блюда a, b, c и 0,1,2.

$array['a'] = array(0=>100, 1=>50, 2=>0); // cook a prefers 0 over 1 with weight 50, over 2 with weight 100
$array['b'] = array(0=>100, 1=>100, 2=>50); // cook b prefers 0,1 over 2 with weight 50
$array['c'] = array(0=>50, 1=>50, 2=>100); // cook c prefers 2 with weight 50

После asort (): $ array ['a'] = array (0 => 100, 1 => 50, 2 => 0); $ array ['b'] = array (0 => 100, 1 => 100, 2 => 50); $ array ['c'] = array (2 => 100, 0 => 50, 1 => 50);

Начните с повара «а», который на 50 баллов (по весу) предпочитает блюдо 0 своему следующему лучшему блюду. Повар 'b' также предпочитает dih 0, но вес следующего блюда равен 0. Следовательно, вероятно (хотя еще не уверен, что готовить 'a' должно получиться блюдо 0.

Считайте блюдо 0 зарезервированным и переходите к приготовлению «b». За исключением блюда 0, повар 'b' предпочитает блюдо 1. Ни один другой повар не предпочитает блюдо 1, поэтому повар 'b' назначает блюдо 1.

По умолчанию Cook 'c' получает блюдо 2.

Это ОЧЕНЬ удобный пример, когда каждый повар может приготовить что-то личное, но я надеюсь, что это иллюстрирует некоторую логику, которая сработает.

Сделаем менее удобным:

$array['a'] = array(0=>75, 1=>50, 2=>0);
$array['b'] = array(0=>100, 1=>50, 2=>50);
$array['c'] = array(0=>100, 1=>25, 2=>25);

Начните снова с готовить «a» и убедитесь, что предпочтительнее 0, но на этот раз с весом 25. Готовьте «b» предпочитает с весом 50, а готовьте «c» предпочитает с весом 75. Повар «c» выигрывает блюдо 0 .

Возвращаясь к списку доступных поваров, «a» предпочитает 1 с весом 50, а «b» - с весом 0. «a» получает блюдо 1, а «b» - блюдо 2.

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

ПУТЬ менее удобно:

$array['a'] = array(0=>200, 1=>148, 2=>148, 3=>0);
$array['b'] = array(0=>200, 1=>149, 2=>0, 3=>0);
$array['c'] = array(0=>200, 1=>150, 2=>147, 3=>147);
$array['d'] = array(0=>69, 1=>18, 2=>16, 3=>15);

'a' получает 0, так как это максимум, и никто другой, кто предпочитает 0, не имеет большего веса 'b' выигрывает 1 с весом 149 'd' выигрывает 2, поскольку 'c' не имеет предпочтения из доступных вариантов ' c 'получает 3

оценка: 200 + 149 + 147 + 16 = 512

Хотя это хорошее предположение, полученное без проверки каждой перестановки, оно может быть неверным. Отсюда спросите: «Если бы один повар торговал с другим поваром, увеличилось бы общее количество?»

Ответ ДА, a (0) + d (2) = 200 + 16 = 216, но a (2) + d (0) = 148 + 69 = 217.

Я оставлю вам написать код для "наилучшего предположения" с использованием взвешенного подхода, но после этого вот вам хорошее начало:

// a totally uneducated guess...
$picks = array(0=>'a', 1=>'b', 2=>'c', 3=>'d');

do {
    $best_change = false;
    $best_change_weight = 0;
    foreach ($picks as $dish1 => $cook1) {
        foreach ($picks as $dish2 => $cook2) {
            if (($array[$cook1][$dish1] + $array[$cook2][$dish2]) <
                ($array[$cook1][$dish2] + $array[$cook2][$dish1]))
            {
                $old_score = $array[$cook1][$dish1] + $array[$cook2][$dish2];
                $new_score = $array[$cook1][$dish2] + $array[$cook2][$dish1];
                if (($new_score - $old_score) > $best_change_weight) {
                    $best_change_weight = $new_score - $old_score;
                    $best_change = $dish2;
                }
            }
        }
        if ($best_change !== false) {
            $cook2 = $picks[$best_change];
            $picks[$dish1] = $cook2;
            $picks[$dish2] = $cook1;
            break;
        }
    }
} while ($best_change !== false);

Я не могу найти пример счетчика, чтобы показать, что это не работает, но я с подозрением отношусь к случаю, когда ($ array [$ cook1] [$ spread1] + $ array [$ cook2] [$ plate2]) = = ($ массив [$ cook1] [$ блюдо2] + $ массив [$ cook2] [$ блюдо1])

Может быть, кто-нибудь еще ответит на этот вопрос «А что, если?».

Учитывая эту матрицу, где элементы в скобках являются «выбранными»

[a1]   a2   a3
 b1   [b2]  b3
 c1    c2  [c3]

Если a1 + b2 == a2 + b1, то «a» и «b» не будут переключать тарелки. Случай, в котором я не уверен на 100%, - это то, что существует такая матрица, что это лучший выбор:

 a1   [a2]   a3
 b1    b2   [b3]
[c1]   c2    c3

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

Я попытался найти пример 3x3, такой, что на основе модели «взвешенного предпочтения», о которой я писал выше, будет выбран первый, но также такой, что реальный оптимальный выбор будет дан вторым. Мне не удалось найти пример, но это не значит, что его не существует. Мне сейчас не хочется больше заниматься матричной алгеброй, но, возможно, кто-то продолжит с того места, где я остановился. Черт возьми, может быть, случая и не существует, но я подумал, что должен указать на проблему.

Если это сработает, и вы начнете с правильного выбора, приведенный выше код будет повторяться только 64 раза (8x8) для 8 поваров / блюд. Если выбор неправильный и у первого повара есть изменение, тогда оно увеличится до 72. Если у 8-го повара есть изменение, оно будет до 128. Возможно, что do-while повторится несколько раз, но я сомневаюсь он будет приближаться к циклам ЦП, необходимым для суммирования всех 40k комбинаций.

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

$cooks = array(
    array(1,2,3,4),
    array(35,0,0,0),
    array(36,33,1,1),
    array(20,20,5,3)
);
$results = array();

while (count($cooks)) {
    $curResult = array(
        'cookId' => -1,
        'recipe' => -1,
        'score'  => -1,
        'ratio'  => -1
    );
    foreach ($cooks as $cookId => $scores) {
        $max = max($scores);
        $ratio = $max / array_sum($scores);
        if ($ratio > $curResult['ratio']) {
            $curResult['cookId'] = $cookId;
            $curResult['ratio']  = $ratio;
            foreach ($scores as $recipe => $score) {
                if ($score == $max) {
                    $curResult['recipe'] = $recipe;
                    $curResult['score']  = $score;
                }
            }
        }
    }

    $results[$curResult['recipe']] = $curResult['score'];
    unset($cooks[$curResult['cookId']]);
    foreach ($cooks as &$cook) {
        unset($cook[$curResult['recipe']]);
    }
}

Для предоставленного набора данных он действительно находит то, что кажется оптимальным ответом (35,33,5,4). Однако он все же не идеален, например, с массивом:

$cooks = array(
    array(1,2,3,4),
    array(35,0,33,0),
    array(36,33,1,1),
    array(20,20,5,3)
);

Идеальным ответом будет (20,33,33,4), однако этот алгоритм вернет (35,33,5,4).

Но поскольку вопрос был о том, с чего начать, я полагаю, что этого, по крайней мере, может быть достаточно как чего-то, с чего начать: P

Попробуй это

$mainArr = array(
   array (1,2,3,4) ,
   array (35,0,0,0) ,
   array (36,33,1,1) ,
   array (20,20,5,3) 
 );
$i = 0;
foreach( $mainArr as $subArray )
{
    foreach( $subArray as $key => $value)
    {
        $newArr[$key][$i]=$value;
        $i++;   
    }
}
$finalArr = array();
foreach( $newArr as $newSubArray )
{
    $finalArr[] = max($newSubArray);    
}
print_r( $finalArr );

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

Спасибо за код для вычисления допустимости массивов к oreilly ... http://docstore.mik.ua/orelly/webprog/pcook/ch04_26.htm

СООБРАЖЕНИЯ:

• Количество поваров и количество рецептов одинаковы.

• Превышение матрицы 5 на 5, как здесь, очень быстро станет очень большим. (см. часть 2, которая будет опубликована в ближайшее время)

Логика: перестановка массива назначает место, а также просто включается (то есть, что делает комбинация), так почему бы тогда не назначить каждый ключ такого массива рецепту, перестановка гарантирует повар не повторяется, а ключи гарантируют, что рецепт не повторится.

Пожалуйста, дайте мне знать, есть ли улучшения или ошибки в моем мышлении или моем коде, но вот они!

<?php

function pc_next_permutation($p, $size) {
//this is from http://docstore.mik.ua/orelly/webprog/pcook/ch04_26.htm
    // slide down the array looking for where we're smaller than the next guy
    for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) { }

    // if this doesn't occur, we've finished our permutations
    // the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1)
    if ($i == -1) { return false; }

    // slide down the array looking for a bigger number than what we found before
    for ($j = $size; $p[$j] <= $p[$i]; --$j) { }

    // swap them
    $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;

    // now reverse the elements in between by swapping the ends
    for (++$i, $j = $size; $i < $j; ++$i, --$j) {
         $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
    }

    return $p;
}
$cooks[441] = array(340=>5,342=>43,343=>50,344=>9,345=>0);
$cooks[442] = array(340=>5,342=>-33,343=>-30,344=>29,345=>0);
$cooks[443] = array(340=>5,342=>3,343=>0,344=>9,345=>10,);                     
$cooks[444] = array(340=>25,342=>23,343=>20,344=>19,345=>20,); 
$cooks[445] = array(340=>27,342=>27,343=>26,344=>39,345=>50,); 

//a consideration: this solution requires that the number of cooks equal the number of recipes
foreach ($cooks as $cooksCode => $cooksProfile){
        $arrayOfCooks[]=$cooksCode;
        $arrayOfRecipes = (array_keys($cooksProfile));
}
echo "<br/> here is the array of the different cooks<br/>";
print_r($arrayOfCooks);
echo "<br/> here is the array of the different recipes<br/>";
print_r($arrayOfRecipes);

$set = $arrayOfCooks;
$size = count($set) - 1;
$perm = range(0, $size);
$j = 0;

do { 
     foreach ($perm as $i) { $perms[$j][] = $set[$i]; }
} while ($perm = pc_next_permutation($perm, $size) and ++$j);
echo "<br/> here are all the permutations of the cooks<br/>";
print_r($perms);

$bestCombo = 0;
foreach($perms as $perm){
    $thisScore =0;
        foreach($perm as $key =>$cook){
        $recipe= $arrayOfRecipes[$key];
        $cookScore =$cooks[$cook][$recipe];
        $thisScore = $thisScore+$cookScore;
        }
    if ($thisScore>$bestCombo){
        $bestCombo=$thisScore;
        $bestArray= $perm;
    }
}



echo "<br/> here is the very best array<br/>";
print_r ($bestArray);
echo "<br/> best recipe assignment value is:".$bestCombo."<br/><br/>";  




?>