[C#]generování náhodných čísel bez opakování

[themrmaros]

Zdravím, mám takový problém. Lámu si hlavu nad tím jak mám napsat jeden program. Přesně zadání je takové:

Načti délku pole, vytvoř jej a naplň náhodnými čísly rozsahu 1-velikostpole tak, aby se žádné z čísel neopakovalo dvakrát.

Vymyslel jsem kód přidaný níže a program funguje, ale s tím problém že to přesto generuje dvě a více stejných čísel, prosím o radu už jsem vyzkoušel snad všechno co mě napadlo:

[Wikan]

Vygeneruješ číslo - zkontroluješ jestli už ho nemáš - pokud ano, vygeneruješ další - vložíš ho tam.
A tam je ten problém, co když už tam je i to druhé vygenerované číslo?
A porovnávat čísla tím, že je převedeš na string, je docela prasárna.

[JirkaVejrazka]

Pri takovemto zadani zadna nahodna cisla generovat nemusis. Zkus ti to rucne (treba na papire nebo v Excelu) pro pole delky pet nebo deset a pak se poradne podivej na vysledek.

[PeterKE]

Napln to bole cislami zaradom (=> nebudeš mať žiadne duplicity) a potom cez neho chod položku po položke a pri každej položke si nechaj vygenerovať náhodné číslo v rozsahu dlžky pola a obsah sucasnej pozície a obsah na vygenerovanej pozícii zamen.

Snad je to zrozumitelne a snad sa to da povazovať za náhodné.

A navyše môžeš to pole takto "premiešať" ľubovoľne veľa krát..

[Mike.M]

Co ta naplnit pole postupně 1,2,3,4-x a pak jen to jen promichat.

[Nargon]

Generování náhodných čísel tak aby se neopakovali lze jedině tak, že v cyklu stále dokola generuješ náhodné číslo dokud se netrefíš do toho čísla co tam není.
Tobě tam chybí ten cyklus. Ty vygeneruješ jedno náhodné číslo, zkontroluješ zda tam už není. Pokud tam je vygeneruješ druhé náhodné číslo a to tam zapíšeš (ale už nezkontroluješ zda i tohle to druhé číslo tam náhodou není)

Ovšem tohle zmíněné řešení je vhodné jen když je velice malá pravděpodobnost kolize dvou náhodně generovaných čísel (tj máš vygenerovat třeba 10 čísel z intervalu 0..100, ale čím více čísel z toho intervalu musíš vyplnit tím je toto řešení horší. Může se dostat až do "téměř nekonečné smyčky". Představ si že máš vygenerovat 1 milion takto náhodných čísel do 1 milionu. A máš už skoro všechny, jen ti chybí posledních 5 čísel. A než ten generátor náhodně vyplodí to jedno číslo co tam můžeš zadat, tak můžeš čekat třeba hodinu, nebo i pár dní.

Pro tyhle situace, kdy máš vygenerovat 10 čísel bez opakování z intervalu 0..9, je nejlepší řešení je nacpat do pole od začátku tj: 0,1,2,3,4,5,6,7,8,9 a následně toto pole náhodně zamíchat. Vygeneruješ dvojici indexů a prohodíš dva prvky na těch indexech. Napr vygeneruješ 3 a 5 a tyhle prvky prohodíš. Dostaneš: 0,1,2,5,4,3,6,7,8,9. A tohle opakuješ tolikrát jak hodně to chceš promíchat. Třeba 5x délka pole. Tj pro tenhle příklad vygeneruješ 50 dvojic náhodných indexů a ty prvky prohodíš.

[themrmaros]

Promícháváním ten program udělat nemohu. Musí tam být to ta metoda Random, aby mi to uznali. Napadlo mě napsat for cyklus naplnit to pole náhodnými čísly a v něm další for cyklus, který by to pole projízděl a v případě že už tam to číslo je tak bude generovat nové tak dlouho dokud nevygeneruje takové které tam není, ale nevím jak na to.

[Wikan]

Promíchávání je přece náhodné, takže tam Random mít budeš.
Co konkrétně nevíš?

[themrmaros]

Byl tady nápad naplnit to pole od 1-velikostpole a pak to promíchat. A já tam právě potřebuji ty čísla generovat náhodně a poté bych tam dal další for cyklus který by to projížděl, ale nevím jak ho mám napsat aby pokračoval furt do té doby než vygeneruje to číslo které v tom poli ještě není a poté se přesunul k dalšímu i-tému prvku v poli. Nevím jak na ten druhý for cyklus. Jinak už mě vážně nic nenapadá jak by se to dalo napsat.

[gandor]

Dalsie trocha lepsie riesenie je vytvorit si dane pole kam vkladas (zatial nic neplnis) vysledok. Toto pole je dobre inicializovat nejakou hodnotou, ktora sa tam nemoze vyskytnut (-1, NULL ak ide o pointre, pripadne dlzka pola+1)
Potom for-cyklom generovat vzdy nahodne cislo v uzavretom intervale <0, (velkost pola - iteracia generovaneho prvku)> - toto cislo ti hovori o pozicii noveho prvku.
Ale miesto toho, aby si dane cislo priamo umiestnil na pole, tak odpocitavas od nultej pozicie, daneho pola.
Pokial, uz v danom policku bol nejaky prvok umiestneny, tak od vygenerovaneho cisla odpocitas 1. V opacnom pripade sa posunies o dalsi prvok. Ked vygenerovane cislo dosiahne 0, tak do daneho pola umiestnis cislo iteracie (vonkajsiej iteracie - to znamena, na zaciatku bude pole obsahovat "niekde" cislo 0, potom 0,1 atd)....

Vyhoda tohto algoritmu je, ze ma zlozitost O(N^2) (takze ani 1 000 000 prvkov nebude riesit niekolko hodin) a vytvorena postupnost je tak nahodna, ako mas nahodny generator nahodnych cisiel.
Ten priklad s naplnenim pola a miesanim prvkov v nom je bud pomalsi, alebo nezanechava vskutku nahodne cisla (je vyssia pravdepodobnost, ze na napriklad 3. pozicii v poly ostane cislo 2 (indexacia od nuly), lebo mozno generator nevygeneroval zamenenie tohto prvku)...

Existuju ale aj lepsie riesenia...

-- 23. 5. 2013 20:26 --

K zamiesaniu pola - najskvor si BEZ NAHODNOSTI napln pole od 0 po dlzka pola-1. Ma vzniknut postupnost - ziadna nahodnost... Toto je prva oddelena cast.
Nasledne v druhej casti X krat vygenerujes 2 nahodne cisla. Tieto cisla ti urcia indexy pola - napriklad ak sa ti vygeneruje 3 a 7, vies ze musis zamenit obsah pola v prvku 3 s obsahom pola v prvku 7. Takze po prvej zamene by si mohol mat vysledok 0127456389...
No a to dane X by malo byt "dost velke". Minimalne o velkosti pola - ale to je nedostatocne minimum...
Ked sa zamyslis, da sa dany algoritmus potom aj vylepsit. Ale ak nechces, tak kludne pouzi aj len "dostatocne velke X". Napriklad 100-nasobok velkosti pola alebo este viac a pozry na vysledok. Predpokladam, ze od profaka by si nedostal nejak vyrazne menej bodov...

[PeterKE]

re gandor: "Nasledne v druhej casti X krat vygenerujes 2 nahodne cisla." - ja som vyššie navrhoval, aby to prvé číslo na výmenu nebolo náhodne ale aby sa prešlo postupne po všetkých pozíciach a až druhe by sa generovalo náhodne. Takto máš istotu že už pri jednom prechode každé jedno bolo ovplyvnené náhodou, aj ked to negarantuje že nebudú čísla ktoré neostanú na svojom mieste (napr číslo 6 na 6-tej pozícii)

[Nargon]

Pokud to mermomocí chceš takhle řešit a generovat to náhodné pole, tak ti to teda napíšu:

Kód: Vybrat vše

Random r = new Random();
for (int i = 0; i < pole.Length; i++)
{
    int tmp = r.Next(1, pole.Length + 1);
    while (pole.Contains(tmp)) tmp = r.Next(1, pole.Length + 1);
    pole[i] = tmp;
}

Ale tohle je ŠPATNÝ přístup, pro nějakých cca 100 000 prvků (a více) toho pole, to může počítat několik dní a stejně to ten výsledek nemusí dopočítat. Pokud ti tohle učitel uzná, tak by měl jít učit něco jiného než programování.

Opravdu jediný správný postup pro zadání typu: "chci výsledek s X náhodnýmí čísly z intervalu <Y,Y+X>, kde se čísla nebudou opakovat", je ten že ty čísla "vyrobíš" tak jak jdou po sobě. A pak je náhodně promícháš. Při tomto postupu máš jistotu že opravdu ten výsledek vygeneruješ. Ten kód co jsem ti napsal výše ti ten výsledek nemusí vypočítat ani do doby, kdy zanikne vesmír.

[pucmeloudek]

ja bych to teda videl takhle:
trida:

Kód: Vybrat vše

    class RandomWithoutRepeat
    {
        private int index;
        private int maxValue;
        private int [] gen;
        private Random r = new Random();

        public RandomWithoutRepeat(int maxValue) {
            this.maxValue = maxValue;
            gen = new int[maxValue];
        }

        public int Next() {
            int res;
            if (gen[index] == 0)
            {
                int cislo = r.Next(maxValue - index);
                if (gen[cislo + index] == 0)
                    res = cislo + index;
                else
                    res = gen[cislo + index] - 1;
                gen[cislo + index] = index + 1;
            }
            else
            {
                res = gen[index] - 1;
            }
            index++;
            return res;
        }
    }


a priklad pouzit

Kód: Vybrat vše

            RandomWithoutRepeat r = new RandomWithoutRepeat(10);
            for (int i = 0; i < 10; i++)
               Console.Out.WriteLine(r.Next());


vyhody: rovnomerna rychlost generovani od zacatku do konce (coz neplati pro metodu s testoovanim, jestli jsem uz generoval) a rychle dodani prvniho vysledku (coz neplati pro metodu s pocatecnim michanim), zapouzdreny algoritmus.

Nevyhodne je to pouze za predpokladu, kdyz potrebny rozsah je prilis velky (treba vic nez 10 milionu) - prilis roste pametova narocnost. pak viz vyse Nargon.

[PeterKE]

myslím že riešiť toto "objektovo" je overkill, len to nafukuje kod a robi ho neprehľadným.
Ja by som to napísal takto - začnem od bodu že máme pole o dlžke c, najprv ho prvotne obsadíme číslami:

Kód: Vybrat vše

for (x=0;x<c;x+=1) pole[x]=x+1;

a potom ich zamiešame (jedným "prechodom"):

Kód: Vybrat vše

for (x=0;x<c;x+=1) {
   y=rand()%c;
   tmp=pole[x];
   pole[x]=pole[y];
   pole[y]=tmp;
}

Nie je to C# ale ten zápis je taký triviálny že by nemal byť problém ho previesť aj do toho C#

[kohutisko]

a este to urob bez pomocnej premennej tmp a budes uplny frajer