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

C++, C#, Visual Basic, Delphi, Perl a ostatní

Moderátor: Moderátoři Živě.cz

Odeslat příspěvekod themrmaros 23. 5. 2013 10:36

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:

Obrázek Obrázek
themrmaros
Kolemjdoucí

Odeslat příspěvekod Wikan 23. 5. 2013 10:52

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.
Wikan
Moderátor
Uživatelský avatar

Odeslat příspěvekod JirkaVejrazka 23. 5. 2013 11:10

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.
JirkaVejrazka
Mírně pokročilý

Odeslat příspěvekod PeterKE 23. 5. 2013 11:45

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..
PeterKE
Junior

Odeslat příspěvekod Mike.M 23. 5. 2013 12:04

Co ta naplnit pole postupně 1,2,3,4-x a pak jen to jen promichat.
Mike.M
Mírně pokročilý
Uživatelský avatar

Odeslat příspěvekod Nargon 23. 5. 2013 12:10

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íš.
Desktop: Ryzen 7 1800X (3.95GHz, 1.35V), Asus Crosshair VI Hero, 16GB DDR4 Ram (3200MHz), 128GB SSD + 3TB HDD, Nvidia GTX 1080
Notebook: Asus UL50VT 15.6" (SU7300@1.7GHz, 4GB ram, 500GB HDD, Intel GMA 4500MHD + nVidia G210M, dlouha vydrz cca 7+ hod)
Nargon
Moderátor

Odeslat příspěvekod themrmaros 23. 5. 2013 19:06

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.
themrmaros
Kolemjdoucí

Odeslat příspěvekod Wikan 23. 5. 2013 19:10

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

Odeslat příspěvekod themrmaros 23. 5. 2013 19:17

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.
themrmaros
Kolemjdoucí

Odeslat příspěvekod gandor 23. 5. 2013 19:20

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...
gandor
Mírně pokročilý

Odeslat příspěvekod PeterKE 23. 5. 2013 20:26

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)
PeterKE
Junior

Odeslat příspěvekod Nargon 23. 5. 2013 20:30

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.
Desktop: Ryzen 7 1800X (3.95GHz, 1.35V), Asus Crosshair VI Hero, 16GB DDR4 Ram (3200MHz), 128GB SSD + 3TB HDD, Nvidia GTX 1080
Notebook: Asus UL50VT 15.6" (SU7300@1.7GHz, 4GB ram, 500GB HDD, Intel GMA 4500MHD + nVidia G210M, dlouha vydrz cca 7+ hod)
Nargon
Moderátor

Odeslat příspěvekod pucmeloudek 23. 5. 2013 21:17

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.
pucmeloudek
Junior

Odeslat příspěvekod PeterKE 23. 5. 2013 22:21

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#
PeterKE
Junior

Odeslat příspěvekod kohutisko 23. 5. 2013 23:31

a este to urob bez pomocnej premennej tmp a budes uplny frajer ;)
kohutisko
Junior
Uživatelský avatar

Další stránka

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 0 návštevníků