[C# - Unity vraag] Alle optelmanieren in één Integer List.

[Jvann]

Hallo allemaal,

Ikzelf ben nog wat noob in codes en formules, en ik zat wat leuks te maken maar ik kwam tot een probleem.
Ik probeer hier het probleem zo duidelijk mogelijk te maken

1. Ik heb een Integer list met een aantal nummers, de hoeveelheid nummers in deze list kan verschillen (In mijn geval van 2 nummers tot en met 6 nummers, maar misschien dat dit in de toekomst meer word).

2. Alle nummers in deze Integer list hebben maximaal de waarde 6 en zijn niet negatief (Dus 1, 2, 3, 4, 5, 6).

3. Ikzelf wil met een formule (Loops en dergelijk) bereiken dat elk optelresultaat in een aparte Integer list word gezet. Voorbeeld:

- Ik heb 3 nummers met de waarden 3, 4, en 5 in de eerste integer list.
- De getallen 3, 4 en 5 komen in de aparte integer list, want deze staan in de eerste.
- Het getal 7 komt ook in de aparte integer list, want 3 en 4 is samen 7.
- Het getal 8 komt ook in de aparte integer list, want 3 en 5 is samen 8.
- Het getal 9 komt ook in de aparte integer list, want 4 en 5 is samen 9.
- Het getal 12 komt ook in de aparte integer list, want 3, 4 en 5 samen is 12.
- Het is NIET zo dat je 7 (3 + 4) ook kan optellen met 9 (4 + 5), want 7 en 9 staan niet in de eerste Integer list.
- Het werkt alleen met optellen (+), dus geen min (-), keer (*) etcetera.

4. Alle eindgetallen komen dus in één aparte Integer list, ik wil ook dat alle getallen er maar 1x in mogen maar dat kan ik zelf wel.

Ik heb wat op internet rond lopen kijken maar ik heb eigenlijk weinig gevonden.
Weet je het antwoord niet in C# voor Unity maar in een andere taal, dan ben ik ook nieuwschierig naar dit antwoord aangezien dit best makkelijk vertaalbaar is.
Hopelijk is mijn vraag duidelijk, en hopelijk weten jullie een antwoord.

Alvast bedankt.

EDIT, misschien maakt dit het een beetje duidelijker (Denk het niet, maar oke):

[ Voor 8% gewijzigd door Jvann op 19-10-2015 16:08 ]

[Woy]

Je bent opzoek naar de term Combinatoriek ( combinatorics in het engels ).

Ik snap niet helemaal wat je wil, maar volgens mij kan je het gewoon als een bitpattern behandelen. Je originele lijst heeft bijvoorbeeld 6 entry's dan kan je loopen van 0 tot 2^6 ( 6 bits ). Als je de binaire waarde van die getallen bekijkt tel je alle getallen op waarbij de bit op die positie 1 is.

[Camulos]

Dit lijkt op een aantal vraagstukken die ik weleens voor prog-challenges heb gemaakt.
Wat Woy al zegt, je bent op zoek naar combinatorics

Even wat dingen structureren
Input: integer list, waar enkel positieve getallen in staan
Transformatie: Tel alle mogelijke combinaties bij elkaar op.
Output: integer list, waarbij alle getallen maximaal 1 keer voorkomen

Je voorbeeld is eigenlijk niet zo goed, omdat de echte complexiteit bij tenminste 4 getallen begint omdat je daar combinaties krijgt die je niet direct lineair op kan lossen.

Voorbeeld strategie:
Input: 2, 3, 4, 5 ,6
- optellen 1 getal: 2, 3, 4, 5, 6
- optellen 2 getallen: 2+3, 2+4, 2+5, 2+5, 2+6, 3+4, 3+5, 3+6, 4+5, 4+6, 5+6
- optellen 3 getallen: 2+3+4, 2+3+5, 2+3+6, 2+4+5, 2+4+6, 2+5+6, 3+4+5, 3+4+6, 3+5+6, 4+5+6
- optellen 4 getallen: 2+3+4+5, 2+3+4+6, 2+3+5+6, 2+4+5+6, 3+4+5+6
- optellen 5 getallen: 2+3+4+5+6

Zorgt dat je de tussentijdse optelsommen opslaat in bijvoorbeeld een hashset zodat er geen dubbele getallen in je lijst kan staan.

Persoonlijk zou ik een functie schrijven die exact op bovenstaande manier te werk gaat. Deze is onafhankelijk van de input-size. Voor de sub-size groottes kun je af met een forloop.. maar het daadwerklijke optellen van de verschillende combinaties zou ik doen dmv een recursieve functie.

Heb bewust geen code gepost omdat OP geen code-voorbeeld heeft gepost wat hij zelf al geprobeerd heeft

[ Voor 7% gewijzigd door Camulos op 21-10-2015 06:22 . Reden: alle optellingen nu wel uitgeschreven ]

[Woy]

Camulos schreef op dinsdag 20 oktober 2015 @ 22:16:
Persoonlijk zou ik een functie schrijven die exact op bovenstaande manier te werk gaat. Deze is onafhankelijk van de input-size. Voor de sub-size groottes kun je af met een forloop.. maar het daadwerklijke optellen van de verschillende combinaties zou ik doen dmv een recursieve functie.

Ik zou het zeker niet recursief oplossen, het is veel eenvoudiger om het als bitpattern te behandelen. Op die manier kun je het zelfs in één linq statement oplossen die het gewoon iteratief doet ( Of gewoon met twee geneste for loopjes )

[RobIII]

Even iets heel anders:
Jvann in "\[C# - Unity vraag] Alle optelmanieren in één Integer List."

Jvann schreef op maandag 19 oktober 2015 @ 15:56:
C# voor Unity

Ik zou even heel dat specifieke gezoek naar Unity achterwege laten. AFAIK is Unity gewoon een engine die je (o.a.) met C# kunt gebruiken (hoewel me er iets van bij staat dat 't 'scriptable in C#' is, maar dat was volgens mij ergens in 't jaar kneup), maar zou je niet de "volledige C#" tot je beschikking hebben: het is gewoon een algoritmisch probleem dat je probeert op te lossen dat los staat van de taal. Als je overgaat tot het bouwen van een specifieke implementatie in taal X komen er taal-specifieke details / trucjes / eigenaardigheden aan te pas, maar in de basis ben je gewoon op zoek naar een algoritme; boeie of dat opgelost wordt "in/voor Unity met C#".

Dan: hou er rekening mee dat je met Woy's implementatie al snel 'vast' zit aan lists (<- ook daar weer: implementatiedetail; het is gewoon een 'set' van getallen) van max 32 of 64 getallen/bits (int/long, en, wederom: implementatiedetail) en als je mogelijk langere lijsten hebt in de toekomst (uit de TS: "maar misschien dat dit in de toekomst meer word") dan kom je al gauw daar weer omheen aan 't werken (misschien dat je dan wat aan BigIntegers hebt (maar dan lever je geheid in op performance*), misschien zit je dan diep in de nesten dus: zoek dat even goed uit) en dat kan je danig in de weg gaan zitten. Daarbij moet wel de kanttekening dat als je 2³², of erger, 2⁶⁴ of nog meer combinaties moet gaan doorrekenen je wel andere problemen hebt; dit geldt dus alleen maar als je bepaalde combinaties wil doorrekenen en niet het hele "spectrum".

En datzelfde geldt ook voor Camulos' idee: bij wat grotere lijsten heb je daar potentieel een risico op een stack overflow (dan heb je 't wel over andere orde groottes dan "6 integers", maar ik zeg het toch even). Hier neig ik ook, net als Woy, toch echt naar iteratief.

Ik zeg niet dat er niets te zeggen is voor beide oplossingen/ideeën maar het is wél iets om rekening mee te houden en voor jezelf even uit te zoeken wat een realistische max. van het aantal getallen in de set is (640Kb ought to be enough... ) en bedenk dan dat elk getal dat in die set erbij komt een verdubbeling is in aantal combinaties ofwel O(n²). Bekijk dus ook even of 't écht nodig is om élke combinatie door te rekenen (dat is het namelijk vaak niet) of dat je niet wat slimmer met de set getallen en de benodigde berekeningen kunt omgaan.

Lang verhaal kort: zoek eerst een algoritme, denk dan na over of/hoe de implementatie die bij je daadwerkelijke probleem pas en ga dan pas implementeren.

* Iets met premature optimization enzo, maar als je dit in een 'tight loop' gaat draaien wil je daar misschien wel bij stilstaan als je X FPS wil blijven halen

[ Voor 23% gewijzigd door RobIII op 21-10-2015 03:56 ]

[Camulos]

RobIII schreef op woensdag 21 oktober 2015 @ 00:24:
Even iets heel anders:
Jvann in "\[C# - Unity vraag] Alle optelmanieren in één Integer List."

[...]
Lang verhaal kort: zoek eerst een algoritme, denk dan na over of/hoe de implementatie die bij je daadwerkelijke probleem pas en ga dan pas implementeren.

^^ wat hij zegt En daarbij helpt het dus als je gewoon een heldere probleem omschrijving hebt en de stappen eens uit schrijft (zoals in mijn vorige post). Daarna kun je dus beslissen hoe je het probleem algoritmisch gaat tackelen. Als je kan vertellen hoe je het analoog/met de hand zou kunnen oplossen; dan kun je het in principe ook programmeren. Het gaat om het spotten van patronen en daarna optimaliseren van oplossingen.

@Rob/Woy: Ik zie inderdaad (nu pas ) dat het idd ook op bitpatterns, maar ook gewoon met normale loops af kan; zonder recursie

[ Voor 10% gewijzigd door Camulos op 21-10-2015 06:44 ]