Optimale verdeling bingokaarten

[Onbekend]

Voor een spelletje thuis wil ik een bingokaartgenerator schrijven.

Nu is dit volgens mij niet zo moeilijk. Er kan straks worden ingegeven welke nummers er uitgedeeld moeten worden, hoeveel nummers er op een bingokaart staan, en hoeveel bingokaarten er gegenereerd moeten worden.
Voor elke gegenereerde kaart moet ik natuurlijk kijken of de kaart wel uniek is.
De controle hierop is niet zo moeilijk, want ik kan gewoon de andere gegenereerde kaarten afgaan op de zelfde combinaties.

Nu kan de volgende situatie ontstaan:
Gebruik de getallen 1 t/m 10, genereer 4 kaarten en zet 5 getallen op een kaart.
Kaart 1: 1,2,3,4,5
Kaart 2: 1,2,3,4,6
Kaart 3: 1,2,3,5,6
Kaart 4: 1,2,3,6,7

Met een beetje ongeluk worden eerst de getallen 8, 9 en 10 getrokken die niemand op zijn kaart heeft staan.
Ik heb liever dat de getallen op de kaarten gelijkmatig uit de gehele range worden gehaald. Zoiets dus:
Kaart 1: 1,2,3,4,5
Kaart 2: 6,7,8,9,10
Kaart 3: 1,3,5,7,9
Kaart 4: 2,4,6,8,10
Welk getal er nu wordt getrokken, er zijn nu altijd wel mensen die een getal op de kaart hebben staan.

Zelf had ik gedacht om eerst te bepalen hoe vaak een willekeurig getal dan op de kaarten voor zou komen.
Daarna zit ik elk getal dat aantal keer (minus het aantal keer dat het getal is uitgegeven) in een array, om vervolgens met een randomgenerator een willekeurig getal eruit te pikken.
Helaas kom ik dan voor het probleem te zitten dat ik bijvoorbeeld voor de laatste kaart nog de keuze heb uit drie zessen. Dit kan ik natuurlijk niet gebruiken en dan zou ik de overgebleven getallen met de al bestaande kaarten moeten uitwisselen.
Dit lijkt mij dan ook geen juiste methode. Hebben jullie een idee om dit aan te pakken?

[frickY]

Als je een goede random-number generator pakt, zoals die tegenwoordig in vrijwel alle talen wel aanwezig is, lijkt het me heel sterk dat je tegen dit probleem aanloopt.

Maar misschien is het een idee om het andersom te doen. Zet eerst alle cijfers op alle kaarten, en haal dan random cijfers van random kaarten af tot het maximum resteert.
Elke keer dat je een nummer hebt weggestreept maak je de kans dat dat nummer valt kleiner, zodat de kans op verschillende kaarten groter wordt.

[ Voor 17% gewijzigd door frickY op 26-09-2010 14:06 ]

[Baldertt]

Wat jij zegt, maar dan met een array beginnende met 4x de getallen 1t/m10. Je kiest random een getal uit die array, stel dat het het getal 5 is. Dat getal haal je uit de array, dus je houdt 4x 1,2,3,4,6,7,8,9,10 over en 3x5. De kans dat het volgende random getal (dus het 1e getal voor de 2e kaart) 5 is is nu kleiner dan voordat je het eerste getal koos. Zo krijg je uiteindelijk een beter gespreide verdeling.
Je blijft ook niet zitten met getallen die je aan het einde uit moet gaan wisselen, want er blijven altijd genoeg unieke getallen over.
Simpel, maar volgens mij voldoende voor wat je wilt bereiken.

[Voutloos]

Ik zou het genereren van kaarten juist lekker simpel houden, dan gaat het wellicht gewoon goed genoeg.

Als er toch gesleuteld moet worden, kan je ook $x kaarten teveel genereren, en dan $x keer de minst unieke kaart verwijderen.

[CMG]

Ik verveelde me en vond het wel leuk om snel wat te maken; enige wat je nog moet doen is ff zorgen dat er geen duplikaat kaarten in staan bedenk ik me achteraf:

C#:

        void Test()
        {
            List<List<int>> Lists = GenerateLists(1, 10, 5, 4);
            foreach (List<int> Card in Lists)
            {
                Card.Sort();
                Debug.Write("Card: ");
                foreach (int Val in Card)
                {
                    Debug.Write(Val + " ");
                }
                Debug.WriteLine("");
            }
        }
        List<List<int>> GenerateLists(int Min, int Max, int AmountPerCard, int AmountOfCards)
        {
            if (Max < Min)
                throw new ArgumentException("Max cannot be lower thne Min");
            List<List<int>> Cards = new List<List<int>>();
            int Required = AmountOfCards * AmountPerCard;
            int RangeLength = (Max - Min) + 1;
            List<int> Range = new List<int>();
            for (int i = Min; i <= Max; i++)
            {
                Range.Add(i);
            }
            int FullItterations = (int)Math.Floor((Double)Required / RangeLength);
            int Rest = Required - (FullItterations * RangeLength);
            List<int> Pool = new List<int>();
            for (int i = 0; i < FullItterations; i++)
            {
                Pool.AddRange(Range);
            }
            for (int i = Min; i < (Min + Rest); i++)
            {
                Pool.Add(i);
            }
            Random Rnd = new Random((int)(DateTime.Now.Ticks % Int32.MaxValue));
            for (int Card = 0; Card < AmountOfCards; Card++)
            {
                List<int> BingoCard = new List<int>();
                for (int i = 0; i < AmountPerCard; i++)
                {
                    int Index = Rnd.Next(0, Pool.Count - 1);
                    int Val = Pool[Index];
                    while (BingoCard.Contains(Val))
                    {
                        // instead of generating a new random, just shift one, this reduces the amount of possible mismatches.
                        Index++;
                        // Prevent the index going out of bounds
                        if (Index >= Pool.Count)
                            Index = 0;
                        Val = Pool[Index];
                    }
                    BingoCard.Add(Val);
                    // Remove from pool
                    Pool.RemoveAt(Index);
                }
                Cards.Add(BingoCard);
            }
            return Cards;
        }

[ Voor 1% gewijzigd door CMG op 26-09-2010 20:08 . Reden: was Pool.Remove vergeten :o ]

[Onbekend]

Het is inmiddels gelukt. Ik zie nu pas dat er een stuk code in C is gepost. Hoewel ik niet helemaal uit die code kom, werkt mijn geschreven stukje vrijwel hetzelfde:

Eerst bepalen hoeveel keer ik welk nummer uit wil geven.
Vervolgens in een array zetten en sorteren.
Daarna ga ik in random volgorde elke speler langs om hem het eerstvolgende nummer uit de array te geven.
Nadat ik elke speler heb gehad (en dus elke speler 1 nummer heeft), ga ik weer random alle spelers langs.

Uiteindelijk heeft elke speler schijnbaar willekeurige getallen, verdeeld over de gehele reeks beschikbare cijfers.

Met een paar keer testen met de code kwam ik erachter dat de kans op spelers met identieke getallen vrij klein is. Dus dat is echt niet zo'n groot probleem.

[Voutloos]

Onbekend schreef op maandag 27 september 2010 @ 22:22:
Met een paar keer testen met de code kwam ik erachter dat de kans op spelers met identieke getallen vrij klein is. Dus dat is echt niet zo'n groot probleem.

Ik betwijfel alleen of je die kans echt kleiner gemaakt hebt.