Cookies op Tweakers

Tweakers is onderdeel van DPG Media en maakt gebruik van cookies, JavaScript en vergelijkbare technologie om je onder andere een optimale gebruikerservaring te bieden. Ook kan Tweakers hierdoor het gedrag van bezoekers vastleggen en analyseren. Door gebruik te maken van deze website, of door op 'Cookies accepteren' te klikken, geef je toestemming voor het gebruik van cookies. Wil je meer informatie over cookies en hoe ze worden gebruikt? Bekijk dan ons cookiebeleid.

Meer informatie
Toon posts:

[PHP] Functie om meest gunstige combinatie te vinden

Pagina: 1
Acties:

Vraag


  • xilent_xage
  • Registratie: februari 2005
  • Laatst online: 07-06 07:01
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: 18-06 21:09
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?

  • xilent_xage
  • Registratie: februari 2005
  • Laatst online: 07-06 07:01
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?

  • xilent_xage
  • Registratie: februari 2005
  • Laatst online: 07-06 07:01
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: 00:26
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: 11:02

Creepy

Moderator Devschuur®

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: 19-06 23:48
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: 18-06 21:09
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: 07-06 07:01
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: 09:16
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


Apple iPad Pro (2021) 11" Wi-Fi, 8GB ram Microsoft Xbox Series X LG CX Google Pixel 5a 5G Sony XH90 / XH92 Samsung Galaxy S21 5G Sony PlayStation 5 Nintendo Switch Lite

Tweakers vormt samen met Hardware Info, AutoTrack, Gaspedaal.nl, Nationale Vacaturebank, Intermediair en Independer DPG Online Services B.V.
Alle rechten voorbehouden © 1998 - 2021 Hosting door True