Random broj bez ponavljanja

[clzola]

Pokusavam da mi program generise 14 brojeva od 1 do 14..
E sad dva broja jedan do drugog ne smiju biti ista.

ovo je okej niz:
5 6 8 12 4 8 7 1 3 13 5 14 3 5 (jedan broj moze da se ponovi vise puta)

ovaj niz ne valja:
4 8 7 2 6 1 [12 12] 7 5 4 6 14 13 (te dvije 12-ice ne smiju da budu jedna do druge)

e sad ja generisem radnom brojeve

for(i=0; i<14; i++)
{
    srand(time(NULL));
    x=rand()%14+1;
    printf("%d ", x); 
    }

Ne znam kako da generisem brojeve a da susedni brojevi ne budu isti... ? probao sam da stavim sleep(1) ali opet se desava, ali ne tako cesto.
Od 1000 generisanih brojeva, u svih 1000 dva susedna broja ne smiju biti ista.
Nadam se da shvatate sta mislim.


EDIT: Uspio sam da resim problem. Moderator moze slobodno da izbrisetemu, a moze i da je ostavi, ako slucajno neko drugi zapne pa da moze da pogleda.

srand(time(NULL));
for(i=0; i<14; i++)
    {
             sleep(1);
             x=rand()%14+1;
             broj[i]=x;
             if(broj[i-1] == x) ako je prethodni broj (broj[i-1]) jednak novom generisanom broju x tada:
             {
                 x = x - 2;
                 if(x == 0) x = x+3; // Nekad ce se dobiti 0 ako se nadju dvije dvojke jedna do druge, brojevi treba da budu u intervalu [1, 14]
                 if(x == -1) x = x+6; // Nekad ce se dobiti -1 ako se nadju dvije jedinice jedna do druge, brojevi treba da budu u intervalu [1, 14]
                 broj[i]=x;
                 }
             printf("%d  ", broj[i]);
             }

[boshkodj]

clzola kaže:

Pokusavam da mi program generise 14 brojeva od 1 do 14..
E sad dva broja jedan do drugog ne smiju biti ista.

ovo je okej niz:
5 6 8 12 4 8 7 1 3 13 5 14 3 5 (jedan broj moze da se ponovi vise puta)

ovaj niz ne valja:
4 8 7 2 6 1 [12 12] 7 5 4 6 14 13 (te dvije 12-ice ne smiju da budu jedna do druge)

e sad ja generisem radnom brojeve

for(i=0; i<14; i++)
{
    srand(time(NULL));
    x=rand()%14+1;
    printf("%d ", x); 
    }

Ne znam kako da generisem brojeve a da susedni brojevi ne budu isti... ? probao sam da stavim sleep(1) ali opet se desava, ali ne tako cesto.
Od 1000 generisanih brojeva, u svih 1000 dva susedna broja ne smiju biti ista.
Nadam se da shvatate sta mislim.

cini mi se da samo seed trebas da promenis

[Stevvan]

Hm, metod ti i nije baš najbolji s obzirom da u slučaju dobijanja istog broja kao i prethodnog on može dobiti vrednost 3 ili 5, što i nije pravo rešenje. Evo kako bih ja to odradio, javi ako ti zatreba optimizovanije rešenje pošto mi se čini da ima prostora za optimizaciju (rand() funkcija je procesorski dosta skupa )

int nums[14];
srand(time(0));
for (int i = 0; i < 14; i++) nums[i] = rand()%14 + 1;

for (int i = 1; i < 13; i++)
{
    while (nums[i] == nums[i-1] || nums[i] == nums[i+1])
        nums[i] = rand()%14 + 1;
}

[EclipsE]

    int last = 0, x = 0, i;
    for(i = 0; i < 14; i++)
    {
        x = rand() % 14 + 1;

        while (last == x)
            x = rand() % 14 + 1;

        printf("%d, ", x);
        last = x;
    }

[MG-RAY]

Ne znam zašto previše komplikujete stvari...

// Rand.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdlib.h"
#include "time.h"

int _tmain(int argc, _TCHAR* argv[])
{
    unsigned int seed = time(NULL);
    int number;

    for(int i = 0; i < 14; i++)
    {
        srand(seed++);
        number = rand() % 14 + 1;

        printf("%d ", number);

    }
}

@Stevvan
rand() zapravo i nije skupa operacija, evo standardne implementacije:

unsigned long int next = 1;
int rand(void)
{
next = next * 1103515245 + 12345;
return (unsigned int)(next/65536) % 32768;
}

void srand(unsigned int seed)
{
next = seed;
}

[Stevvan]

Hm jesi siguran da su funkcije rand i srand toliko jednostavne, meni se čini da sam negde pročitao da je njihovo izvršavanje dosta skuplje?

[EclipsE]

MG-RAY kaže:

Ne znam zašto previše komplikujete stvari...

Zao mi je ali tvoj primer failuje ^^ Ima slucajeva gde su susedni brojevi isti.

[irreal]

ne mogu da verujem kolko su se neki nalupali.

u svakom slucaju, bar dva dobra resenja su postavljena pa necu tupiti o tome, ali hocu naglasiti jedno.

cizola, to sa "sleep" funkcijom je bio totalni promasaj.
sigurno nije problem da se suvise brzo zove dva puta rand funkcija, pa eto zato daje dva ista broja. "problem" je sto je rand nasumican (ili bi bar trebao da bude, idealno), tako da apsolutno je validno da se nigde ne pokazu dva ista broja, ali je isto tako moguce (ma da malo verovatno) da ce svi brojevi da budu isti. svih 1000.

E sad, verovatno si primetio da ti sleep nije resio problem, ali vidim da si taj sleep ostavio i nakon sto si "popravio" (ali pogresno) program.


BTW,
evo jos jedne implementacije random funkcije

[clzola]

To sleep ostalo xD, nisam puno ni obracao paznju. Jednostavno sam uzeo da razmisljam kako pa mi je palo na pamet da ako su dva ista jedan do drugog da ovom drugom promjenim vrijednost tako sto cu da mu oduzmem/dodam neki broj, sta vec..

Uglavnom hvala i na ova ostala resenja. I ako sam ja zakomplikovao, tek mjesec dana ucim C jezik sam.. tako da mene sad jos nije bitno kako ce kod da izgleda, ali s vremnom cu uciti i sticati naviku da to mnogo ljepse izgleda i da je efikasnije. U svakom slucaju Hvala vama na sugestije i kritike!

[MG-RAY]

Stevvan kaže:

Hm jesi siguran da su funkcije rand i srand toliko jednostavne, meni se čini da sam negde pročitao da je njihovo izvršavanje dosta skuplje?

Aha, ili varijacije na temu. Evo primera za MSC++ kompajler:

// RandTest.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "time.h"
#include "stdlib.h"

unsigned long int next = 1;

int myrand(void)
{
next = next * 0x343fd + 0x269EC3;
return (next >> 0x10) & 0x7FFF;

}

void mysrand(unsigned int seed)
{
next = seed;
}

int _tmain(int argc, _TCHAR* argv[])
{
unsigned int seed = time(0);

srand(seed);
mysrand(seed);

for(int i = 0; i < 30; i++)
{
printf("%d - %d\n", rand() % 100, myrand() % 100);
}
}

EclipsE kaže:

Zao mi je ali tvoj primer failuje ^^ Ima slucajeva gde su susedni brojevi isti.

Čudno, ja imam 1 000 000 brojeva koji ne failuju (Vidi attachment)...

Jedini problem sa mojim rešenjem jeste što se sekvence ponavljaju, logično, obzirom da su implementirane funkcije PRNG, sto znaci da nemaju ni R od Random u sebi...

No, da ne davim više, verujem da ima sasvim dovoljno predloga za rešenje ovde...

[EclipsE]

MG-RAY kaže:

Čudno, ja imam 1 000 000 brojeva koji ne failuju (Vidi attachment)...

Jedini problem sa mojim rešenjem jeste što se sekvence ponavljaju, logično, obzirom da su implementirane funkcije PRNG, sto znaci da nemaju ni R od Random u sebi...

No, da ne davim više, verujem da ima sasvim dovoljno predloga za rešenje ovde...

Tvoji brojevi prate sledeci niz (p = prethodni broj):

neki_broj, p + 3, p + 3, p + 4, p + 3, p + 3, p + 4 itd.. Tako idu do 100 i onda krecu od 1

[MG-RAY]

EclipsE kaže:

Tvoji brojevi prate sledeci niz (p = prethodni broj):

neki_broj, p + 3, p + 3, p + 4, p + 3, p + 3, p + 4 itd.. Tako idu do 100 i onda krecu od 1

Ups... Nisam ni primetio...

[Mr.Deeds]

Moram ovo da ozivim... treba mi ista ta random funkcija, samo sto imam niz znakova koji ne smeju da se ispisuju jedni za drugim. Ustvari rec je o logickim operacijama i treba da napravim program koji ce da izbacuje nasumicnu formulu koja naravno ne moze da ima 2 znaka jedan pored drugog, jer onda ne bi imala svoj smisao. Sta mislite kako to moze da se napravi?

[Geomaster]

Prvo što mi pada na pamet je da ako slovo biraš po sistemu random broj X od 1 do N (gde je N broj slova) pa onda X-to slovo, da od sledećeg odabereš broj od 1 do N - 1 i onda svakom od tih brojeva dodeliš po slovo, bez onog zadnjeg. Na primer: Imaš slova a, b, c, d i e, treba ti da generišeš niz u kome se ne pojavljuje slovo dvaput zaredom. Za prvo slovo ćeš da odabereš broj od 1 do 5, neka bude 2, pa uzimaš slovo b. Za sledeće ćeš uzeti broj od 1 do 4 i slovo birati na sledeći način: 1 -> a, 2 -> c, 3 -> d, 4 -> e. Recimo da si odabrao 4 odnosno e. Za sledeće ćeš ponovo uzeti broj od 1 do 4, s tim što bi slovo birao kao 1 -> a, 2 -> b, 3 -> c, 4 -> e. Mislim da je to ono što ti treba, ako si me razumeo (ja sam malo konfuzno objasnio ali valjda kontaš).

int n = 5, restricted = 0, goal_size = 200;
char letters_used[] = { 'a', 'b', 'c', 'd', 'e' };
std::vector<char> letters;

restricted = rand() % n;
letters.push_back(letters_used[restricted]);
while (--goal_size)
{
   int random = rand() % (n - 1), id = random;
   if (id >= restricted)
       ++id;
   restricted = id;
   letters.push_back(letters_used[id]);
   assert(letters.back() != letters[letters.size()-2]);
}

[pivonroll]

And now a surprise, slucajn i broj koji ti funkcija rand (ili random, ili srand ili bilo koja funkcija koja ima takvu namenu) generise je ustvari pseudo-slucajan broj koji generise odredjeni algoritam. Nije on bas 100% slucajan

[NISAM NESTO SMART]

Not that big of a surprise, inace evo jedan dobar clanak o pravilnom koriscenu rand funckije u C++ Link

[Geomaster]

pivonroll kaže:

And now a surprise, slucajn i broj koji ti funkcija rand (ili random, ili srand ili bilo koja funkcija koja ima takvu namenu) generise je ustvari pseudo-slucajan broj koji generise odredjeni algoritam. Nije on bas 100% slucajan

Ako uspeš da dobiješ stvarno random broj na prosečnom sistemu, platim ti pivo

[zokocx]

Moguce je ,ali radom algoritam koji sluzi za generisanje random sekvence mora da bude takav radom sekvenca koju generise se ne ponavlja recimo posle 50k brojeva ako je tolko dovoljno za konkretan zadatak.
Tj. svaki generator je tolko dobar kolko pasuje nekoj primeni.

I nepostoji apsolutni random generator, svaki ima neko ponvaljanje bar posle milijardu brojeva a mozda i vise.

[Geomaster]

Svi 'random' brojevi su u suštini pseudo-random. Ukoliko nekome treba nešto stvarno random, mora da se osloni na spoljašnje uticaje, kao na primer random.org koji koriste atmosferski šum.

[irreal]

Geomaster kaže:

Svi 'random' brojevi su u suštini pseudo-random. Ukoliko nekome treba nešto stvarno random, mora da se osloni na spoljašnje uticaje, kao na primer random.org koji koriste atmosferski šum.

a ako cemo da sitnicimo, nista u ovom univerzumu nije random.

jedino sto neke stvari, kao pomenuti atmosferski sum, mnooooooogo vise lice na pravi random nego "obicna" rand funkcija na racunaru