Geek asks and answers

Limited Cartesian Product Computing - PHP

EDIT 1 - after publication, I found out that the main question is how to find CARTESIAN PRODUCT (now go google), but not only because I don’t want every perm, I want to find Cartesian products that use the same Subarray Key never more than once for each edit. And my “additional” question is more about how to minimize the workload required by a Cartesian product (I have to say, assuming a small error rate) -

Imagine ... I have four cooks and four recipes, each cook has points for each recipe, and today I would like each cook to cook one dish (but did not have to do it twice), and the decision should be based on the best (highest final grade) permutation for all four (so maybe the cook won't do everything possible).

I put the data in a multidimensional array as such

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

  • it has the same number of values ​​in each basement as the number of sub-arrays (if that helps)

  • in fact, the number of sub-arrays will reach a maximum of 8 (max perms therefore = 8 !, approximately 40,000, and not 8 ^ 8, because many combinations are not allowed)

  • choosing the availability of data in this format is flexible if it helps

, (.. ) , .

- [0] [1] [2] [3] subarrayKey [0] [1] [2] [3] , , .--

, newArray (35,33,5,4)// , [2] [0]

-, , , , , .

, ? .

SO . PHP 2D Array

2 , , , , ( )

+5
4

- , , , .

perm o'reilly... 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/>";  




?>
0

, , ...

, (1,2,3,4) , , , ,

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

asort() , $array [$ cook_id] = array ($ lower_scored_dish,..., $maximum);

, .

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

'a', 0 50 (). Cook 'b' dih 0, 0 . , , ( , cook 'a' 0.

0, , 'b'. 0, "" 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. Cook '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, max , 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] [$ dish1] + $array [$ cook2] [$ dish2])   ==   ($ array [$ cook1] [$ dish2] + $array [$ cook2] [$ dish1])

, - ", ?"

, ""

[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. , 128. , do-while , , 40k.

+2

, ( , -, , , )

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

But since the question asked ideas about where to start, I think this, at least, may be enough to start: P

+1
source

try it

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

More articles:


All Articles