Alle mogelijke sommen van getallen in een array berekenen

[Anoniem: 50825]

Probleem
Ik heb een aantal getallen, en ik wil weten welke getallen ik moet optellen om tot een bepaalde uitkomst te komen.

Voorbeeld
Stel ik heb deze lijst met getallen:

C#:

int[] a = { 75, 50, 25, 45, 5, 20 };

Nu wil ik weten welke getallen ik bij elkaar moet optellen om bijvoorbeeld als uitkomst 100 te krijgen.
Dat kan in dit gevallen met
75 + 25
75 + 5 + 20
50 + 25 + 5 + 20
50 + 45 + 5
etc

Vraag
Maar hoe bereken je nou zoiets? Ik heb ook niet echt een idee hoe zo'n wiskundig probleem heet, dus googlen vind ik lastig deze keer.

[RobIII]

Permutaties
Overigens is je omschrijving beperkt; mag ik bijvoorbeeld ook 5 + 5 + 5 ... + 5 = 100 doen? Dus een getal hergebruiken?

[ Voor 81% gewijzigd door RobIII op 25-08-2008 22:07 ]

[RedPixel]

Het woord dat je zoekt is "permutaties", en dat kun je recursief oplossen...
edit: spuit11

[ Voor 10% gewijzigd door RedPixel op 25-08-2008 22:09 ]

[roy-t]

Volgens mij heeft iemand anders een paar maanden geleden dezelfde vraag gesteld (is het voor een opdracht misschien)

Anyway als je het doel getal al weet discard je eerst alle getallen die samen met het kleinste getal al boven het target getal komen. (dus als het kleinste getal 15 is discard je alle getalen groter dan targetgetal - 15.

Daarna kun je nog zoiets bedenken om getallen die iig te klein zijn te filteren (bijvoorbeeld kleinste getal + grootste getal wat er nog is zijn die te klein dan discard je het kleinste getal en ga zo maar door net zolang tot je het getal gevonden hebt.

Vrij simpel algoritme, net in 5 minuten bedacht en je hoeft niet alle getallen @ random te doorzoeken .

[Anoniem: 50825]

Thanks jongens!

[Anoniem: 50825]

roy-t schreef op maandag 25 augustus 2008 @ 22:10:
(is het voor een opdracht misschien)

Nee hoor, gewoon een vaker voorkomend probleem.

Anyway als je het doel getal al weet discard je eerst alle getallen die samen met het kleinste getal al boven het target getal komen. (dus als het kleinste getal 15 is discard je alle getalen groter dan targetgetal - 15.

Daarna kun je nog zoiets bedenken om getallen die iig te klein zijn te filteren (bijvoorbeeld kleinste getal + grootste getal wat er nog is zijn die te klein dan discard je het kleinste getal en ga zo maar door net zolang tot je het getal gevonden hebt.

Vrij simpel algoritme, net in 5 minuten bedacht en je hoeft niet alle getallen @ random te doorzoeken .

Thanks!

[RayNbow]

Subset sum

[RedPixel]

Ik zou een recursieve functie schrijven. Als invoer geef je dan de getallen die al gebruikt zijn en welke er nog over zijn, en je probeert telkens het getal eerste wél of niet te gebruiken, en dan nog even kijken of het al hoger dan of gelijk aan 100 is geworden.

edit: bovenstaande werkt trouwens alleen als je getallen 1x mag gebruiken, of als alle getallen positief zijn.

[ Voor 17% gewijzigd door RedPixel op 25-08-2008 22:18 ]

[RemcoDelft]

wwwhizz schreef op maandag 25 augustus 2008 @ 22:08:
Het woord dat je zoekt is "permutaties", en dat kun je recursief oplossen...
edit: spuit11

Afhankelijk van het aantal getallen kan dat nog best lang gaan duren... 1 miljoen getallen recursief doorrekenen is een enorme hoeveelheid rekenwerk! Als het er 1000 zijn is het natuurlijk geen enkel probleem.

[RedPixel]

RemcoDelft schreef op maandag 25 augustus 2008 @ 22:20:
[...]

Afhankelijk van het aantal getallen kan dat nog best lang gaan duren... 1 miljoen getallen recursief doorrekenen is een enorme hoeveelheid rekenwerk! Als het er 1000 zijn is het natuurlijk geen enkel probleem.

Vaak kun je de boom al eerder afkappen doordat je te hoog bent gekomen, bovendien kun je alle te grote getallen er aan het begin al uit gooien. Maar als je een miljoen getallen hebt onder de 10, en je zoekt alle mogelijkheden om 100000 te vormen, tsja, dan ben je hoe dan ook lang bezig (je moet immers veel resultaten krijgen...)

[writser]

Zoals anderen al aangeven: je moet inderdaad alle permutaties bij langs. Dat is recursief het makkelijkst te implementeren. Iets in de trand van wat whizz geeft is in de meeste talen maar een paar regels code. Bedenk wel dat dit qua rekentijd enorm snel uit de klauwen loopt. Voor elk getal in je lijst zijn er twee mogelijkheden:

- Wel meenemen in de som
- Niet meenemen in de som.

Van een lijstje met 25 elementen zijn dat 2^25 (ongeveer 33 miljoen) permutaties die je moet controleren. Nou kun je je algoritme misschien wel iets slimmer maken, maar het blijft erg veel rekenwerk. Je kan beter de vraag aanpassen.

Maar goed, alles is al uitstekend uitgelegd door anderen. Waarom post ik hier nog?

[Anoniem: 50825]

writser schreef op maandag 25 augustus 2008 @ 23:50:
Van een lijstje met 25 elementen zijn dat 2^25 (ongeveer 33 miljoen) permutaties die je moet controleren. Nou kun je je algoritme misschien wel iets slimmer maken, maar het blijft erg veel rekenwerk. Je kan beter de vraag aanpassen.

De vraag is gelukkig ook iets minder breed dan een willekeurig aantal elementen:

Het kan bijvoorbeeld gaan om betalingen die bij elkaar horen.
Er is 1 hoofdbetaling, en daar kunnen een of meerdere andere betalingen bij horen. Dat kan een 1 op 1 relatie zijn, een hoofdbetaling van 100,- is gekoppeld aan een andere betaling van 100,-.
Maar het kan ook zo zijn dat er vier andere betalingen zijn, waarvan er 2 stuks tot 100,- optellen, en op een andere manier tellen 3 van die vier ook op tot 100,-.

Dat is al een stuk minder rekenwerk.

[Patriot]

roy-t schreef op maandag 25 augustus 2008 @ 22:10:
Volgens mij heeft iemand anders een paar maanden geleden dezelfde vraag gesteld (is het voor een opdracht misschien)

Anyway als je het doel getal al weet discard je eerst alle getallen die samen met het kleinste getal al boven het target getal komen. (dus als het kleinste getal 15 is discard je alle getalen groter dan targetgetal - 15.

Daarna kun je nog zoiets bedenken om getallen die iig te klein zijn te filteren (bijvoorbeeld kleinste getal + grootste getal wat er nog is zijn die te klein dan discard je het kleinste getal en ga zo maar door net zolang tot je het getal gevonden hebt.

Vrij simpel algoritme, net in 5 minuten bedacht en je hoeft niet alle getallen @ random te doorzoeken .

Het eerste is zonder meer waar, maar het laatste niet omdat je ook meer dan twee getallen bij elkaar op kan tellen.

vb:
5 is het laagste getal
80 is het hoogste getal
5 + 80 = 85

Volgens jouw algoritme zou de 5 komen te vervallen, maar als er een getal 15 is dan kan 5 + 15 + 80 gewoon en moet 5 blijven bestaan.

[Soultaker]

RemcoDelft schreef op maandag 25 augustus 2008 @ 22:20:
1 miljoen getallen recursief doorrekenen is een enorme hoeveelheid rekenwerk! Als het er 1000 zijn is het natuurlijk geen enkel probleem.

Ik geloof dat sommige mensen niet echt gevoel hebben voor hoe snel dit soort exponentiële functies groeien. Het aantal permutaties van duizend getallen is 1000 faculteit, dat is in de orde van 10¹⁵⁸ (ja, dat is een 1 met 158 nullen!); dat is volstrekt onmogelijk om langs te gaan. In de praktijk is 15 faculteit ongeveer het maximum haalbare, en dan nog alleen als je er een paar uur voor uit wil trekken.

Natuurlijk kun je in sommige gevallen wel recursief zoeken en ondertussen handig afkappen, maar ik zou er niet vanuit gaan dat dat voldoende ordes-van-grootte winst oplevert om werkbaar te zijn. In de praktijk werkt alle permutaties afzoeken (eventueel met wat afkappen) dus alleen voor relatief kleine aantallen getallen.

In de praktijk kun je dit soort problemen beter aanpakken met een pseudo-polynomiaal algoritme. De link die RayNbow gaf, geeft daar meer informatie over (zie Pseudo-polynomial dynamic programming solutions). Als je met integers werkt, kom je dan op een complexiteit van het aantal getallen vermenigvuldigt met de absolute som van de getallen; meestal is dat wel binnen een paar miljoen, en dat is goed te doen binnen een paar seconde en met een paar megabyte geheugen.

Kortom: de standaardaanpak is dynamisch programmeren, niet recursief zoeken.

[.oisyn]

Soultaker schreef op dinsdag 26 augustus 2008 @ 00:55:
[...]

Ik geloof dat sommige mensen niet echt gevoel hebben voor hoe snel dit soort exponentiële functies groeien. Het aantal permutaties van duizend getallen is 1000 faculteit, dat is in de orde van 10¹⁵⁸ (ja, dat is een 1 met 158 nullen!);

Echter gaat het niet om permutaties. Als je gaat permuteren zet je de getallen alleen in andere volgorde, maar dat is hier onbelangrijk. In feite is het juist een bitpatroon van 1000 bits. Een 1 betekent dat dat getal meedoet, een 0 niet. Writser gaf het al aan. "Slechts" 2¹⁰⁰⁰ ~= 10³⁰¹ dus.

1000 faculteit is overigens een heel stuk groter dan 10¹⁵⁸ (ongeveer 10²⁵⁶⁷, als mijn arbitrary precision arithmetic class me niet in de steek laat )

offtopic:
40238726007709377354370243392300398571937486421071463254379991042993851239862902059204420848696
94048004799886101971960586316668729948085589013238296699445909974245040870737599188236277271887
32519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783
6478499770124766328910994 * 10²²⁵⁸ om exact te zijn

[ Voor 22% gewijzigd door .oisyn op 26-08-2008 01:38 ]

[writser]

Maar het gaat hier niet om permutaties in die zin, want de volgorde van de getallen is niet relevant. Dit probleem is op te lossen in O(2^n). Dat is veel, veel sneller dan O(n!). Maar nog steeds langzaam voor lijsten met meer dan ~25 elementen. Oisyn was me uiteraard weer voor.

Het kan bijvoorbeeld gaan om betalingen die bij elkaar horen.

Ik hoop voor je dat dit geen probleem is waar je in de praktijk mee bent opgezadeld. Klinkt als een beroerd bijgehouden administratie.

[ Voor 33% gewijzigd door writser op 26-08-2008 01:27 ]

[Soultaker]

.oisyn schreef op dinsdag 26 augustus 2008 @ 01:12:
Echter gaat het niet om permutaties. Als je gaat permuteren zet je de getallen alleen in andere volgorde, maar dat is hier onbelangrijk. In feite is het juist een bitpatroon van 1000 bits

Klopt, maar RobIII, wwwhizz, writser begonnen over permutaties. In de praktijk is het allebei veel te veel. Exponentieel met basis 2 kun je misschien tot 40 elementen in plaats van 15, maar dat schaalt natuurlijk ook niet. (Ik hou altijd aan: 2^N < N! < N^N (N>2); wat een aardige inschatting geeft.)

1000 faculteit is overigens een heel stuk groter dan 10¹⁵⁸ (ongeveer 10²⁵⁶⁷, als mijn arbitrary precision arithmetic class me niet in de steek laat )

Ah, ik had blijkbaar 100 faculteit gepost. Niet dat 't veel uitmaakt voor 't argument. =)

offtopic:
40238726007709377354370243392300398571937486421071463254379991042993851239862902059204420848696
94048004799886101971960586316668729948085589013238296699445909974245040870737599188236277271887
32519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783
6478499770124766328910994 * 10²²⁵⁸ om exact te zijn

offtopic:
Denk dat je class stuk is, want Python komt op
40238726007709377354370243392300398571937486421071463254379991042993851239862902059204420848696
94048004799886101971960586316668729948085589013238296699445909974245040870737599188236277271887
32519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783
6478499770124766328898359;
merk op dat de laatste zes cijfers verschillen.

Python:

reduce(mul, range(1,1001))/(10**2258)

[ Voor 37% gewijzigd door Soultaker op 26-08-2008 02:29 ]

[Anoniem: 255888]

Probeer ook even een stukje code te schrijven het in polynomiale tijd doet, would make you a millionaire

[roy-t]

Patriot schreef op dinsdag 26 augustus 2008 @ 00:33:
[...]


Het eerste is zonder meer waar, maar het laatste niet omdat je ook meer dan twee getallen bij elkaar op kan tellen.

vb:
5 is het laagste getal
80 is het hoogste getal
5 + 80 = 85

Volgens jouw algoritme zou de 5 komen te vervallen, maar als er een getal 15 is dan kan 5 + 15 + 80 gewoon en moet 5 blijven bestaan.

Ah shit klopt die optie had ik gemist, en maakt het helaas meteen 10000x zo ingewikkeld, nouja iig kun je getallen scheiden bij het begin

[RobIII]

Soultaker schreef op dinsdag 26 augustus 2008 @ 02:21:
Klopt, maar RobIII, wwwhizz, writser begonnen over permutaties.

In de TS ging het dan ook over 6 getalletjes

[0rbit]

Wil je één oplossing of alle oplossingen?

[writser]

Mr_Atheist schreef op dinsdag 26 augustus 2008 @ 10:55:
Wil je één oplossing of alle oplossingen?

Dat maakt niet zoveel uit, je zal toch alle mogelijk oplossingen moeten doorzoeken.

[Santford]

writser schreef op dinsdag 26 augustus 2008 @ 13:20:
[...]

Dat maakt niet zoveel uit, je zal toch alle mogelijk oplossingen moeten doorzoeken.

Niet als je kan stoppen met zoeken zodra je aan de voorwaarde hebt voldaan

[writser]

Tuurlijk zal je programma gemiddeld wat sneller zijn, maar a) in de meeste gevallen zal het niet significant veel sneller zijn en b) je kan nooit garanderen dat je programma snel is. Want er is altijd het worst-case scenario. Niet voor niets ga je daar meestal van uit bij het analyseren van een algoritme.

[.oisyn]

Je redenatie klopt niet. Als je namelijk op zoek bent of er een antwoord bestaat kun je een heuristiek toepassen die gericht de zoekboom afloopt naar het antwoord. Natuurlijk is de worst-case performance gelijk (er is geen antwoord), maar als je naar alle antwoorden zoekt zal het altijd worst-case zijn, terwijl het voor 1 antwoord significant sneller kan zijn.

[Voutloos]

Niet specifiek voor dit probleem: Belangrijk is dan ook af hoe de antwoorden gedistribueerd zijn over de zoekruimte.

[Soultaker]

.oisyn schreef op woensdag 27 augustus 2008 @ 11:11:
Natuurlijk is de worst-case performance gelijk (er is geen antwoord), maar als je naar alle antwoorden zoekt zal het altijd worst-case zijn, terwijl het voor 1 antwoord significant sneller kan zijn.

Het blijft zo dat als de complexiteit van het pseudopolynomiale algoritme kleiner is dan die van het exponentiële algoritme, het vinden van één oplossing sneller is dan van allemaal (worst case namelijk exponentieel). In dat geval kun je met het pseudopolynomiale algoritme veel sneller aantonen dat er geen oplossing is, juist omdat je alle mogelijkheden niet langs hoeft te gaan.

[pkuppens]

Mosterd na de maaltijd?

Wikipedia: Knapsack problem

met een pseudo polynomiaal oplossings algoritme...

(en met subset als specifieke variant)

[.oisyn]

Soultaker schreef op dinsdag 26 augustus 2008 @ 02:21:

offtopic:
Denk dat je class stuk is, want Python komt op
40238726007709377354370243392300398571937486421071463254379991042993851239862902059204420848696
94048004799886101971960586316668729948085589013238296699445909974245040870737599188236277271887
32519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783
6478499770124766328898359;
merk op dat de laatste zes cijfers verschillen.

Python:

reduce(mul, range(1,1001))/(10**2258)

offtopic:
Je hebt gelijk. Althans, m'n class is niet stuk, maar m'n operator<<() verantwoordelijk voor de uitvoer wel (die een benadering van 1/10 gebruikt, maar die benadering niet uitrekende in de resolutie van het uit te voeren getal, maar in slechts 256 bits, terwijl het resultaat van 1000! in 7552 bits werd opgeslagen ). De echte waarde moet zijn:

40238726007709377354370243392300398571937486421071463254379991042993851239862902059204420848696
94048004799886101971960586316668729948085589013238296699445909974245040870737599188236277271887
32519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783
64784997701247663288983595573543251318532395846307555740911426241747434934755342864657661166779
73966688202912073791438537195882498081268678383745597317461360853795345242215865932019280908782
97308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426
23613141250878020800026168315102734182797770478463586817016436502415369139828126481021309276124
48963599287051149649754199093422215668325720808213331861168115536158365469840467089756029009505
37616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399
73628075013783761530712776192684903435262520001588853514733161170210396817592151090778801939317
81141945452572238655414610628921879602238389714760885062768629671466746975629112340824392081601
53780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745
99264295658174662830295557029902432415318161721046583203678690611726015878352075151628422554026
51704833042261439742869330616908979684825901254583271682264580665267699586526822728070757813918
58178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180
61213855860030143569452722420634463179746059468257310379008402443243846565724501440282188525247
09351906209290231364932734975655139587205596542287497740114133469627154228458623773875382304838
65688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193
89701786004081188972991831102117122984590164192106888438712185564612496079872290851929681937238
86426148396573822911231250241866493531439701374285319266498753372189406942814341185201580141233
44828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389
86355427719674282224875758676575234422020757363056949882508796892816275384886339690995982628095
61214509948717012445164612603790293091208890869420285106401821543994571568059418727489980942547
42173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004
15369010593398383577793941097002775347200000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000