Ograniczona kartezjańska kalkulacja produktu - PHP

Question

EDYCJA 1 - po zaksięgowaniu Dowiedziałem się, że podstawowe pytanie dotyczy znalezienia PRODUKTU KARTESJANOWEGO (teraz google), ale nie tylko dlatego, że nie chcę każdego permu, chcę aby znaleźć produkty kartezjańskie, które używają tego samego podprzestrzeni Klucz nigdy więcej niż jeden raz na permuację I moje "dodatkowe" pytanie to więcej o tym, jak zminimalizować obciążenie, jakiego wymagałby produkt kartezjański (akceptując mały wskaźnik błędu, muszę powiedzieć) -

Wyobraź sobie ... mam czterech kucharzy i cztery przepisy, każdy kucharz ma wynik za każdy przepis i dziś chciałbym, aby każdy kucharz przygotował jedno danie (ale nie powinno się robić naczynia dwa razy) i decyzja powinna opierać się na najlepszej (najwyższej sumie punktów) permutacji dla wszystkich czterech osób (więc może kucharz nie sprawi, że jego osobista będzie st).

I umieścić dane w wielowymiarowej tablicy jako taki

array(
    array (1,2,3,4), 
    array (35,0,0,0), 
    array (36,33,1,1), 
    array (20,20,5,3) 
) 

• ma taką samą liczbę valuepairs w każdym sub tablicy jako liczba cząstkowych matryc (jeśli ułatwia jakiekolwiek)

• w rzeczywistości liczba tablic podrzędnych osiągnie maksimum 8 (perms max zatem = 8 !, około 40000 nie 8^8, gdyż wiele kombinacji nie są dozwolone)

• wybór mając dane w tym formacie jest elastyczny, jeśli pomaga

próbuję utworzyć drugą tablicę, że wyjście najlepsze (czyli najwyższa wartość) możliwa kombinacja z sub-macierzy, jak na klucze gdzie może być użyta tylko JEDNA z każdej podmary

- tak tutaj każda podmole [0] [1] [2] [3] byłaby używana raz na permutację , a każda podprzestrzeńKey [0] [1] [2] [3] byłby używany raz na permutację, w moim rzeczywistym problemie używam powiązanych tablic, ale to jest dodatkowe w tym wydaniu. -

Tak więc przykład woul d utwórz tablicę jako taką newArray (35,33,5,4) // zauważ, że [2] [0] nie był używany

IDEALNIE Wolałbym nie produkować wszystkich permów, ale raczej, SOMEHOW, discard wiele kombinacji, które z pewnością nie byłyby najlepiej dopasowane.

Wszelkie pomysły na rozpoczęcie? Akceptowałbym pseudo kod.

Na przykład na SO o iloczyn kartezjański, zobacz PHP 2D Array output all combinations

EDIT 2 Więcej informacji na temat dokonywania iloczyn kartezjański bardziej efektywne, a może dlaczego to musi być przypadek specyficzny jeśli chcesz sprawdzić, czy można na skróty (z ryzykiem) Efficient Cartesian Product algorithm

Answer 1

OK Oto rozwiązanie, które pozwala znaleźć najlepszą kombinację jednego kucharza do jednej receptury i żaden kucharz nie działa dwa razy i żadna receptura nie jest wykonywana dwukrotnie.

Dzięki za kod do obliczenia perm tablic idzie do o'reilly ... http://docstore.mik.ua/orelly/webprog/pcook/ch04_26.htm

UWAGI:

• liczba kucharzy i liczba receptur są takie same.

• Przechodzenie powyżej matrycy 5 na 5, jak tutaj, bardzo szybko stanie się bardzo duże. (Patrz część 2 zostanie zamieszczona wkrótce)

Logika: permutacji tablicy przypisuje się jak tylko jest włączony (czyli co kombinacja robi), więc dlaczego nie następnie przypisać każdy klucz takiej tablicy do receptury, permutacja gwarantuje, że żaden kucharz nie zostanie powtórzony, a klucze gwarantują, że żadna receptura nie zostanie powtórzona.

Proszę dać mi znać, jeśli są ulepszenia lub błędy w moim myśleniu lub mój kod, ale oto jest!

<?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/>"; 




?> 

Answer 2

Spróbuj

$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); 

Answer 3

mogę mieć punkt wyjścia do ciebie z tego algorytmu, który stara się wybierać kucharzy na podstawie ich stosunku max wynik na sumę sc Rudy (w ten sposób próbuje wybrać kucharzy, którzy są naprawdę dobrzy w jednej receptury, ale źle na resztę receptur zrobić tego przepisu)

$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']]); 
    } 
} 

dla zbioru danych dostarczonych, to może znaleźć to, co wydaje się być optymalna odpowiedź (35,33,5,4).Jednak nadal nie jest idealna, na przykład za pomocą tablicy:

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

Idealną odpowiedzią będzie (20,33,33,4), jednak algorytm ten wróci (35,33,5,4).

Ale skoro pytanie z prośbą o pomysły, od czego zacząć, myślę, że to przynajmniej może wystarczyć jako coś zacząć od: P

Answer 4

przeprosiny, ale to będzie raczej układ logiczny niż kod ...

to nie jest dla mnie jasne, czy array (1,2,3,4) są wyniki za pierwsze danie lub z pierwszego kucharza, ale to pewnie używać tablicy tak, że

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

() każda tablica tak, aby $ array [$ cook_id] = array ($ lowest_scored _dish, ..., $ najwyższy);

Należy rozważyć ważoną preferencję dla konkretnego kucharza, aby danie stanowiło różnicę między wynikiem najlepszego dania a innym.

Jako bardzo prosty przykład gotuje, a, b, c oraz naczynia 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 

Po asort(): $ tablica [ '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);

Zacznij od kucharza "a", który woli danie 0 od swojej następnej najlepszej potrawy o 50 punktów (waga). Cook 'b' również preferuje dih 0, ale o wadze 0 w stosunku do następnego dania. Dlatego jest prawdopodobne (choć nie jest jeszcze pewne, że kucharz "a" powinien przygotować danie 0.

Rozważ danie 0, które ma być zarezerwowane i przejdź do gotowania "b" Z wyjątkiem dania 0, gotuj "b" preferuje danie 1. Nie inny kucharz preferuje danie 1, więc gotować „b” jest przypisany potrawie 1.

kucharska „c” dostaje danie 2 domyślnie.

jest to bardzo wygodne przykład gdzie każdy kucharz dostaje ugotować coś, co jest osobisty max, ale mam nadzieję, że jest to ilustracja jakiejś logiki, która by zadziałała.

Zrobimy to mniej wygodnie:

$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); 

Powtórzyć Cooka a "i 0 zauważyć, że jest korzystne, ale tym razem z wagi 25. Cooka b 'preferuje o gramaturze od 50 do gotowania„c”preferuje o wadze 75. gotowania "c" wygrywa danie 0.

Wracając do listy dostępnych kucharzy, "a" preferuje 1 o wadze 50, ale "b" preferuje wagę 0. "a" dostaje danie 1 i "b" "dostaje danie 2.

To nadal nie zajmuje się wszystkimi złożonościami, ale jest krokiem we właściwym kierunku. Czasami założenie przyjęte dla pierwszej kombinacji dania/dania będzie błędne.

WAY mniej wygodne:

$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' dostaje 0, ponieważ jest to max i nikt inny, kto preferuje 0 ma wyższą masę 'b' wygrywa 1 o wadze 149 'd' wygrywa 2 od „c” nie posiada pierwszeństwo z dostępnych opcji „C” dostaje 3

wynik: 200 + 149 + 147 + 16 = 512

Mimo, że jest to dobry przypuszczenie, że zebrali bez sprawdzania każda permutacja, t może być nie tak. Stąd zapytaj: "Gdyby jeden kucharz wymienił się z kimś innym, czy całkowity wzrost?"

odpowiedź brzmi tak, a (0) + d (2) = 200 + 16 = 216, ale (2) + d (0) = 148 + 69 = 217.

Zostawię to do ciebie, aby napisać kod dla „najlepszego odgadnięcia” stosując metodę ważonego, ale po tym, tutaj jest to dobry początek dla Ciebie:

// 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); 

nie mogę znaleźć przykład licznik, aby pokazać, że to nie robi” działa, ale jestem podejrzliwy wobec przypadku, w którym ($ array [$ cook1] [$ dish1] + $ array [$ cook2] [$ dish2]) == ($ array [$ cook1] [$ dish2 ] + tablica $ [$ cook2] [$ dish1])

Może ktoś inny odpowie na to pytanie "Co, jeśli?"

Biorąc pod uwagę to macierz, w której elementy w nawiasach są "rozgrywki"

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

Jeśli a1 + a2 + b2 == b1, a następnie 'a' i 'b' nie przejdzie potraw. Sprawa nie jestem 100% pewny jest, jeśli istnieje taka macierz taką, że jest lepszym wyborem:

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

Pierwsze z pierwszego stanu do drugiego wymaga dwa przełączniki, z których pierwszy jest arbitralne, ponieważ nie zmienia sumy. Ale tylko przechodząc przez tę arbitralną zmianę, można dokonać ostatniego przełączenia.

Próbowałem znaleźć przykład 3x3 taki, że w oparciu o model "ważonej preferencji", o którym pisałem powyżej, pierwszy zostałby wybrany, ale także taki, że prawdziwy optymalny wybór jest podawany przez drugi. Nie mogłem znaleźć przykładu, ale to nie znaczy, że nie istnieje. Nie mam ochoty robić więcej algebry macierzy teraz, ale może ktoś podchwyci to, gdzie skończyłem. Heck, może sprawa nie istnieje, ale myślałem, że powinienem zwrócić uwagę na problem.

Jeśli to zadziała i zaczniesz od prawidłowego wyboru, powyższy kod przejdzie tylko 64 razy (8x8) dla 8 smażonych potraw/potraw. Jeśli pick nie jest poprawny, a pierwszy kucharz ma zmianę, to osiągnie 72. Jeśli ósmy kucharz ma zmianę, to jest to 128. Możliwe, że do-while będzie się zapętlać kilka razy, ale wątpię pojawi się w pobliżu cykli procesora wymaganych do zsumowania wszystkich kombinacji 40k.