Wiskundig probleempje met combinaties

[Twazerty]

In java heb ik wat gemaakt wat voor mij formules genereert. Op dit moment genereerd het formules met 2 combinaties. Voorbeeld:
Rood
Groen
Blauw

Daarmee zijn de volgende combinaties mogelijk:

Rood-Rood
Rood-Groen
Rood-Blauw
Groen-Groen
Groen-Blauw
Blauw-Blauw

Zoals je ziet komt elke combinatie maar 1x voor. Dus Rood-Groen en Groen-Rood is hetzelfde. Dit heb ik zo opgelost in java:
for(int i = 0; i < kleuren.size(); i++){
for(int j = i; j < kleuren.size(); j++){

Bovenstaande code doet exact wat ik nodig heb. kleuren is in dit geval een ArrayList in java of een List in C#

Voor de eenvoud blijf ik nu praten met kleuren. In werkelijkheid zijn het audiobestanden. Met 10 verschillende kleuren heb ik 55 combinaties: 10+9+8+7+6+5+4+3+2+1

Maar nu wil ik een stap verder door met 3 combinaties te werken. Voorbeeld met 2 kleuren:
Rood-Rood-Rood
Rood-Rood-Groen
Rood-Groen-Groen
Groen-Groen-Groen

En volgens mij kan ik dit oplossen door hetzelfde truucje nogmaals toe te passen:
for(int i = 0; i < kleuren.size(); i++){
for(int j = i; j < kleuren.size(); j++){
for(int k = j; k < kleuren.size(); k++){

Maar voor dat ik dit uit ga voeren zou ik graag willen weten hoeveel combinaties ik heb met bv 10 kleuren. Mijn wiskunde is weggezakt en ik heb niet echt een idee hoe ik dit ook al weer uit moet rekenen. Wie kan mij helpen? want uitschrijven is geen optie

Dit zou ik willen weten omdat elke binnenste loop circa 5-10 minuten duurt. Dan kan ik van te voren bepalen hoeveel combinaties ik toelaat.

_{SG of PRG}

[disjfa]

3x2 = 6

Dus dan is 10x3 is 30 verschillende uitkomsten. Toch?

Nee, ik lul geloof ik. Dat is met unieke waardes. Dus je loopt er wat meer doorheen. 10x10x10.

[ Voor 43% gewijzigd door disjfa op 07-08-2009 13:31 ]

[roy-t]

Raar dat dit lang duurt want het gaat dus om 10 kleuren dus er zijn minder dan 10*10*10 combinaties dus dat zou echt geen 5 minuten moeten duren (zelfs geen 5ms).

Kun je het stukje code laten zien dat je nu hebt? Want dit stukje is niet volledig.

Verder kun je van te voren het aantal combinaties uitrekenen door een grafisch rekenmachine (online) te gebruiken. Als je wilt dat je 10 kleuren hebt en daar van alle unieke (maar volgorde is niet belangrijk) combinaties van 3 wilt hebben doe je dan

code:

10 nCr 3

In dit geval dus 120

[Matis]

Mijn wiskundig vermogen verteld mij dat je 10 boven 3 verschillende mogelijkheden hebt. (ben alleen even de terminologie vergeten)

maar er was een functie op mijn rekenmachine. Iets met Binomiale Permutatie en Binomiale Combinatie


edit: roy-t

[ Voor 4% gewijzigd door Matis op 07-08-2009 13:38 ]

[Verwijderd]

Zal dit dan niet (3!)^2 = 36 zijn? Klopt niet

Misschien heb je hier nog wat aan: Wikipedia: Permutatie
http://nl.wikipedia.org/wiki/Combinatie_(wiskunde)

Als je geen rekenmachine bij de hand hebt, kan je www.wolframalpha.com gebruiken.

[ Voor 35% gewijzigd door Verwijderd op 07-08-2009 13:40 ]

[Spinal]

Daar heb je geen GR voor nodig hoor
10 nCr 3 is "10 boven 3" en is (10!)/(3!(10-3)!) oftewel (10x9x8x7x6x5x4x3x2x1)/((3x2x1)(7x6x5x4x3x2x1))

edit: spuit 13

[ Voor 11% gewijzigd door Spinal op 07-08-2009 13:39 ]

[Twazerty]

Als het 10 nCr 3 moet zijn waarom komt er dan geen 55 uit als ik 10 nCr 2 doe?

Ik heb met 10 kleuren 55 resultaten gekregen. En 10 nCr 2 geeft 45

In elke inner loop word een proces gestart. Is niet relevant in dit topic.

Edit: Ik heb een GR voor mn neus liggen

[ Voor 9% gewijzigd door Twazerty op 07-08-2009 13:41 ]

[GlowMouse]

Twazerty schreef op vrijdag 07 augustus 2009 @ 13:40:
Als het 10 nCr 3 moet zijn waarom komt er dan geen 55 uit als ik 10 nCr 2 doe?

Ik heb met 10 kleuren 55 resultaten gekregen. En 10 nCr 2 geeft 45

Met combinaties tel je de dubbel-mogelijkheid niet: rood-rood, groen-groen, etc. Die moet je er nog bij optellen.

[ Voor 17% gewijzigd door GlowMouse op 07-08-2009 13:43 ]

[Matis]

GlowMouse schreef op vrijdag 07 augustus 2009 @ 13:42:
[...]

55 is fout

Je hebt combinaties en permutaties, je zult dus de verkeerde gepakt hebben. Bij de ene maakt de volgorde wel uit, bij de andere niet!

[The_Ghost16]

Twazerty schreef op vrijdag 07 augustus 2009 @ 13:40:
Als het 10 nCr 3 moet zijn waarom komt er dan geen 55 uit als ik 10 nCr 2 doe?

Ik heb met 10 kleuren 55 resultaten gekregen. En 10 nCr 2 geeft 45

In elke inner loop word een proces gestart. Is niet relevant in dit topic.

Edit: Ik heb een GR voor mn neus liggen

--

[ Voor 13% gewijzigd door The_Ghost16 op 07-08-2009 13:44 . Reden: zie hierboven ]

[Matis]

Het is dus het volgende:
http://www41.wolframalpha.com/input/?i=10+permutation+2
90 mogelijkheden
http://www41.wolframalpha.com/input/?i=10+combination+2
45 mogelijkheden

10 boven 3; geeft dus 120 bij een combinatie en 720 bij een permutatie!

[ Voor 46% gewijzigd door Matis op 07-08-2009 13:49 ]

[Twazerty]

GlowMouse schreef op vrijdag 07 augustus 2009 @ 13:42:
[...]

55 is fout

Nope 55 is niet fout. Ik heb exact wat ik moet hebben. 55 files en er ontbreekt niets. Er is ook niets dubbel.
10 kleuren geeft mij 55 files let op:

K10-K10
K10-K9
K10-K8
K10-K7
K10-K6
K10-K5
K10-K4
K10-K3
K10-K2
K10-K1
K9-K9
K9-K8
K9-K7
K9-K6
K9-K5
K9-K4
K9-K3
K9-K2
K9-K1
K8-K8
K8-K7
K8-K6
K8-K5
K8-K4
K8-K3
K8-K2
K8-K1
K7-K7
K7-K6
K7-K5
K7-K4
K7-K3
K7-K2
K7-K1
K6-K6
K6-K5
K6-K4
K6-K3
K6-K2
K6-K1
K5-K5
K5-K4
K5-K3
K5-K2
K5-K1
K4-K4
K4-K3
K4-K2
K4-K1
K3-K3
K3-K2
K3-K1
K2-K2
K2-K1
K1-K1
______
55 stuks

[Matis]

Dit is de totaalsom dat is iets heel anders dan aantal mogelijkheden

http://www41.wolframalpha.com/input/?i=1%2B2%2B3%2B...%2B10

[ Voor 29% gewijzigd door Matis op 07-08-2009 13:51 ]

[GlowMouse]

GlowMouse schreef op vrijdag 07 augustus 2009 @ 13:42:
[...]

Met combinaties tel je de dubbel-mogelijkheid niet: rood-rood, groen-groen, etc. Die moet je er nog bij optellen.

En dat wordt een probleem bij langere ketens.

Het algemene geval kun je het schrijven als som van binomiaalcoefficiënten. Ik heb alleen nu geen tijd om het uit te zoeken.

[Twazerty]

Matis schreef op vrijdag 07 augustus 2009 @ 13:50:
Dit is de totaalsom dat is iets heel anders dan aantal mogelijkheden

http://www41.wolframalpha.com/input/?i=1%2B2%2B3%2B...%2B10

Zover is mijn wiskunde dus weggezakt
Uit mijn openingspost kon je ook halen wat ik bedoelde:

quote: mezelf

Daarmee zijn de volgende combinaties mogelijk:

Rood-Rood
Rood-Groen
Rood-Blauw
Groen-Groen
Groen-Blauw
Blauw-Blauw

Ik kan mij overigens niet herrinneren dat ik op school ooit heb gewerkt met 3 combinaties. Alleen met 2. (nCr en nPr)

[ Voor 10% gewijzigd door Twazerty op 07-08-2009 13:54 ]

[hstoker]

Waarom programmer je niet de drie loopjes, en laat je in de middelste loop een tellertje meelopen? Lijkst me het snelst zonder al te veel na te hoeven denken

[Matis]

Twazerty schreef op vrijdag 07 augustus 2009 @ 13:53:
Ik kan mij overigens niet herrinneren dat ik op school ooit heb gewerkt met 3 combinaties. Alleen met 2. (nCr en nPr)

We begrijpen elkaar denk ik verkeerd. Ik heb het over twee verschillende manieren van tellen, namelijk nCr (combinaties, volgorde is niet belangrijk) en nPr (permutaties, volgorde doet er wel degelijk toe).

Wat jij wilt is combinatie, alleen dan met de dubbele;

Dus (10 nCr 2) + 10 en dat is precies 55

Voor 10 boven 3 doe je het zelfde; (10 nCr 3) + ...

Alleen weet ik niet of dat er nu 10, 20 of 100 bij moeten...

[ Voor 10% gewijzigd door Matis op 07-08-2009 14:00 ]

[Twazerty]

hstoker schreef op vrijdag 07 augustus 2009 @ 13:53:
Waarom programmer je niet de drie loopjes, en laat je in de middelste loop een tellertje meelopen? Lijkst me het snelst zonder al te veel na te hoeven denken

Als het te veel combinaties blijken dan verkwist ik teveel tijd met onnodig processen. Dit hoeft trouwens maar eenmalig te lopen. Als het klaar is heb ik het nooit meer nodig. Maar als ik 3 combi's heb gehad ga ik naar vier combi's en daar moet ik zeker weten hoeveel x het process word uitgevoerd. Dan krijgen we dit:
Rood-Rood-Rood-Rood
Rood-Rood-Rood-Groen
enz

Het is niet de bedoeling dat mijn pc hier weken staat te lopen. Dan verminder ik het aantal combinaties wel.

[hstoker]

Twazerty schreef op vrijdag 07 augustus 2009 @ 14:01:
[...]


Als het te veel combinaties blijken dan verkwist ik teveel tijd met onnodig processen. Dit hoeft trouwens maar eenmalig te lopen. Als het klaar is heb ik het nooit meer nodig. Maar als ik 3 combi's heb gehad ga ik naar vier combi's en daar moet ik zeker weten hoeveel x het process word uitgevoerd. Dan krijgen we dit:
Rood-Rood-Rood-Rood
Rood-Rood-Rood-Groen
enz

Het is niet de bedoeling dat mijn pc hier weken staat te lopen. Dan verminder ik het aantal combinaties wel.

Ik bedoelde ook niet dat je in je binnenste loop al daadwerkelijk gaat doen wat je van plan bent (wat vijf minuten blijkt te duren..), maar om alleen een tellertje op te hogen. Dan moet je binnen enkele seconden je antwoord hebben dacht ik zo...

[Twazerty]

hstoker schreef op vrijdag 07 augustus 2009 @ 14:03:
[...]

Ik bedoelde ook niet dat je in je binnenste loop al daadwerkelijk gaat doen wat je van plan bent (wat vijf minuten blijkt te duren..), maar om alleen een tellertje op te hogen. Dan moet je binnen enkele seconden je antwoord hebben dacht ik zo...

Aja

maar even op papier uitrekenen is ook altijd mooi. Kunnen we weer onze kennis bijschaven. En blijkbaar is dit probleem moeilijker als ik dacht.

[ Voor 16% gewijzigd door Twazerty op 07-08-2009 14:04 ]

[Jewest]

De oplossing is aantalkleuren ^ aantal "bits"

dus 3 ^ 1 vakje ==> 3
dus 3 ^ 2 vakjes ==> 9
dus 3 ^ 3 vakjes ==> 27

dus 10 kleuren ^ 5 vakjes ==> 1e5 mogelijkheden

stom idee, maar waarom roep je je functie niet gewoon recursief aan?
en elke keer retourneer je gewoon de mogelijke opties? en plak je je eigen opties er aan vast?
Hetzelfde wat je in je for lus doet maar dan in 1 functie waar in je het begin en einde opgeeft?

(just my 2 cents)

[Twazerty]

Ik heb de index waarden nodig uit alle 3 de loops.

Maar het antwoord is 220.

Maar waarom moet je nu 100 optellen bij 10 nCr 3??

[Jewest]

Bedenk net dat dit wel erg traag kan worden.

[Matis]

Jewest schreef op vrijdag 07 augustus 2009 @ 14:06:
De oplossing is aantalkleuren ^ aantal "bits"

Maar zo werkt het algoritme niet, wat TS wil is gewoon X loopjes met N mogelijkheden.

Ik zal even wat pseudo code tikken

Twazerty schreef op vrijdag 07 augustus 2009 @ 14:09:
Ik heb de index waarden nodig uit alle 3 de loops.

Maar het antwoord is 220.

Maar waarom moet je nu 100 optellen bij 10 nCr 3??

Ja, dat weet ik dus niet, ik dacht 10^2 ofzo, weet niet

Hier iig pseudo code die ook netjes 55 geeft:

PHP:

<?php
define("MOGELIJKHEDEN", 10);
define("LUSJES", 3);
$counter = 0;
for($i = MOGELIJKHEDEN; $i > 0; $i--)
{
    for($n = MOGELIJKHEDEN; $n >= $i; $n--)
    {
        printf("%d %d <br>", $i, $n);
        $counter++;
    }
}
echo $counter;
?>

[ Voor 51% gewijzigd door Matis op 07-08-2009 14:15 ]

[roy-t]

Twazerty schreef op vrijdag 07 augustus 2009 @ 14:09:
Ik heb de index waarden nodig uit alle 3 de loops.

Maar het antwoord is 220.

Maar waarom moet je nu 100 optellen bij 10 nCr 3??

Zoals boven wordt uitgelegd en waar ik geen rekening mee gehouden had is dat je "Combinaties wil met terug leggen" zodat dus RRR mogelijk is.

10 ncr 2 rekent dus zonder terugleggen uit en geeft je dus 45 combinaties maar alle 10 combinaties van 2x dezelfde kleur (RR, GG, BB etc..) mis je dus nog.

Voor 10 ncr 3 zit het nog even ingewikkelder, daar moet je 10ncr 3 + 10 voor RRR GGG BBB etc + 10* (10 ncr2) hebben (voor RGG, BRR, GRR etc).

Je formule is dus iets als 10 ncr 3 + 10*10nrc2 + 10*10ncr1. Om zoveel te tellen als jij wilt voor 3 uit 10. Je snapt dat het truukje bij je 10ncr 4 + 10*10ncr3 + etc... neemt.

Tenminste als ik zo even nadenk is dit juist


Edit: wie plempt er even leuke code neer om via een recursieve definitie een instelbaar aantal geneste loopjes te hebben?

[ Voor 6% gewijzigd door roy-t op 07-08-2009 14:21 ]

[Matis]

roy-t schreef op vrijdag 07 augustus 2009 @ 14:20:
Edit: wie plempt er even leuke code neer om via een recursieve definitie een instelbaar aantal geneste loopjes te hebben?

Ik,

C++:

#define N 10 //De size of the window
void QuickPerm(void)
{
    unsigned char a[N], p[N + 1];
    unsigned char alphabet[] = "ABCDEFGH";
    register unsigned int i, j, tmp; // Upper Index i; Lower Index j

    for (i = 0; i < N; i++) // initialize arrays; a[N] can be any type
    {
        a[i] = i + 1; // a[i] value is not revealed and can be arbitrary
        p[i] = i;
    }
    p[N] = N; // p[N] > 0 controls iteration and the index boundary for i
    //display(a, 0, 0);   // remove comment to display array a[]
    i = 1; // setup first swap points to be 1 and 0 respectively (i & j)
    while (i < N)
    {
        p[i]--; // decrease index "weight" for i by one
        j = i % 2 * p[i]; // IF i is odd then j = p[i] otherwise j = 0
        tmp = alphabet[j]; // swap(a[j], a[i])
        alphabet[j] = alphabet[i];
        alphabet[i] = tmp;
        display(alphabet, j, i); // remove comment to display target array a[]
        i = 1; // reset index i to 1 (assumed)
        while (!p[i]) // while (p[i] == 0)
        {
            p[i] = i; // reset p[i] zero value
            i++; // set new index value for i (increase by one)
        } // while(!p[i])
    } // while(i < N)
} // QuickPerm()

Stukje dat ik ooit geschreven heb om ALLE mogelijkheden met een bepaald alphabet te maken

Zie ook Wikipedia: Cryptex

[Twazerty]

roy-t schreef op vrijdag 07 augustus 2009 @ 14:20:
[...]


Zoals boven wordt uitgelegd en waar ik geen rekening mee gehouden had is dat je "Combinaties wil met terug leggen" zodat dus RRR mogelijk is.

10 ncr 2 rekent dus zonder terugleggen uit en geeft je dus 45 combinaties maar alle 10 combinaties van 2x dezelfde kleur (RR, GG, BB etc..) mis je dus nog.

Voor 10 ncr 3 zit het nog even ingewikkelder, daar moet je 10ncr 3 + 10 voor RRR GGG BBB etc + 10* (10 ncr2) hebben (voor RGG, BRR, GRR etc).

Je formule is dus iets als 10 ncr 3 + 10*10nrc2 + 10*10ncr1. Om zoveel te tellen als jij wilt voor 3 uit 10. Je snapt dat het truukje bij je 10ncr 4 + 10*10ncr3 + etc... neemt.

Tenminste als ik zo even nadenk is dit juist


Edit: wie plempt er even leuke code neer om via een recursieve definitie een instelbaar aantal geneste loopjes te hebben?

Klopt ook niet want als 10ncr2 al 45 is en je gaat vermenigvuldigen met 10 zit je al op 450

Zo recursieve definitie ben ik ook wel benieuwd naar. Zou niet weten hoe ik die moet maken in dit geval. Wat belangrijk is is dat van iedere loop de index bekend moet zijn. Dus 5 loops heb ik ook 5 index waarden nodig maar volgens mij is zo'n recursieve loop in mijn opbouw zowiso niet mogelijk want ik spreek direct files aan en dan word het toch wel verdomd lastig om de juiste filenames te creeren zonder met vele loops te werken. Maar dan nog ben ik wel benieuwd

@ hierboven

Eerlijk gezegd snap ik er niet veel van. Ik ken de syntax van C++ dan ook niet.

[ Voor 4% gewijzigd door Twazerty op 07-08-2009 14:29 ]

[jstruik]

Wanneer je naar 3 combinaties toe wilt werken heb je
* 10 enkele (10 boven 1), die je aanvult met dezelfde letter
* 45 dubbele (10 boven 2), die je aanvult met de ene of de andere letter => 45*2
* 120 standaard (10 boven 3), die je niet aanvult

Voor 4 is het dus volgens mij (10 boven 4) + 3* (10 boven 3) + 2*(10 boven 2) + 1*(10 boven 1) = 210+3*120+2*45+10 =670
wie rekent dit even na in code?

[ Voor 6% gewijzigd door jstruik op 07-08-2009 14:47 ]

[Matis]

http://www.geocities.com/permute_it/01example.html Hier staat die code, hij is niet recursief, maar misschien begrijp je enigszins wat er bedoeld wordt

[T-mo]

Je bent hier volgens mij op zoek naar een herhalingcombinatie (combinatie met teruglegging), zie Wikipedia: Combinatoriek (de onderste dus).

met n = 10 en k=3 krijg je (12 boven 3), waar 220 uitkomt en met n = 10 en k=4 krijg je (13 boven 4) = 715 combinaties

[RayNbow]

/spuit11, zie T-mo boven me

Twazerty schreef op vrijdag 07 augustus 2009 @ 14:09:
Ik heb de index waarden nodig uit alle 3 de loops.

Maar het antwoord is 220.

Maar waarom moet je nu 100 optellen bij 10 nCr 3??

Herhalingscombinatie
Aantal trekkingen: k
Aantal elementen in verzameling: n
Aantal mogelijke combinaties: C(k+n-1, k)

In het geval van k=3, n=10 krijg je dus C(12, 3) = 220.

[ Voor 6% gewijzigd door RayNbow op 07-08-2009 15:00 ]

[Matis]

RayNbow schreef op vrijdag 07 augustus 2009 @ 14:59:
In het geval van k=3, n=10 krijg je dus C(12, 3) = 220.

Dus toch, immers is 11 nCr 2 --> 55.

Nu nog *even* recursief maken!

[RayNbow]

Matis schreef op vrijdag 07 augustus 2009 @ 15:05:
[...]

Dus toch, immers is 11 nCr 2 --> 55.

Nu nog *even* recursief maken!

Haskell code...

Haskell:

-- g berekent alle oplossingen voor de vergelijking:
--      x_1 + x_2 + ... + x_n = r
g 0 0 = [[]]
g 0 _ = []
g n r = [ x:xs | x <- [0..r], xs <- g (n-1) (r-x) ]

kleuren = ["K"++show i | i <- [1..10]]
alleCombos = map (concat . zipWith (flip replicate) kleuren) $ g 10 2

ghci> mapM_ (putStrLn.unwords) alleCombos
K10 K10
K9 K10
K9 K9
K8 K10
K8 K9
K8 K8
K7 K10
K7 K9
K7 K8
K7 K7
K6 K10
K6 K9
K6 K8
K6 K7
K6 K6
K5 K10
K5 K9
K5 K8
K5 K7
K5 K6
K5 K5
K4 K10
K4 K9
K4 K8
K4 K7
K4 K6
K4 K5
K4 K4
K3 K10
K3 K9
K3 K8
K3 K7
K3 K6
K3 K5
K3 K4
K3 K3
K2 K10
K2 K9
K2 K8
K2 K7
K2 K6
K2 K5
K2 K4
K2 K3
K2 K2
K1 K10
K1 K9
K1 K8
K1 K7
K1 K6
K1 K5
K1 K4
K1 K3
K1 K2
K1 K1

Als we nu naar de oorspronkelijke aanpak van de TS kijken:

Twazerty schreef op vrijdag 07 augustus 2009 @ 13:26:
Zoals je ziet komt elke combinatie maar 1x voor. Dus Rood-Groen en Groen-Rood is hetzelfde. Dit heb ik zo opgelost in java:

code:

for(int i = 0; i < kleuren.size(); i++){
    for(int j = i; j < kleuren.size(); j++){

Zien we dus dat ie per trekking alle kleuren naloopt. Dit is met herhalingscombinatie's niet handig. Het is makkelijker om per kleur die je hebt te bepalen hoe vaak die kleur moet voorkomen.

Heb je dus de kleuren Rood, Groen en Blauw en 5 dingen die je moet voorzien van een kleur, dan bepaal je dus hoeveel dingen je rood verft, hoeveel groenen hoeveel blauw:

ghci> g 3 5
[[0,0,5],[0,1,4],[0,2,3],[0,3,2],[0,4,1],[0,5,0],[1,0,4],[1,1,3],[1,2,2],[1,3,1]
,[1,4,0],[2,0,3],[2,1,2],[2,2,1],[2,3,0],[3,0,2],[3,1,1],[3,2,0],[4,0,1],[4,1,0]
,[5,0,0]]

Een mogelijke inkleuring als bijv. [1,0,4] moet je dan dus lezen als 1 ding rood, 0 dingen groen en 4 dingen blauw: "R-B-B-B-B"

[ingdas]

Ik weet dat Haskell krachtig is voor zulke dingen maar ik slaag er niet in om dit te lezen. Voor de geinteresseerden die net zoals ik Haskell niet machtig zijn, een recursieve javacode voor het probleem:

Java:

package math;
 
import java.util.ArrayList;
import java.util.Arrays;
 
public class CombinationRe {
 
    ArrayList<Object[]> alist = new ArrayList<Object[]>();
    
 
    public CombinationRe(Object[] objs, int p) {
 
        int slotIndex = 0;
        int maxValue = objs.length - 1;
        int[] array = new int[p];
        fillSlot(objs, array, slotIndex, maxValue);
    }
 
    public void fillSlot(Object[] obj, int[] array, int slotIndex, int maxValue) {
 
        if (slotIndex == array.length) {
            // print the combo
            //   CombinationRe.spewArray(alist,obj,a); no need anymore
            Object[] tempobj = new Object[array.length];
            for (int i = 0; i < tempobj.length; i++) {
                int index = array[i];
                tempobj[i] = obj[index];
            }
            alist.add(tempobj);
        } else {
            int minValue = 0;
            if (slotIndex > 0) {
                minValue = array[slotIndex - 1];
            }
            for (int i = minValue; i <= maxValue; i++) {
 
                array[slotIndex] = i;
                fillSlot(obj, array, slotIndex + 1, maxValue);
            }
        }
    }
 
    public static void main(String[] args) {
        // n  =  5  and we want combinations of 3  
        Object[] str = {"A", "B", "C", "D", "E"};
 
        CombinationRe cb = new CombinationRe(str, 3);
 
        ArrayList<Object[]> alist = new ArrayList<Object[]>();
        alist = cb.alist;
 
        for (Object[] val : alist) {
            System.out.println(Arrays.toString(val));
        }
         
        System.out.println("number of element created " +alist.size());
    }
}

Uitvoer:
[A, A, A]
[A, A, B]
[A, A, C]
[A, A, D]
:
[C, E, E]
[D, D, D]
[D, D, E]
[D, E, E]
[E, E, E]
number of element created 35


Bron: http://forums.sun.com/thread.jspa?threadID=5300684

[RayNbow]

Nog een oplossing in Python:

Python:

def down_from(n):
    return xrange(n,-1,-1)

def CombinationsR(items, k):
    if items and k > 0:                          # was: if items and k >= 0:
        item = items[0]
        remainder = items[1:]
        for i in down_from(k):
            for combination in CombinationsR(remainder,k-i):
                yield [item]*i + combination
    elif k==0:                                   # was: elif not items and k==0:
        yield []

>>> print '\n'.join(map(str, CombinationsR('rgb',2)))
['r', 'r']
['r', 'g']
['r', 'b']
['g', 'g']
['g', 'b']
['b', 'b']
>>> len(list(CombinationsR('abcde',3)))
35

Ik wilde eig. eerst een Java versie brouwen, maar het ontbreken van een yield feature hield me tegen.

[ Voor 7% gewijzigd door RayNbow op 12-08-2009 16:39 . Reden: Simpelere base cases ]

[Wolfboy]

Sinds Python 2.6 zit die functie ingebouwd, zie hier de broncode: http://docs.python.org/li...ml#itertools.combinations

Maar... anders kan je het zo zelf schrijven: (geinspireerd door RayNbow z'n code)

Python:

def CombinationsR(items, k):
    if k != 0:
        for i in xrange(len(items)):
            for combination in CombinationsR(items[i:], k-1):
                yield [items[i]] + combination
    else:
        yield []

def Combinations(items, k):
    if k != 0:
        for i in xrange(len(items)):
            for combination in Combinations(items[:i] + items[i+1:], k-1):
                yield [items[i]] + combination
    else:
        yield []

Eenvoudiger dan dat kan ik 'm even niet krijgen in Python

[ Voor 21% gewijzigd door Wolfboy op 12-08-2009 13:16 ]

[RayNbow]

Wolfboy schreef op woensdag 12 augustus 2009 @ 12:37:
Sinds Python 2.6 zit die functie ingebouwd, zie hier de broncode: http://docs.python.org/li...ml#itertools.combinations

Die is alleen zonder herhalingen.

Maar... anders kan je het zo zelf schrijven: (geinspireerd door RayNbow z'n code)

Python:

def CombinationsR(items, k):
    if k != 0:
        for i in xrange(len(items)):
            for combination in CombinationsR(items[i:], k-1):
                yield [items[i]] + combination
    else:
        yield []

# *snip*

Die's best interessant (al kostte het me ff om 'm te doorgronden). Je kiest in feite non-deterministisch k keer een element i uit de lijst items. Maar wanneer je element i gekozen heb, besluit je om in het vervolg niet meer elementen 0..i - 1 te kiezen.

Een Haskell versie geinspireerd door WoLpH's code:

Haskell:

import Data.List
combinationsR _  0 = [[]]
combinationsR xs k = [y:c | ys@(y:_) <- tails xs, c <- combinationsR ys (k-1)]

[Wolfboy]

RayNbow schreef op woensdag 12 augustus 2009 @ 17:05:
[...]

Die is alleen zonder herhalingen.

Python:

import itertools
CombinationsR = lambda items, k: set(tuple(sorted(x)) for x in itertools.combinations(items*k, k))

[ Voor 11% gewijzigd door Wolfboy op 13-08-2009 12:53 ]