Un calcolo di prodotto cartesiano limitato - PHP

Question

EDIT 1 -sulla pubblicazione ho appreso che la domanda di fondo è su come trovare il PRODOTTO CARTESIANO (ora google), ma non solo perché non voglio ogni perm, voglio per trovare i prodotti cartesiani che usano lo stesso codice di sottoarray Mai più di una volta per permutazione E la mia domanda 'extra' è più su come minimizzare il carico di lavoro che un prodotto cartesiano richiederebbe (accettando un piccolo tasso di errore, devo dire) -

Immaginate ... Ho quattro cuochi e quattro ricette, ogni cuoco ha un punteggio per ogni ricetta e oggi vorrei che ogni cuoco preparasse un piatto (ma non dovrebbe essere preparato un piatto due volte) e la decisione dovrebbe si basa sulla migliore (massima totalizzazione) permutazione per tutti e quattro (quindi forse un cuoco non farà il suo personale essere st).

ho messo i dati in un array multidimensionale come tale

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

• ha lo stesso numero di valuepairs in ogni matrice sub come il numero di sub-array (se che aiuta qualsiasi)

• in realtà il numero di sub-array raggiungerebbe un massimo di 8 (max permanenti quindi = 8 !, circa 40.000 non 8^8 perché molte combinazioni non sono ammessi)

• la scelta di avere i dati in questo formato è flessibile se funziona

Sto provando a generare una seconda schiera che avrebbe generato il miglior (valore massimo) eventuale combinazione delle sub-array secondo KEYs dove può essere utilizzato solo UNO di ogni sottoarray

- così qui ogni sottoarray [0] [1] [2] [3] sarebbe utilizzato una volta per permutazione e ogni sottoarrayKey [0] [1] [2] [3] sarebbe usato una volta per permutaion, nel mio problema reale sto usando array associati, ma questo è extra a questo problema .--

Quindi l'esempio woul d creare un array come tale newArray (35,33,5,4) // notare che [2] [0] non è stato utilizzato

IDEALLY Preferirei non produrre TUTTI i PERMUTI ma piuttosto, SOMEHOW, scartare molte combinazioni che chiaramente non sarebbero le migliori.

Qualche idea su come iniziare? Accetterei pseudo codice.

Per un esempio su SO su prodotto cartesiano, vedere PHP 2D Array output all combinations

EDIT 2 per più sul fare prodotti cartesiani più efficiente, e forse il motivo per cui deve essere caso specifico, se si vuole vedere se è possibile tagliare gli angoli (con il rischio) Efficient Cartesian Product algorithm

Answer 1

OK qui è una soluzione che consente di trovare la migliore permutazione di una ricetta da cuoco a una e nessuna cottura funziona due volte e nessuna ricetta viene eseguita due volte.

Grazie per il codice per calcolare perm di matrici va a o'reilly ... http://docstore.mik.ua/orelly/webprog/pcook/ch04_26.htm

CONSIDERAZIONI:

• Il numero di cuochi e il numero di ricette sono gli stessi.

• Passando sopra una matrice 5 x 5 come qui diventerà molto grande molto veloce. (Vedi parte 2 da registrare breve)

La logica: Una permutazione di un array assegna un posto così come appena essere inclusi (cioè che combinazione fa), quindi perché non quindi assegnare ciascun chiave di una tale matrice per una ricetta, la permutazione garantisce che nessun cuoco viene ripetuto e le chiavi garantiscono che nessuna ricetta viene ripetuta.

Per favore fatemi sapere se ci sono miglioramenti o errori nel mio modo di pensare o nel mio codice, ma eccolo qui!

<?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

Prova questo

$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

io possa avere un punto di partenza per voi con questo algoritmo che cerca di scegliere i cuochi in base al loro rapporto del punteggio massimo per riassumere di sc minerali (cercando così di scegliere cuochi che sono veramente bravo a una ricetta, ma male al resto delle ricette per farlo ricetta)

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

Per il set di dati forniti, non trovare quello che sembra essere la risposta ottimale (35,33,5,4).Tuttavia, non è ancora perfetto, per esempio, con l'array:

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

La risposta ideale sarebbe (20,33,33,4), tuttavia questo algoritmo restituirebbe (35,33,5,4).

Ma dal momento che la questione è stato chiesto per le idee di dove cominciare, credo che questo, almeno potrebbe bastare come qualcosa da cui partire da: P

Answer 4

Spiacente, ma questo sta per essere più di un layout di logica rispetto al codice ...

non è del tutto chiaro se la matrice (1,2,3,4) sono i punteggi per il primo piatto o per la prima cuoca, ma mi sarebbe probabilmente utilizzare un array in modo tale che

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

asort() ogni array in modo che $ array [$ cook_id] = array ($ lowest_scored _dish, ..., $ più alto);

Considerare una preferenza ponderata per un cuoco particolare per fare di un piatto la differenza tra il punteggio del piatto migliore e un altro.

Come esempio molto semplice, cucina a, b, c e piatti 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 

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

Inizia con il cuoco 'a' che preferisce il piatto 0 sul piatto successivo migliore di 50 punti (peso). Anche Cook 'b' preferisce dih 0, ma con un peso di 0 sul piatto successivo. Quindi è probabile (anche se non è ancora certo che cuocere 'a' dovrebbe fare il piatto 0.

Considerare il piatto 0 da prenotare e passare a cucinare 'b'. Escludendo il piatto 0, il cuoco 'b' preferisce il piatto 1. No altro cuoco preferisce piatto 1, in modo da cucinare 'b' viene assegnato piatto 1.

Cook 'c' ottiene piatto 2 per impostazione predefinita.

Questo è un esempio molto pratico in cui ogni cuoco viene a cucinare qualcosa che è un personal max, ma spero che sia illustrativo di una logica che potrebbe funzionare.

Rendiamolo meno conveniente:

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

Inizia di nuovo con cuoco 'a' e vedere che 0 è preferito, ma questa volta con il peso 25. Cook 'b' preferisce con un peso di 50 e cuocere 'c' preferisce con un peso di 75. Cook 'c' vince il piatto 0.

Tornando all'elenco dei cuochi disponibili, 'a' preferisce 1 con un peso di 50, ma 'b' lo preferisce con il peso 0. 'a' ottiene il piatto 1 e 'b 'ottiene piatto 2.

Questo ancora non si prende cura di tutte le complessità, ma è un passo nella giusta direzione. A volte l'ipotesi fatta per la prima combinazione cuoco/piatto sarà errata.

modo meno conveniente:

$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' ottiene 0 dato che è il massimo e nessun altro che preferisce 0 ha un peso più elevato 'b' vince 1 con un peso di 149 'd' vince 2 poiche 'c' non ha una preferenza tra le opzioni disponibili 'c' ottiene 3

punteggio: 200 + 149 + 147 + 16 = 512

Mentre questo è una buona congettura che è riunito senza controllare ogni permutazione, i potrebbe essere sbagliato Da qui, chiedi: "Se un cuoco commercia con un altro cuoco, l'aumento totale?"

La risposta è sì, un (0) + d (2) = 200 + 16 = 216, ma una (2) + d (0) = 148 + 69 = 217.

lascio a voi di scrivere il codice per la "ipotesi migliore" utilizzando l'approccio ponderato, ma dopo che, qui è un buon inizio per voi:

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

non riesco a trovare un controesempio per mostrare che questo doesn' lavoro, ma sono sospettoso del caso in cui ($ array [$ cook1] [$ dish1] + $ array [$ cook2] [$ dish2]) == ($ array [$ cook1] [$ dish2 ] + $ array [$ cook2] [$ dish1])

Forse qualcun altro risponderà a questa domanda "E se?"

Data questa matrice, dove gli elementi tra parentesi sono i "picconi"

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

Se a1 + b2 == a2 + b1, quindi 'a' e 'b' non passerà piatti. Il caso non sono sicuro al 100% circa è se esiste una matrice tale che questa è una scelta migliore:

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

Come dal primo stato al secondo richiede due interruttori, il primo dei quali sembra arbitraria dal non cambia il totale. Ma solo passando attraverso questo cambiamento arbitrario si può fare l'ultimo passaggio.

Ho cercato di trovare un esempio 3x3 tale che in base al modello "preferenza ponderata" di cui sopra ho scritto, il primo sarebbe stato selezionato, ma anche tale che la reale selezione ottimale è data dal secondo. Non ero in grado di trovare un esempio, ma ciò non significa che non esiste. Non mi sento di fare più algebra matriciale adesso, ma forse qualcuno riprenderà da dove ho lasciato. Diamine, forse il caso non esiste, ma ho pensato di dover segnalare la preoccupazione.

Se funziona e si inizia con la scelta corretta, il codice precedente eseguirà solo un ciclo di 64 volte (8x8) per 8 cuochi/piatti. Se il plettro non è corretto e il primo cuoco cambia, passerà a 72. Se l'ottavo cuoco ha una modifica, è fino a 128. È possibile che il do-while esegua il loop più volte, ma dubito si alzerà vicino ai cicli della CPU necessari per sommare tutte le combinazioni 40k.