Toon posts:

[PHP] Functie om meest gunstige combinatie te vinden

Pagina: 1
Acties:

Vraag


  • xilent_xage
  • Registratie: Februari 2005
  • Laatst online: 06-01 20:03
Hoi,

Ik heb een geneste array, bijvoorbeeld:

PHP:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    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!

Beste antwoord (via xilent_xage op 06-11-2018 10:40)


  • Hopscotch
  • Registratie: September 2015
  • Laatst online: 28-09-2021
PHP:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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"
  }
}

Alle reacties


  • foxgamer2019
  • Registratie: Februari 2009
  • Niet online
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?

Forza Horizon 5? Voeg mij toe op Xbox Live. :)


  • xilent_xage
  • Registratie: Februari 2005
  • Laatst online: 06-01 20:03
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
  • Registratie: Februari 2009
  • Niet online
Even een stapje verder, wanneer komt iets in KastA en wanneer in KastB? Is dat at random?

Forza Horizon 5? Voeg mij toe op Xbox Live. :)


  • xilent_xage
  • Registratie: Februari 2005
  • Laatst online: 06-01 20:03
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
  • Registratie: Januari 2009
  • Laatst online: 15:22
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
  • Registratie: Juni 2001
  • Laatst online: 16:31

Creepy

Tactical Espionage Splatterer

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.

"I had a problem, I solved it with regular expressions. Now I have two problems". That's shows a lack of appreciation for regular expressions: "I know have star problems" --Kevlin Henney


  • TomsDiner
  • Registratie: November 2014
  • Laatst online: 16-07-2022
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
  • Registratie: Juli 2014
  • Nu online
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.

Acties:
  • Beste antwoord
  • 0Henk 'm!

  • Hopscotch
  • Registratie: September 2015
  • Laatst online: 28-09-2021
PHP:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
  • Registratie: Februari 2005
  • Laatst online: 06-01 20:03
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
  • Registratie: April 2007
  • Laatst online: 26-01 16:12
Je moet de mogelijkheden als een boom zien (ja ja een fruit boom :P). 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.
Pagina: 1


Tweakers maakt gebruik van cookies

Tweakers plaatst functionele en analytische cookies voor het functioneren van de website en het verbeteren van de website-ervaring. Deze cookies zijn noodzakelijk. Om op Tweakers relevantere advertenties te tonen en om ingesloten content van derden te tonen (bijvoorbeeld video's), vragen we je toestemming. Via ingesloten content kunnen derde partijen diensten leveren en verbeteren, bezoekersstatistieken bijhouden, gepersonaliseerde content tonen, gerichte advertenties tonen en gebruikersprofielen opbouwen. Hiervoor worden apparaatgegevens, IP-adres, geolocatie en surfgedrag vastgelegd.

Meer informatie vind je in ons cookiebeleid.

Sluiten

Toestemming beheren

Hieronder kun je per doeleinde of partij toestemming geven of intrekken. Meer informatie vind je in ons cookiebeleid.

Functioneel en analytisch

Deze cookies zijn noodzakelijk voor het functioneren van de website en het verbeteren van de website-ervaring. Klik op het informatie-icoon voor meer informatie. Meer details

janee

    Relevantere advertenties

    Dit beperkt het aantal keer dat dezelfde advertentie getoond wordt (frequency capping) en maakt het mogelijk om binnen Tweakers contextuele advertenties te tonen op basis van pagina's die je hebt bezocht. Meer details

    Tweakers genereert een willekeurige unieke code als identifier. Deze data wordt niet gedeeld met adverteerders of andere derde partijen en je kunt niet buiten Tweakers gevolgd worden. Indien je bent ingelogd, wordt deze identifier gekoppeld aan je account. Indien je niet bent ingelogd, wordt deze identifier gekoppeld aan je sessie die maximaal 4 maanden actief blijft. Je kunt deze toestemming te allen tijde intrekken.

    Ingesloten content van derden

    Deze cookies kunnen door derde partijen geplaatst worden via ingesloten content. Klik op het informatie-icoon voor meer informatie over de verwerkingsdoeleinden. Meer details

    janee