[PHP] Functie om meest gunstige combinatie te vinden

[xilent_xage]

Hoi,

Ik heb een geneste array, bijvoorbeeld:

PHP:

    public $test = array(
        "appel"=>array(
            array("a", "b", "c"),
            array("d", "e", "f")
        ),
        "banaan"=>array(
            array("a"),
            array("d")
        ),
        "peer"=>array(
            array("f"),
            array("d")
        ),
        "citroen"=>array(
            array("a"),
            array("g")
        )
    );

Hiermee hou ik bij in welke kastjes het fruit mag worden opgeborgen. In mijn voorbeeld zijn de kastjes oneindig groot In sommige gevallen moet een stuk fruit in 1 kastje worden opgeborgen, in andere gevallen in meerdere. Elke array die onder een stuk fruit hangt, bevat een geldige opbergcombinatie, maar je mag steeds maar 1 combinatie kiezen. Dus:

-Een appel mag in kast a+b+c, of in kast d+e+f. Een appel mag dus niet alleen in kast a, of in kast a, e, en f: alleen de genoemde combinaties zijn een geldige optie.
-Een citroen mag in kast a of in kast g, niet in beiden.

Ik moet op zoek naar de indeling waarbij het kleinste aantal verschillende kistjes wordt gebruikt voor alle fruitsoorten samen. Omdat ik met een groot aantal combinaties te maken krijg is het fijn als de code ook nog een beetje efficient is.,

Ik ben al de hele dag aan het kloten met recursieve functies, maar kom er niet lekker uit. Graag jullie hulp!

[foxgamer2019]

Ik snap het even niet, waarom noem je dan die kast dan niet 'a-b-c'?

Je kunt in jou voorbeeld ook niet echt lekker combineren lijkt me. Het kan wel, maar waarom niet gewoon unieke kasten?

[xilent_xage]

foxgamer2019 schreef op zondag 4 november 2018 @ 22:13:
Ik snap het even niet, waarom noem je dan die kast dan niet 'a-b-c'?

Je kunt in jou voorbeeld ook niet echt lekker combineren lijkt me. Het kan wel, maar waarom niet gewoon unieke kasten?

Omdat citroenen ook in kast 'a' mogen. Stel dat je alleen citroenen en appels zou hebben, dan heb je de volgende opties:

appels in kast a+b+c en citroenen in kast a => 3 kasten gebruikt
appels in kast d+e+f en citroenen in kast a => 4 kasten gebruikt
appels in kast a+b+c en citroenen in kast g => 4 kasten gebruikt
appels in kast d+e+f en citroenen in kast g => 5 kasten gebruikt

De bovenste combinatie is dus het efficientst. Idealiter zou ik alle geldige combinaties op aantal gebruikte kasten willen kunnen sorteren, en bijv de 10 slimste combinaties tonen...

[foxgamer2019]

Even een stapje verder, wanneer komt iets in KastA en wanneer in KastB? Is dat at random?

[xilent_xage]

Ik snap je vraag niet helemaal, maar misschien helpt dit: De array toont de geldige opberglocaties.

Een appel kan dus op 2 manieren worden opgeborgen:

in kast a EN kast b EN kast C

of

in kast d EN kast e EN kast F

[Sizzla]

ik zou beginnen met een kleine testdataset zoals jou voorbeeld, en code maken die gewoon alle combinaties eens aftest. De code telt het aantal bakjes per combinatie en indien het aantal kleiner is dan de voorgaande onthoud je die.

indien enkele testen al slagen voor eens simpele dataset, kan je die eens loslaten op je volledige. indien het niet performant is zou ik proberen te paralleliseren, en pas indien dit nog niet snel genoeg gaat, eens nadenken hoe een optimaler algoritme zou kunnen werken

[Creepy]

xilent_xage schreef op zondag 4 november 2018 @ 22:08:
.,

Ik ben al de hele dag aan het kloten met recursieve functies, maar kom er niet lekker uit. Graag jullie hulp!

Misschien goed om wat stukjes code die je al hebt te delen zodat we beter kunnen helpen en kunnen zien waar je nu niet uit komt.

[TomsDiner]

Even heel stom...

Alle vier de stukken fruit zijn in het antwoord aanwezig.

Alle stukken fruit hebben twee opruim alternatieven....

Dan zijn er maar 2^4 oplossingen na te rekenen, toch? Dat zijn 16 mogelijke oplossingen...

En dat gedoe met arrays.... Is het niet simpeler om een integer de waarde 1 of 2 te geven?

Dus A=1 is voor Appels alternatief 1.
En A=2 os voor Appels atternatief 2.

En als je dan met arrays wil gaan werken, zou ik het omdraaien.

A[1]={1,1,1,0,0,0}
A[2]={0,0,0,1,1,1}

B[1]={1,0,0,0,0,0}
B[2]={0,0,0,1,0,0}

enzovoort. Dan optellen.

[eric.1]

xilent_xage schreef op zondag 4 november 2018 @ 22:08:
Omdat ik met een groot aantal combinaties te maken krijg is het fijn als de code ook nog een beetje efficient is.

Hoe groot is je uiteindelijke dataset? En waarom gebruik je een geneste array?

Als je dataset niet zo groot is kan je net zo goed alle mogelijke combinaties afgaan, brute-force idee . De combinatie met de minst verschillende kastjes; winnaar.

Anders zou ik (om te beginnen) de top X grootste arrays selecteren (van verschillende stukken "fruit"), daarvan de meest gunstige combinatie pakken (quick win) en dan de rest zo efficient mogelijk erbij voegen. Om het van daaruit te optimalizeren.

Hoe dacht je zelf dit aan te pakken?

Al zal je vast niet de eerste zijn die zoiets doet, er zijn vast al bestaande algoritmes bruikbaar voor deze use-case.

[Hopscotch]

PHP:

function go (array $input) {
    return help([], $input);
}

function help($used, $toPlace) {
    if(empty($toPlace)) {
        return $used;
    }
    $firstKey = array_keys($toPlace)[0];
    return min(array_map(function($item) use ($used, $toPlace, $firstKey) {
        foreach($item as $cabinet) {
            $used[$cabinet][] = $firstKey;
        }
        return help($used, array_slice($toPlace, 1));
    }, $toPlace[$firstKey]));
}

geeft de optimale indeling terug met per kastje wat erin zit

PHP:

array(4) {
  ["a"]=>
  array(2) {
    [0]=>
    string(5) "appel"
    [1]=>
    string(7) "citroen"
  }
  ["b"]=>
  array(1) {
    [0]=>
    string(5) "appel"
  }
  ["c"]=>
  array(1) {
    [0]=>
    string(5) "appel"
  }
  ["d"]=>
  array(2) {
    [0]=>
    string(6) "banaan"
    [1]=>
    string(4) "peer"
  }
}

[xilent_xage]

Bedankt voor alle hulp. De uitdaging is dat ik in de praktijk te maken krijg met zeer grote datasets. Om maar even bij de testdata te blijven: 60 stuks fruit met meestal 60-70 geldige combinaties per fruitsoort, van ongeveer 250 kastjes. Klinkt niet als belachelijk grote aantallen, maar het aantal mogelijke combnaties wordt al snel heel groot.

daarom ben ik op zoek naar een slimme strategie ipv domweg alle mogelijkheden uitrekenen

[jmzeeman]

Je moet de mogelijkheden als een boom zien (ja ja een fruit boom ). Er zijn legio zoek algoritmen om zo'n boom wat efficiënter te doorzoeken. In dit geval zou ik eerst is een simpele best first search proberen.

Simpel gezegd komt dat er op neer dat:
Je begint met geen fruit aan de wortel van de boom en op elk niveau van de boom komt er een soort fruit bij met een tak voor alle opties voor kastjes. Elk knooppunt in de boom heeft een score die het aantal kastjes voor het pad aangeeft. Je vult de boom niet in een keer maar bekijkt alleen steeds de mogelijke volgende stappen op de volledige breedte van je boom. Je evalueert dan welke volgende stap de beste score heeft en diepst in de boom zit net zolang totdat je bij de oplossing bent.