[C] numeri casuali senza ripetizione

Linguaggi di programmazione: php, perl, python, C, bash e tutti gli altri.
Avatar utente
Vincenzo1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 450
Iscrizione: lunedì 14 gennaio 2013, 14:21
Desktop: Unity
Distribuzione: Ubuntu 18.04.3 LTS x86_64
Località: Villabate(PA)
Contatti:

Re: [C] numeri casuali senza ripetizione

Messaggio da Vincenzo1968 » mercoledì 4 dicembre 2013, 20:37

nth_perm.c:

Codice: Seleziona tutto

void ithPermutation(const int n, int i, int* perm, int *fact)
{
   int j, k = 0;

   /* compute factorial numbers */
   /*
   fact[k] = 1;
   while (++k < n)
      fact[k] = fact[k - 1] * k;
   */

   /* compute factorial code */
   for (k = 0; k < n; ++k)
   {
      perm[k] = i / fact[n - 1 - k];
      i = i % fact[n - 1 - k];
   }

   /*
   readjust values to obtain the permutation
   start from the end and check if preceding values are lower
   */
   for (k = n - 1; k > 0; --k)
      for (j = k - 1; j >= 0; --j)
         if (perm[j] <= perm[k])
            perm[k]++;
}

int main()
{
	int i;
	
	int n = 10;
	int k = 0;
	
	int *fact = (int *)calloc(n, sizeof(int));
	int *perm = (int *)calloc(n, sizeof(int));	
	
	/* compute factorial numbers */
	fact[k] = 1;
	while (++k < n)
		fact[k] = fact[k - 1] * k;	
		
	for ( i = 0; i < 100000; i++ )
	{
		ithPermutation(n, i, perm, fact);
		/* print permutation */
		for (k = 0; k < n; ++k)
			printf("%d ", perm[k]);
		printf("\n");		
	}
		
	free(fact);
	free(perm);
	
	return 0;
}
nth_perm2.c:

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>

void PermLexUnrank(int n, int r, int *pi, int *f)
/*
**  Algorithm 2.16
**
**  Returns the permutation pi that has rank r.
*/
{
 int i,j,d;
 
 pi[n] = 1;
 for(j=1;j<n;j=j+1)
 {
   d = (r % f[j+1])/f[j];
   r = r - d * f[j];
   pi[n-j] = d+1;
   for(i=n-j+1;i<=n;i=i+1)
   {
     if(pi[i] > d)
        pi[i] = pi[i] + 1;
   }
  }    
} 

int main()
{
	int i;
	
	int n = 10;
	int k = 0;	
	
	int *fact = (int *)calloc(n+1, sizeof(int));
	int *perm = (int *)calloc(n+1, sizeof(int));	
	
	/* compute factorial numbers */
	fact[k] = 1;
	while (++k < n)
		fact[k] = fact[k - 1] * k;		

	/* print first permutation */
	for (k = 0; k < n; k++)
		printf("%d ", k);
	printf("\n"); 		
		
	for ( i = 1; i < 100000; i++ )
	{
		PermLexUnrank(n - 1, i, perm, fact);
		/* print permutation */
		for (k = 0; k < n; k++)
			printf("%d ", perm[k]);
		printf("\n"); 		
	}
		
	free(fact);
	free(perm);
	
	return 0;
}

Codice: Seleziona tutto

[vincenzo]$ time ./nth_perm > out1.txt

real	0m0.093s
user	0m0.084s
sys	0m0.008s
[vincenzo]$ time ./nth_perm2 > out2.txt

real	0m0.095s
user	0m0.089s
sys	0m0.004s
Ultima modifica di Vincenzo1968 il mercoledì 4 dicembre 2013, 22:18, modificato 1 volta in totale.
È ormai difficile incontrare un cretino che non sia intelligente e un intelligente che non sia un cretino. [...] Oh i bei cretini di una volta! Genuini, integrali. Come il pane di casa. Come l'olio e il vino dei contadini. (da "Nero su nero" di Leonardo Sciascia)

Avatar utente
vaeVictis
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 4135
Iscrizione: venerdì 27 luglio 2012, 17:58
Desktop: Gnome
Distribuzione: Ubuntu/Lubuntu 18.04.1 64bit

Re: [C] numeri casuali senza ripetizione

Messaggio da vaeVictis » mercoledì 4 dicembre 2013, 21:17

OT
FINALMENTE una discussione interessante!
È bellissimo quando da una semplice domanda si arriva a scandagliare il problema in un modo così approfondito!
Questo forum è un posto bellissimo!
:D
Pirates arrrrrrrrrrr awesome!!!
«I fear not the man who has practiced 10000 kicks once, but I fear the man who has practiced one kick 10000 times.»

Avatar utente
M_A_W_ 1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 856
Iscrizione: venerdì 15 febbraio 2013, 3:57
Desktop: KDE
Distribuzione: SuSE
Sesso: Maschile
Località: Un luogo geometrico
Contatti:

Re: [C] numeri casuali senza ripetizione

Messaggio da M_A_W_ 1968 » mercoledì 4 dicembre 2013, 21:48

Due concetti che devi senz'altro approfondire. Il primo si chiama "domanda retorica". Dove tu l'abbia pescato era ed è terribilmente ovvio ed esplicito. Lo stupefacente è che a te sia venuto in mente di proporlo qui, a poche righe di distanza da un riferimento al COS di Ruskey. E il grave è che a qualcun altro sia venuto in mente di scriverlo in quel modo, nel terzo millennio. :cry:

Il secondo si chiama "complessità ciclomatica" o anche "function points". C'è tutto un universo inerente la qualità e la struttura del codice, che va oltre la complessità computazionale e il banale profiling.

Il terzo è in omaggio: ho già scritto due volte che esistono algoritmi di unranking in tempo lineare, assai migliori di quello del datatissimo Kreher-Stinson che costituisce, repetita juvant, un esempio volutamente negativo. Occorre ripeterlo nuovamente?

Il punto è che non ha alcun senso proporre una discutibile implementazione di un algoritmo così obsoleto, appena un paio di post dopo un riferimento esplicito al ranking ed al COS di Ruskey: un sito che, assieme alla bibliografia proposta, vale quanto un paio di corsi universitari in materia. E la cui lettura, anche superficiale, avrebbe permesso di evitare la riproposizione di codesto codice, valutandolo per quel che è. Fine della questione, procediamo oltre che il tempo è maledettamente tiranno ed io, sull'argomento combinatorio, posso riempire dei tomi - invece di sprecare tempo con codici fossili e surclassati, che purtroppo permangono in circolazione solo per cause murphologiche.

vaeVictis [url=http://forum.ubuntu-it.org/viewtopic.php?p=4497278#p4497278][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:OT
FINALMENTE una discussione interessante!
È bellissimo quando da una semplice domanda si arriva a scandagliare il problema in un modo così approfondito!
Questo forum è un posto bellissimo!
...e questa è solo la punta dell'iceberg... il mondo sommerso degli algoritmi combinatori è in continua evoluzione da almeno mezzo secolo. W la matematica discreta! (Pubblicità Progresso) :D
Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo...

"...in una società che sembra sempre più spaventata dai problemi troppo articolati e che rigetta come un corpo estraneo ogni elemento di complessità, sapremo ancora come utilizzare il parere degli esperti?"

Avatar utente
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2617
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: [C] numeri casuali senza ripetizione

Messaggio da gila75 » mercoledì 4 dicembre 2013, 21:52

Sono lontano anni luce da quello che avete postato ultimamente, quindi farò domande più a basso livello :sisi:
Ho studiato il programma, e mi sembra di averlo capito.
Su una cosa però ho una perplessità.
Generiamo un array con un determinato offset:
array[3]
quindi 0,1,2
offset 3 quindi

array[0]=3;
array[1]=4;
array[2]=5;

in definitiva, vengono estratti i numeri 3,4,5 senza essere ripescati. Una volta estratti vengono scartati, in un modo particolare dall'algoritmo.
Noi abbiamo inizializzato l'array in modo automatico, con un ciclo for, e anche l'offset è automatico, di conseguenza non ci sarà mai un numero doppione.
Supponiamo però che l'offest sia inizializzato a mano:

array[0]=3;
array[1]=3;
array[2]=5;

Da quello che capisco, l'algoritmo, non ha modo di sapere che di 3 ce ne sono due, per lui sono due numeri e basta, e operando in un modo tutto suo
e senza controlli di sorte ( costrutti if o altra roba simile), non si accorge di nulla, no?
Magari al lato pratico, non si presenta nemmeno questa eventualità, però dovrebbero stare così le cose, giusto?

Avatar utente
M_A_W_ 1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 856
Iscrizione: venerdì 15 febbraio 2013, 3:57
Desktop: KDE
Distribuzione: SuSE
Sesso: Maschile
Località: Un luogo geometrico
Contatti:

Re: [C] numeri casuali senza ripetizione

Messaggio da M_A_W_ 1968 » mercoledì 4 dicembre 2013, 22:02

gila75 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4497292#p4497292][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto: Supponiamo però che l'offest sia inizializzato a mano:

array[0]=3;
array[1]=3;
array[2]=5;

Da quello che capisco, l'algoritmo, non ha modo di sapere che di 3 ce ne sono due, per lui sono due numeri e basta
Due cose:

1) Compila e studia l'ultimo sorgente che ho proposto, in ordine di tempo. L'output è di una chiarezza esemplare.

2) Come ripetuto più volte, l'array dei simboli è del tutto arbitrario. Ci mettiamo dentro quel che vogliamo, e l'esempio usa un offset esplicito per rendere evidente questo concetto. Possiamo avere ripetizioni, intervalli disgiunti, e molto altro (stringhe, puntatori a strutture complesse, interi alberi e foreste!), non solo il banale insieme dei primi N interi positivi in sequenza. Questo algoritmo è una modellazione potente ed efficace di una reale estrazione da un sacchetto o urna di biglie numerate o altri oggetti fisici facilmente distinguibili.

Attenzione alla parola chiave. L'algoritmo è uno dei pochi che operino genuinamente su un insieme, seppure rappresentato tramite un array, e ottimizza l'operazione di unione dei due sottoinsiemi (involontariamente partizionati dalla "estrazione", a causa della rappresentazione usata) con una semplice ma geniale euristica: sovrascrive la locazione del valore appena estratto con il contenuto dell'ultima locazione, così modificando l'ordine relativo (che in un insieme non ha alcun senso) ma "accorciando" l'array senza operazioni terrificanti e demenziali come un memory shift (i.e. memcopy(), memmove()...) o peggio una realloc() (ho visto cose che voi umani...). Nell'insieme, per definizione, non c'è un ordinamento e non esistono elementi ripetuti: ma questo ultimo aspetto è a totale carico del programmatore, in questo caso.

Si possono comunque trattare anche multiinsiemi, nei quali uno o più elementi possono essere ripetuti (l'insieme è opportunamente descritto da coppie valore-quantità), con idonee strutture dati. Ma al momento non allontaniamoci troppo da questo algoritmo.
Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo...

"...in una società che sembra sempre più spaventata dai problemi troppo articolati e che rigetta come un corpo estraneo ogni elemento di complessità, sapremo ancora come utilizzare il parere degli esperti?"

Avatar utente
Vincenzo1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 450
Iscrizione: lunedì 14 gennaio 2013, 14:21
Desktop: Unity
Distribuzione: Ubuntu 18.04.3 LTS x86_64
Località: Villabate(PA)
Contatti:

Re: [C] numeri casuali senza ripetizione

Messaggio da Vincenzo1968 » mercoledì 4 dicembre 2013, 22:30

M_A_W_ 1968 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4497291#p4497291][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:
Il terzo è in omaggio: ho già scritto due volte che esistono algoritmi di unranking in tempo lineare, assai migliori di quello del datatissimo Kreher-Stinson che costituisce, repetita juvant, un esempio volutamente negativo. Occorre ripeterlo nuovamente?
No veramente avevi lasciato intendere che il Kreher-Stinson, nonostante sia uno dei peggiori, fosse più veloce di quello che ho trovato su stackoverflow:
Starai scherzando, spero... :muro:
Mi occupo professionalmente di combinatorica e matematica discreta computazionale da più di un quarto di secolo, e per diletto ormai da oltre sei lustri. Francamente dubito di aver mai visto qualcosa di più mostruosamente inefficiente e farraginoso fin dai tempi del BASIC sui vari PET e su TRS80
...
infatti è uno dei peggiori esempi, ma nonostante questo siamo già anni luce lontano da quella "soluzione" che calcola addirittura il fattoriale al volo! Qui almeno l'array f[] contiene una tabella dei fattoriali precalcolata, ed è questa la più banale delle ottimizzazioni necessarie, senza contare che esistono algoritmi assai migliori in generale, come sopra indicato.
Almeno io avevo capito così; ed è per questo che ho voluto comparare i tempi.

Puoi postare uno degli algoritmi assai migliori? Anche in pseudocodice.
È ormai difficile incontrare un cretino che non sia intelligente e un intelligente che non sia un cretino. [...] Oh i bei cretini di una volta! Genuini, integrali. Come il pane di casa. Come l'olio e il vino dei contadini. (da "Nero su nero" di Leonardo Sciascia)

Avatar utente
M_A_W_ 1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 856
Iscrizione: venerdì 15 febbraio 2013, 3:57
Desktop: KDE
Distribuzione: SuSE
Sesso: Maschile
Località: Un luogo geometrico
Contatti:

Re: [C] numeri casuali senza ripetizione

Messaggio da M_A_W_ 1968 » mercoledì 4 dicembre 2013, 22:43

Vincenzo1968 ha scritto: Puoi postare uno degli algoritmi assai migliori? Anche in pseudocodice.
L'ho già fatto sopra, Vincenzo: è contenuto nel paper in versione PDF su Citeseer.
M_A_W_ 1968 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4497235#p4497235][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto: esistono asseverati algoritmi di ranking e unranking in tempo lineare: si veda appunto il già citato COS di Ruskey, vero e proprio tempio degli algoritmi in materia. Uno dei più validi lavori in materia è questo.
Vincenzo1968 ha scritto: No veramente avevi lasciato intendere che il Kreher-Stinson, nonostante sia uno dei peggiori, fosse più veloce di quello che ho trovato su stackoverflow:
[...]
Almeno io avevo capito così; ed è per questo che ho voluto comparare i tempi.
Mi scuso in tal caso per la eventuale mancanza di chiarezza o per l'eccesso di frettolosità da parte mia.
RIbadisco che l'algoritmo del Kreher-Stinson, in quella implementazione che accompagna il testo, è certamente uno dei peggiori e la comparazione verteva sulla complessità strutturale del codice, che - pur essendo il sorgente K-S di qualità ampiamente insoddisfacente - risulta migliore di quella dell'esempio proposto, secondo le metriche usuali (i.e. function points e altre metriche di complessità).

Devo anche sottolineare che ho appena rilevato come nei sorgenti K-S online - a differenza di quelli che ho sui miei HD, presumibilmente provenienti dal floppy che accompagnava il testo - la tabella dei fattoriali risulta parimenti generata a runtime, il che sostanzialmente ne abbassa le prestazioni fino a collimare con quelle dell'altro esempio. Nulla quaestio.

Spero sia più chiaro adesso: al di là dei relativi meriti, ambedue quei codici sono fossili da dimenticare, sui quali abbiamo speso fin troppo tempo negli anni passati, in mancanza di meglio.
Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo...

"...in una società che sembra sempre più spaventata dai problemi troppo articolati e che rigetta come un corpo estraneo ogni elemento di complessità, sapremo ancora come utilizzare il parere degli esperti?"

Avatar utente
Vincenzo1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 450
Iscrizione: lunedì 14 gennaio 2013, 14:21
Desktop: Unity
Distribuzione: Ubuntu 18.04.3 LTS x86_64
Località: Villabate(PA)
Contatti:

Re: [C] numeri casuali senza ripetizione

Messaggio da Vincenzo1968 » mercoledì 4 dicembre 2013, 23:17

M_A_W_ 1968 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4497319#p4497319][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:
Vincenzo1968 ha scritto: Puoi postare uno degli algoritmi assai migliori? Anche in pseudocodice.
L'ho già fatto sopra, Vincenzo: è contenuto nel paper in versione PDF su Citeseer.
Perfetto. Grazie mille!
M_A_W_ 1968 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4497235#p4497235][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto: esistono asseverati algoritmi di ranking e unranking in tempo lineare: si veda appunto il già citato COS di Ruskey, vero e proprio tempio degli algoritmi in materia. Uno dei più validi lavori in materia è questo.
Vincenzo1968 ha scritto: No veramente avevi lasciato intendere che il Kreher-Stinson, nonostante sia uno dei peggiori, fosse più veloce di quello che ho trovato su stackoverflow:
[...]
Almeno io avevo capito così; ed è per questo che ho voluto comparare i tempi.
Mi scuso in tal caso per la eventuale mancanza di chiarezza o per l'eccesso di frettolosità da parte mia.
RIbadisco che l'algoritmo del Kreher-Stinson, in quella implementazione che accompagna il testo, è certamente uno dei peggiori e la comparazione verteva sulla complessità strutturale del codice, che - pur essendo il sorgente K-S di qualità ampiamente insoddisfacente - risulta migliore di quella dell'esempio proposto, secondo le metriche usuali (i.e. function points e altre metriche di complessità).

Devo anche sottolineare che ho appena rilevato come nei sorgenti K-S online - a differenza di quelli che ho sui miei HD, presumibilmente provenienti dal floppy che accompagnava il testo - la tabella dei fattoriali risulta parimenti generata a runtime, il che sostanzialmente ne abbassa le prestazioni fino a collimare con quelle dell'altro esempio. Nulla quaestio.
Negli ultimi due sorgenti che ho postato per calcolare i tempi ho spostato il calcolo del fattoriale al di fuori delle funzioni.
Spero sia più chiaro adesso: al di là dei relativi meriti, ambedue quei codici sono fossili da dimenticare, sui quali abbiamo speso fin troppo tempo negli anni passati, in mancanza di meglio.
Ok, vedo se riesco ad implementare l'algoritmo di Myrvold e Ruskey.

;)
È ormai difficile incontrare un cretino che non sia intelligente e un intelligente che non sia un cretino. [...] Oh i bei cretini di una volta! Genuini, integrali. Come il pane di casa. Come l'olio e il vino dei contadini. (da "Nero su nero" di Leonardo Sciascia)

Avatar utente
M_A_W_ 1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 856
Iscrizione: venerdì 15 febbraio 2013, 3:57
Desktop: KDE
Distribuzione: SuSE
Sesso: Maschile
Località: Un luogo geometrico
Contatti:

Re: [C] numeri casuali senza ripetizione

Messaggio da M_A_W_ 1968 » giovedì 5 dicembre 2013, 1:12

Vincenzo1968 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4497338#p4497338][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto: Negli ultimi due sorgenti che ho postato per calcolare i tempi ho spostato il calcolo del fattoriale al di fuori delle funzioni.
La soluzione standard, all'epoca, prevedeva l'uso di una tabella dei fattoriali pregenerata.

Codice: Seleziona tutto

unsigned long f[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, ...};
In tale senso era stato modificato anche il codice di Kreher & Stinson, almeno nella versione in mio possesso.

Esistono comunque, a margine, sia algoritmi veloci su interi a lunghezza arbitraria per il calcolo esatto del fattoriale, sia approssimazioni (basate sostanzialmente su quelle di Stirling e Stieltjes) usate comunemente nel mondo del calcolo numerico. Questo sito è una vera cornucopia in tal senso (le formule di approssimazione che legano il fattoriale al CBC, coefficiente binomiale centrale, ed ai parenti stretti numeri di Catalan sono pura pornografia matematica :lol: ).

Ma in generale, quando si parla in sede didattica di generare oggetti combinatori elementari come le permutazioni senza restrizioni, i numeri coinvolti sono sufficientemente piccoli da potersi permettere l'uso di una banale tabella di lookup (LUT) dei fattoriali, che abbrevia drasticamente i tempi di calcolo. D'altro canto, questo know how che negli anni Ottanta e Novanta si è andato accumulando e trasmettendo in maniera quasi artigianale è ormai da anni incapsulato in potenti librerie di calcolo numerico, ma prima o poi si devono fare i conti con qualche situazione nella quale occorre saper implementare questi algoritmi (anche nelle occasioni più impensate, ad esempio nello scheduler di un kernel realtime o su un sistema embedded) in modo efficiente o comunque massimizzando/minimizzando qualche altro parametro.

Ti divertirai molto con l'algoritmo di unranking di Ruskey, che peraltro è tail recursive e, nella prima versione, non fa uso del fattoriale (risultato che lo rende notevolissimo!). L'ordine di generazione (enumerazione) delle permutazioni, nel caso del primo algoritmo che è poi quello di nostro maggior interesse, non è quello usuale lessicografico, ma questo non ha la benché minima importanza in una applicazione di "random pick", nella quel cioé si usa l'unranking per "pescare" in modo pseudocasuale una delle n! permutazioni possibili!
Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo...

"...in una società che sembra sempre più spaventata dai problemi troppo articolati e che rigetta come un corpo estraneo ogni elemento di complessità, sapremo ancora come utilizzare il parere degli esperti?"

Avatar utente
ienaplinsky
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 954
Iscrizione: giovedì 21 gennaio 2010, 9:56
Località: Napoli

Re: [C] numeri casuali senza ripetizione

Messaggio da ienaplinsky » giovedì 5 dicembre 2013, 2:19

scusate ho detto una scemenza non ci fate caso :D

Avatar utente
M_A_W_ 1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 856
Iscrizione: venerdì 15 febbraio 2013, 3:57
Desktop: KDE
Distribuzione: SuSE
Sesso: Maschile
Località: Un luogo geometrico
Contatti:

Re: [C] numeri casuali senza ripetizione

Messaggio da M_A_W_ 1968 » giovedì 5 dicembre 2013, 4:30

Provate a dare un'occhiata a questo codice, che implementa l'algoritmo di Myrvold-Ruskey.

Edit: tutto il codice è stato accentrato in questo post.
Ultima modifica di M_A_W_ 1968 il sabato 7 dicembre 2013, 19:16, modificato 1 volta in totale.
Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo...

"...in una società che sembra sempre più spaventata dai problemi troppo articolati e che rigetta come un corpo estraneo ogni elemento di complessità, sapremo ancora come utilizzare il parere degli esperti?"

Avatar utente
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2617
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: [C] numeri casuali senza ripetizione

Messaggio da gila75 » giovedì 5 dicembre 2013, 7:06

Altra considerazione M_A_W.
Noi dichiariamo un array di N elementi es: 5, quindi avremo 0,1,2,3,4
ASide, come viene chiamato vale N-1, quindi 5-1=4.
Quindi il numero random generato sarà (al primo passaggio) compreso tra 0 e3
Essendo :
Pos = rand() % ASize; ASize qui vale 3 e quindi il modulo può essere al massimo 2.

In considerazione di questo, al primo passaggio il numero in posizione array [5], non sarà mai pescato giusto?
Al massimo arriviamo alla pen'ultima posizione dell'array.
Non alteriamo le probabilità? Devono avere tutti la stessa possibilità di uscire, no?
Voglio precisare che ho fatto solo un ragionamento veloce, potrei aver detto una stupidata, devo analizzare bene.
é presto e devo andare al lavoro!!! :ciao:
Ultima modifica di gila75 il giovedì 5 dicembre 2013, 19:04, modificato 1 volta in totale.

Avatar utente
BlueEyes
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1330
Iscrizione: giovedì 15 marzo 2012, 14:08

Re: [C] numeri casuali senza ripetizione

Messaggio da BlueEyes » giovedì 5 dicembre 2013, 9:37

E' lecito commentare con un laconico "mi piace"? Ecco il test effettuato.
Ciao

Codice: Seleziona tutto

C:\>gcc rus.c
C:\>a // eseguibile in ambiente Windows
----------------------------------
> array[] = {0, 1, 2, 3, 4, 5, 6, 7}

Estrazione di 20 permutazioni pseudocasuali di lunghezza 8:
rank = 17498, array[] = {1, 5, 6, 4, 7, 0, 3, 2}
rank = 9935, array[] = {6, 0, 5, 1, 4, 3, 2, 7}
rank = 7350, array[] = {2, 3, 4, 0, 7, 5, 1, 6}
rank = 22174, array[] = {2, 3, 4, 1, 0, 5, 7, 6}
rank = 15292, array[] = {5, 7, 2, 1, 6, 3, 0, 4}
rank = 25294, array[] = {2, 5, 7, 3, 0, 1, 4, 6}
rank = 32135, array[] = {4, 2, 1, 6, 0, 3, 5, 7}
rank = 1024, array[] = {1, 6, 4, 5, 3, 7, 2, 0}
rank = 6489, array[] = {5, 2, 0, 3, 4, 7, 6, 1}
rank = 6381, array[] = {1, 2, 0, 4, 3, 7, 6, 5}
rank = 28036, array[] = {6, 5, 1, 0, 3, 2, 7, 4}
rank = 32564, array[] = {0, 2, 7, 6, 1, 5, 3, 4}
rank = 16245, array[] = {4, 6, 7, 1, 3, 2, 0, 5}
rank = 29616, array[] = {5, 2, 4, 1, 3, 7, 6, 0}
rank = 14644, array[] = {1, 7, 2, 0, 5, 6, 3, 4}
rank = 15996, array[] = {5, 0, 6, 1, 2, 3, 7, 4}
rank = 30683, array[] = {0, 7, 4, 2, 5, 1, 6, 3}
rank = 20488, array[] = {2, 1, 3, 4, 7, 5, 6, 0}
rank = 23250, array[] = {7, 3, 0, 5, 4, 6, 1, 2}
rank = 24561, array[] = {6, 7, 5, 2, 3, 0, 4, 1}

rank = 0, array[] = {1, 2, 3, 4, 5, 6, 7, 0}
rank = 40319, array[] = {0, 1, 2, 3, 4, 5, 6, 7}


Avatar utente
Vincenzo1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 450
Iscrizione: lunedì 14 gennaio 2013, 14:21
Desktop: Unity
Distribuzione: Ubuntu 18.04.3 LTS x86_64
Località: Villabate(PA)
Contatti:

Re: [C] numeri casuali senza ripetizione

Messaggio da Vincenzo1968 » giovedì 5 dicembre 2013, 13:22

M_A_W_ 1968 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4497400#p4497400][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Provate a dare un'occhiata a questo codice.

Codice: Seleziona tutto

/*
** Implementazione didattica dell'algoritmo di unranking 
** in tempo lineare definito da Frank Ruskey & Wendy Myrvold
** in "Ranking and unranking permutations in linear time"
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* 
** Dimensione massima per l'array delle permutazioni, 
** non minore di PERM_SIZE definito a seguito.
*/ 
#define ASIZE 8
/* Dimensione delle permutazioni */
#define PERM_SIZE 6
/* Il fattoriale della dimensione appena definita */ 
#define PERM_SPACE 720
/* Numero di estrazioni pseudorandom desiderate */
#define NUM_EXTRACT 12

/* Definire per abilitare il debug nella funzione unrank */ 
//#define VERBOSE
/* 
** Definire per generare TUTTE le permutazioni 
** (a vs. rischio e pericolo). 
*/ 
//#define EXHAUSTIVE

void unrank(size_t size, size_t rank, unsigned int *pi)
{
    if (size > 0)
    {
        register unsigned int q, mod;
        register unsigned int t;

        /* 
        ** Precalcolo e memorizzazione ai soli fini didattici e di debug.
        ** Di fatto, il compilatore su x86 dovrebbe invocare una singola
        ** istruzione IDIV che calcola resto e quoziente in due registri.        
        */
        q = rank / size;
        mod = rank % size;

#ifdef VERBOSE
        printf("> n = %d, r = %d: int(r/n) = %d, mod(r, n) = %d\n",
               size, rank, q, mod);
        printf("> swapping pi[%d] = %d and pi[%d] = %d\n",
               size -1, pi[size -1], mod, pi[mod]);
#endif
        /* SWAP(pi[n-1], pi[n%r]) */
        t = pi[size -1];
        pi[size -1] = pi[mod];
        pi[mod] = t;

        /* Tail recursion */
        unrank(size -1, q, pi);
    } 
}

void init(size_t size, unsigned int *pi)
{
    size_t i;
    for (i = 0; i < size; ++i)
    {
        pi[i] = i;
    }
}

int main(void)
{
    unsigned int pi[ASIZE];
    size_t i;
    time_t t;

    srand((unsigned)time(&t));
  
    init(PERM_SIZE, pi);
    printf("> array[] = {%d", pi[0]);
    for (i = 1; i < PERM_SIZE; ++i)
    {
        printf(", %d", pi[i]); 
    }
    puts("}\n");

#ifdef EXHAUSTIVE    
    for (i = 0; i < PERM_SPACE; ++i)
    {
        int k;
        /* 
        ** L'array DEVE essere reinizializzato prima di OGNI chiamata, 
        ** per ottenere l'esatta sequenza descritta nel paper. 
        */ 
        init(PERM_SIZE, pi);
        unrank(PERM_SIZE, i, pi);
        for (k = 0; k < PERM_SIZE; ++k)
        {
            printf("%d ", pi[k]);
        }
        puts("");
    }
#endif

    printf("Estrazione di %d permutazioni pseudocasuali di lunghezza %d:\n", 
           NUM_EXTRACT, PERM_SIZE);
    for (i = 0; i < NUM_EXTRACT; ++i)
    {
        size_t rnd = rand() % (PERM_SPACE -1);
        size_t k;

        init(PERM_SIZE, pi);
        unrank(PERM_SIZE, rnd, pi);
        printf("rank = %3d, array[] = {%d", rnd, pi[0]);  
        for (k = 1; k < PERM_SIZE; ++k)
        {
            printf(", %d", pi[k]);
        }
        puts("}");
    }

    puts("\n");

    init(PERM_SIZE, pi);
    unrank(PERM_SIZE, 0, pi);
    printf("rank = 0, array[] = {%d", pi[0]);  
    for (i = 1; i < PERM_SIZE; ++i)
    {
        printf(", %d", pi[i]);
    }
    puts("}");
    
    init(PERM_SIZE, pi);
    unrank(PERM_SIZE, PERM_SPACE -1, pi);
    printf("rank = %d, array[] = {%d", PERM_SPACE -1, pi[0]);  
    for (i = 1; i < PERM_SIZE; ++i)
    {
        printf(", %d", pi[i]);
    }
    puts("}\n");

    return 0;
}
/* EOF: ruskey.c */
Mi scuso in anticipo per eventuali sviste...

Si, l'algoritmo di Ruskey è più veloce:

Codice: Seleziona tutto

[vincenzo]$ gcc -Wall -W -pedantic -O3 nth_perm3.c -o nth_perm3
[vincenzo]$ time ./nth_perm3 > out3.txt

real	0m0.081s
user	0m0.076s
sys	0m0.004s
[vincenzo]$ gcc -Wall -W -pedantic -O3 nth_perm.c -o nth_perm
[vincenzo]$ time ./nth_perm > out1.txt

real	0m0.094s
user	0m0.088s
sys	0m0.004s
nth_perm3.c:

Codice: Seleziona tutto

/*
** Implementazione didattica dell'algoritmo di unranking
** in tempo lineare definito da Frank Ruskey & Wendy Myrvold
** in "Ranking and unranking permutations in linear time"
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/*
** Dimensione massima per l'array delle permutazioni,
** non minore di PERM_SIZE definito a seguito.
*/
#define ASIZE 8
/* Dimensione delle permutazioni */
#define PERM_SIZE 10
/* Il fattoriale della dimensione appena definita */
#define PERM_SPACE 3628800
/* Numero di estrazioni pseudorandom desiderate */
#define NUM_EXTRACT 12

/* Definire per abilitare il debug nella funzione unrank */
/* #define VERBOSE */
/*
** Definire per generare TUTTE le permutazioni
** (a vs. rischio e pericolo).
*/
/* #define EXHAUSTIVE */

void unrank(size_t size, size_t rank, unsigned int *pi)
{
    if (size > 0)
    {
        register unsigned int q, mod;
        register unsigned int t;

        /*
        ** Precalcolo e memorizzazione ai soli fini didattici e di debug.
        ** Di fatto, il compilatore su x86 dovrebbe invocare una singola
        ** istruzione IDIV che calcola resto e quoziente in due registri.       
        */
        q = rank / size;
        mod = rank % size;

#ifdef VERBOSE
        printf("> n = %d, r = %d: int(r/n) = %d, mod(r, n) = %d\n",
               size, rank, q, mod);
        printf("> swapping pi[%d] = %d and pi[%d] = %d\n",
               size -1, pi[size -1], mod, pi[mod]);
#endif
        /* SWAP(pi[n-1], pi[n%r]) */
        t = pi[size -1];
        pi[size -1] = pi[mod];
        pi[mod] = t;

        /* Tail recursion */
        unrank(size -1, q, pi);
    }
}

void init(size_t size, unsigned int *pi)
{
    size_t i;
    for (i = 0; i < size; ++i)
    {
        pi[i] = i;
    }
}

int main()
{
	int i;	
	int k;	
			
	unsigned int *perm = (unsigned int*)calloc(PERM_SIZE, sizeof(unsigned int));
			
	/* init(PERM_SIZE, perm); */
			
	for ( i = 0; i < 100000; i++ )
	{
		init(PERM_SIZE, perm);
        unrank(PERM_SIZE, i, perm);
        for (k = 0; k < PERM_SIZE; ++k)
        {
            printf("%d ", perm[k]);
        }
        printf("\n");		
	}
		
	free(perm);
	
	return 0;
}
È ormai difficile incontrare un cretino che non sia intelligente e un intelligente che non sia un cretino. [...] Oh i bei cretini di una volta! Genuini, integrali. Come il pane di casa. Come l'olio e il vino dei contadini. (da "Nero su nero" di Leonardo Sciascia)

Avatar utente
M_A_W_ 1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 856
Iscrizione: venerdì 15 febbraio 2013, 3:57
Desktop: KDE
Distribuzione: SuSE
Sesso: Maschile
Località: Un luogo geometrico
Contatti:

Re: [C] numeri casuali senza ripetizione

Messaggio da M_A_W_ 1968 » giovedì 5 dicembre 2013, 19:29

gila75 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4497414#p4497414][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Altra considerazione M_A_W.
Noi dichiariamo un array di N elementi es: 5, quindi avremo 0,1,2,3,4
ASide, come viene chiamato vale N-1, quindi 5-1=4.
Un array di N elementi, in linguaggio C, è indicizzato da tutti e soli gli interi strettamente compresi tra 0 e N-1. In altri termini, la "ultima" locazione sarà A[N-1]. Questo tipo di "off by one" è una caratteristica ricorrente del linguaggio C, e le norme di stile invariabilmente contengono indicazioni e raccomandazioni in merito.
Vincenzo1968 ha scritto: Si, l'algoritmo di Ruskey è più veloce:

Codice: Seleziona tutto

[vincenzo]$ gcc -Wall -W -pedantic -O3 nth_perm3.c -o nth_perm3
[vincenzo]$ time ./nth_perm3 > out3.txt

real	0m0.081s
user	0m0.076s
sys	0m0.004s
[vincenzo]$ gcc -Wall -W -pedantic -O3 nth_perm.c -o nth_perm
[vincenzo]$ time ./nth_perm > out1.txt

real	0m0.094s
user	0m0.088s
sys	0m0.004s
Non vi erano dubbi al riguardo, anche dalla sola analisi statica del codice. :)

Non l'ho aggiunto nei commenti, ma lo ritengo implicito: l'eliminazione della ricorsione è lasciata come facile e piacevole esercizio per il lettore interessato. :D

Codice: Seleziona tutto

/* L'eleganza di questo codice e' a dir poco meravigliosa! */
void unrank(size_t size, size_t rank, unsigned int *pi)
{
    size_t i;

    for (i = size; i > 0; --i)
    {
        register unsigned int t, mod;
        mod = rank % i;
        /* SWAP(pi[n-1], pi[n%r]) */
        t = pi[i -1];
        pi[i -1] = pi[mod];
        pi[mod] = t;

        rank /= i;
    } 
}
BlueEyes ha scritto:
E' lecito commentare con un laconico "mi piace"?
Ne sono contento. Naturalmente l'algoritmo di Myrvold-Ruskey è strettamente correlato all'algoritmo di Knuth (che chiamiamo così per comodità, essendo in realtà noto in letteratura da molti decenni prima del TAoCP ma privo di attribuzione). Infatti, l'algoritmo Knuth presentato sopra può essere banalmente adattato a lavorare in-place su un unico vettore, dimezzando quindi l'occupazione di memoria e modificando la sovrascrittura in uno swap. In tal modo risulta evidente la parentela tra i due approcci: tuttavia, anche a parità di altre condizioni, il Myrvold-Ruskey richiede una singola chiamata al PRNG per ogni permutazione generata, al contrario dello Knuth che ne richiede evidentemente N (a rigore, N-1).

Seguendo l'algoritmo con carta e penna (o abilitando il rozzo debug nel codice sopra proposto), si nota che alcuni scambi sono nulli, avendo destinazione e origine coincidenti. Il codice risultante è comunque in linea di principio più efficiente rispetto all'introduzione di un salto condizionato con un controllo di identità tra i due indici, anche su ampiezze di permutazione molto piccole.

DI fatto, nella sua versione esplicitamente iterativa (e pochissimo varia con la tail recursion), l'algoritmo Myrvold-Ruskey è il più efficiente ad oggi noto per la generazione della k-esima permutazione, tra quelli di elementare implementazione su hardware convenzionale. Ricordo solo, a mero titolo inventariale, che molti vector processor e alcuni DSP avanzati dispongono di istruzioni in grado di effettuare swap multipli non sovrapposti grazie alle istruzioni SIMD, come pure split e unione in memoria tra due vettori in un singolo ciclo di clock, grazie a generatori di indirizzi particolarmente sofisticati ed all'incorporazione on-chip di ampia parte della memoria di lavoro. Così diventa un gioco da ragazzi, oltre al lavoro in parallelo, generare una permutazione "spezzando e intercalando" un vettore in due o più parti, che vengono poi giustapposte come due pettini... :lol:
Ultima modifica di M_A_W_ 1968 il venerdì 6 dicembre 2013, 4:02, modificato 1 volta in totale.
Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo...

"...in una società che sembra sempre più spaventata dai problemi troppo articolati e che rigetta come un corpo estraneo ogni elemento di complessità, sapremo ancora come utilizzare il parere degli esperti?"

Avatar utente
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2617
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: [C] numeri casuali senza ripetizione

Messaggio da gila75 » giovedì 5 dicembre 2013, 20:53

gila75 Immagine ha scritto:Altra considerazione M_A_W.
Noi dichiariamo un array di N elementi es: 5, quindi avremo 0,1,2,3,4
ASide, come viene chiamato vale N-1, quindi 5-1=4.



Un array di N elementi, in linguaggio C, è indicizzato da tutti e soli gli interi strettamente compresi tra 0 e N-1. In altri termini, la "ultima" locazione sarà A[N-1]. Questo tipo di "off by one" è una caratteristica ricorrente del linguaggio C, e le norme di stile invariabilmente contengono indicazioni e raccomandazioni in merito.
Intendo dire che l'ultimo numero dell'array, non sarà mai estratto per primo.
Questo non altera la distribuzione\casualità?
Questo volevo dire

Avatar utente
M_A_W_ 1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 856
Iscrizione: venerdì 15 febbraio 2013, 3:57
Desktop: KDE
Distribuzione: SuSE
Sesso: Maschile
Località: Un luogo geometrico
Contatti:

Re: [C] numeri casuali senza ripetizione

Messaggio da M_A_W_ 1968 » giovedì 5 dicembre 2013, 22:12

gila75 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4497778#p4497778][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto: Intendo dire che l'ultimo numero dell'array, non sarà mai estratto per primo.
Questo non altera la distribuzione\casualità?
Questo volevo dire
Comunque sia, ignora pure tutto il resto e concentrati sull'idea che il core loop dell'algoritmo "vanilla" funziona nel seguente modo:

Codice: Seleziona tutto

#define ASIZE 16
    ...
    for(ASize = ASIZE; ASize > 1; --ASize)
    {
        unsigned int Pos, Ext;

        Pos = rand() % ASize;
        Ext = array[Pos];
        array[Pos] = array[ASize -1];
        /*
        **  ...e se volessimo trasformarlo in uno swap:
        ** array[ASize -1] = Ext;
        ** ...cosi' il cerchio si chiude.
        */  

        printf("%d\n", Ext);
    }
    printf("%d\n", array[0]);
Pos assume quindi valori strettamente compresi tra 0 e N-1 (in questo caso, 15).

Per restare alle banalità didattiche, nel loop compaiono contemporaneamente riferimenti alla variabile ASize ed alla medesima variabile diminuita o aumentata di una unità. Al di là dell'esplicitazione delle condizioni di iterazione nella for() (le altre versioni presentate o suggerite permettono un numero di estrazioni non necessariamente uguale alla dimensione dell'intero array), è pressoché indifferente scegliere l'una o l'altra forma:

Codice: Seleziona tutto

        /* Qui ASize va inizializzato a N */
        Pos = rand() % ASize;
        ...
        array[Pos] = array[ASize -1];
versus

Codice: Seleziona tutto

        /* Qui ASize va inizializzato a N-1 */
        Pos = rand() % (ASize +1);
        ...
        array[Pos] = array[ASize];
In generale, tuttavia, si preferisce la prima forma, anche agendo opportunamente sull'inizializzazione delle variabili, per evitare che - come al solito - qualcuno incespichi nella priorità degli operatori, dimenticando le parentesi. Inoltre, trattandosi di un loop a decremento proprio sulla variabile ASize, con la prima forma l'ottimizzatore in genere riesce ad intercalare nel modo più efficiente le operazioni, evitando una sottrazione ridondante. Si tratta comunque di inezie, purché il codice sia coerente.

Detto questo, nella versione più corretta l'algoritmo - a rigore - termina quando ASize è pari a due, decidendo l'ordine relativo degli ultimi due valori superstiti con un singolo bit pseudorandom e stampando quindi l'ultimo "estratto" al di fuori del loop.
Ultima modifica di M_A_W_ 1968 il lunedì 24 febbraio 2014, 22:12, modificato 1 volta in totale.
Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo...

"...in una società che sembra sempre più spaventata dai problemi troppo articolati e che rigetta come un corpo estraneo ogni elemento di complessità, sapremo ancora come utilizzare il parere degli esperti?"

Avatar utente
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2617
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: [C] numeri casuali senza ripetizione

Messaggio da gila75 » venerdì 6 dicembre 2013, 17:46

Codesto è possibile, ma è con ogni probabilità una svista. Non ho ben presente a quale versione ti riferisci, probabilmente l'introduzione del range ti confonde un po' nella lettura del codice, oppure c'è qualche "fossile" o off-by-one residuato da precedenti utilizzi/presentazioni del medesimo. :lol:
La mia pedanteria è universalmente nota, ma francamente in questi giorni sto operando in condizioni al limite del credibile, in una sede altamente disagiata e avendo a disposizione solo un netbook con schermo da 7". Si fa una fatica immane a leggere e scrivere... Ora rileggo ed eventualmente correggo, grazie.
Scusa M_A_W, sono di stra-fretta e ho letto veloce il tuo post, quindi rispondo solo a questo.
Mi riferisco al primo codice.
Se Asize vale N-1 (array), logicamente il campo d'estrazione di ASize, non potrà mai pescare l'ultimo valore dell'array (contenuto intendo).
Ho fatto un po' di prove e infatti non lo pesca.
A conti fatti se ho 5 numeri e il quinto non potrà mai essere pescato, al primo giro gli altri numeri, hanno una possibilita d 1/4=0.25= 25% a fronte del reale 20%.
Il resto del post, lo leggo con calma appena posso.

Avatar utente
M_A_W_ 1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 856
Iscrizione: venerdì 15 febbraio 2013, 3:57
Desktop: KDE
Distribuzione: SuSE
Sesso: Maschile
Località: Un luogo geometrico
Contatti:

Re: [C] numeri casuali senza ripetizione

Messaggio da M_A_W_ 1968 » sabato 7 dicembre 2013, 19:07

Ricapitoliamo, approfittando di un breve attimo di tregua nel weekend.

Per evitare dispersione, concentro nel presente post tutto il codice finora proposto, con qualche ritocco cosmetico. Per il prosieguo della discussione, fa testo solo quanto qui riportato, o per dirla col terrificante burocratese-legalese italiota del manuale Cencelli, "annulla e sostituisce ogni versione precedente".

Cominciamo con la versione semplificata del range shrink, per l'occasione riveduta nel flavour "tombola natalizia" con un range tra 1 e 90, estremi ovviamente inclusi.

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LIMITE_SUP 90

int main()
{
    int i, ASize;
    int array[LIMITE_SUP];

    time_t t;

    srand((unsigned)time(&t));

    /*
    ** Inizializza opportunamente l'array, in questo
    ** caso con un offset unitario.
    */
    for(i = 0; i < LIMITE_SUP; ++i)
    {
        array[i] = i +1;
    }

    printf("Stampa dei valori compresi tra %d e %d\n"
           "selezionati casualmente (metodo \"range shrink\")\n",
           1, LIMITE_SUP);
    /*
    ** Genera una singola permutazione random dell'array di input,
    ** usando l'algoritmo range shrink di Donald E. Knuth.
    */
    for(i = 1, ASize = LIMITE_SUP; ASize > 1; --ASize)
    {
        int Pos;

        Pos = rand() % ASize;
        printf("[%2d] %2d\n", i++, array[Pos]);
        array[Pos] = array[ASize -1];
    }

    printf("[%2d] %d\n", i, array[0]);

    return 0;
}
/* EOF: estraz2.c*/
Ecco il relativo output:

Codice: Seleziona tutto

Stampa dei valori compresi tra 1 e 90
selezionati casualmente (metodo "range shrink")
[ 1] 45
[ 2] 56
[ 3]  7
[ 4] 58
[ 5] 30
[ 6] 54
[ 7] 80
[ 8] 49
[ 9]  6
[10] 18
[11] 28
[12] 20
[13] 43
[14] 26
[15] 78
[16] 24
[17] 34
[18] 23
[19] 33
[20] 63
[21] 60
[22] 29
[23] 39
[24] 48
[25] 62
[26] 50
[27] 76
[28]  4
[29] 53
[30] 13
[31] 65
[32] 17
[33] 69
[34] 89
[35] 90
[36] 38
[37] 36
[38] 77
[39] 11
[40] 86
[41] 84
[42] 19
[43] 46
[44] 61
[45] 68
[46] 44
[47] 85
[48] 25
[49] 15
[50] 47
[51] 42
[52] 64
[53] 87
[54] 73
[55] 57
[56] 31
[57] 12
[58] 37
[59] 75
[60] 14
[61] 81
[62]  3
[63] 74
[64] 79
[65] 88
[66] 41
[67] 10
[68] 66
[69] 32
[70] 82
[71]  8
[72] 59
[73] 40
[74] 51
[75] 67
[76] 55
[77]  1
[78] 16
[79]  9
[80] 83
[81] 27
[82] 71
[83]  2
[84] 22
[85]  5
[86] 21
[87] 52
[88] 72
[89] 70
[90] 35

Al secondo posto in classifica, la versione didattica "verbose" del sullodato range shrink, più facile da seguire.

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LIMITE_SUP 12
#define LIMITE_INF 5
#define ASIZE (LIMITE_SUP - LIMITE_INF +1)
#define GUARD_VALUE 0xFF

#define H_SEP_STAR "************************************************************"
#define H_SEP_LINE "------------------------------------------------------------"

#define VERBOSE

void Inspect(int *A, size_t siz, int P, int Id)
{
    int i;

    printf("> i = %d, random = %d, elementi attivi = %d:"
           "\n> Array[] = {%2d",
           Id, P, siz, A[0]);

    for (i = 1; i < siz; ++i)
    {
        printf(", %2d", A[i]);
    }
    printf("}\n>          ");

    for(i = 0; i < P; ++i)
    {
        printf("    ");
    }
    printf("  ^^\n");
}

int main()
{
    int i;
    int Ext, Pos;
    size_t ASize;
    int array[ASIZE];
    time_t t;

    srand((unsigned)time(&t));

#ifdef VERBOSE
    puts(H_SEP_STAR);
    for(i = 0; i < ASIZE; ++i)
    {
        array[i] = i + LIMITE_INF;
        printf("> array[%d] = %d\n", i, array[i]);
    }
#endif

    puts(H_SEP_STAR);
    printf("Stampa dei valori compresi tra %d e %d\n"
           "selezionati casualmente (metodo \"range shrink\")\n",
           LIMITE_INF, LIMITE_SUP);

    for(i = 0, ASize = ASIZE; ASize > 1; ++i, --ASize)
    {
        Pos = rand() % ASize;
        Ext = array[Pos];

#ifdef VERBOSE
        puts(H_SEP_LINE);
        Inspect(array, ASize, Pos, i +1);
        puts(H_SEP_LINE);
#endif
        array[Pos] = array[ASize -1];
        array[ASize -1] = GUARD_VALUE;
        printf("[%2d] %d\n", i + 1, Ext);
    }

#ifdef VERBOSE
    puts(H_SEP_LINE);
    Inspect(array, ASize, 0, i +1);
    puts(H_SEP_LINE);
#endif
    printf("[%2d] %d\n", i + 1, array[0]);
    puts(H_SEP_STAR);

	return 0;
}
/* EOF: estraz3.c */
Eccone l'output:

Codice: Seleziona tutto

************************************************************
> array[0] = 5
> array[1] = 6
> array[2] = 7
> array[3] = 8
> array[4] = 9
> array[5] = 10
> array[6] = 11
> array[7] = 12
************************************************************
Stampa dei valori compresi tra 5 e 12
selezionati casualmente (metodo "range shrink")
------------------------------------------------------------
> i = 1, random = 2, elementi attivi = 8:
> Array[] = { 5,  6,  7,  8,  9, 10, 11, 12}
>                    ^^
------------------------------------------------------------
[ 1] 7
------------------------------------------------------------
> i = 2, random = 5, elementi attivi = 7:
> Array[] = { 5,  6, 12,  8,  9, 10, 11}
>                                ^^
------------------------------------------------------------
[ 2] 10
------------------------------------------------------------
> i = 3, random = 2, elementi attivi = 6:
> Array[] = { 5,  6, 12,  8,  9, 11}
>                    ^^
------------------------------------------------------------
[ 3] 12
------------------------------------------------------------
> i = 4, random = 4, elementi attivi = 5:
> Array[] = { 5,  6, 11,  8,  9}
>                            ^^
------------------------------------------------------------
[ 4] 9
------------------------------------------------------------
> i = 5, random = 1, elementi attivi = 4:
> Array[] = { 5,  6, 11,  8}
>                ^^
------------------------------------------------------------
[ 5] 6
------------------------------------------------------------
> i = 6, random = 1, elementi attivi = 3:
> Array[] = { 5,  8, 11}
>                ^^
------------------------------------------------------------
[ 6] 8
------------------------------------------------------------
> i = 7, random = 1, elementi attivi = 2:
> Array[] = { 5, 11}
>                ^^
------------------------------------------------------------
[ 7] 11
------------------------------------------------------------
> i = 8, random = 0, elementi attivi = 1:
> Array[] = { 5}
>            ^^
------------------------------------------------------------
[ 8] 5
************************************************************

Last and not least, l'algoritmo di Myrvold & Ruskey per la generazione di una permutazione random tra le n! di ampiezza n.

Codice: Seleziona tutto

/*
** Implementazione didattica dell'algoritmo di unranking
** in tempo lineare descritto da Frank Ruskey & Wendy Myrvold
** in "Ranking and unranking permutations in linear time"
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/*
** Dimensione massima per l'array delle permutazioni,
** non minore di PERM_SIZE definito a seguito.
** Introdotta solo come predisposizione per ulteriori
** utilizzi didattici del presente codice.
*/
#define ASIZE 8
/* Dimensione delle permutazioni */
#define PERM_SIZE 6
/* Il fattoriale della dimensione appena definita */
#define PERM_SPACE 720
/* Numero di estrazioni pseudorandom desiderate */
#define NUM_EXTRACT 12

/* Definire per abilitare il debug nella funzione unrank */
/* #define VERBOSE */
/*
** Definire per generare TUTTE le permutazioni
** (a vs. rischio e pericolo).
*/
/* #define EXHAUSTIVE */

#define H_SEP_STAR "************************************************************"
#define H_SEP_LINE "------------------------------------------------------------"

void unrank(size_t size, size_t rank, unsigned int *pi)
{
    size_t i;

    for (i = size; i > 0; --i)
    {
        register unsigned int t, mod;
        mod = rank % i;

        /* SWAP(pi[n-1], pi[n%r]) */
        t = pi[i -1];
        pi[i -1] = pi[mod];
        pi[mod] = t;

        rank /= i;
    }
}

void init(size_t size, unsigned int *pi)
{
    size_t i;
    for (i = 0; i < size; ++i)
    {
        pi[i] = i;
    }
}

int main(void)
{
    unsigned int pi[ASIZE];
    size_t i;
    time_t t;

    srand((unsigned)time(&t));

#ifdef VERBOSE
    init(PERM_SIZE, pi);
    puts(H_SEP_STAR);
    printf("> array[] = {%d", pi[0]);
    for (i = 1; i < PERM_SIZE; ++i)
    {
        printf(", %d", pi[i]);
    }
    puts("}");
    puts(H_SEP_STAR);
#endif

#ifdef EXHAUSTIVE
    for (i = 0; i < PERM_SPACE; ++i)
    {
        int k;
        /*
        ** L'array DEVE essere reinizializzato prima di OGNI chiamata,
        ** per ottenere l'esatta sequenza descritta nel paper.
        */
        init(PERM_SIZE, pi);
        unrank(PERM_SIZE, i, pi);
        for (k = 0; k < PERM_SIZE; ++k)
        {
            printf("%d ", pi[k]);
        }
        puts("");
    }
#endif

    puts(H_SEP_LINE);
    printf("Estrazione di %d permutazioni pseudocasuali di lunghezza %d:\n",
           NUM_EXTRACT, PERM_SIZE);
    for (i = 0; i < NUM_EXTRACT; ++i)
    {
        size_t rnd = rand() % (PERM_SPACE -1);
        size_t k;

        init(PERM_SIZE, pi);
        unrank(PERM_SIZE, rnd, pi);
        printf("rank = %3d, array[] = {%d", rnd, pi[0]);
        for (k = 1; k < PERM_SIZE; ++k)
        {
            printf(", %d", pi[k]);
        }
        puts("}");
    }

    puts(H_SEP_LINE);
    puts("Permutazioni agli estremi del range:");

    init(PERM_SIZE, pi);
    unrank(PERM_SIZE, 0, pi);
    printf("rank =   0, array[] = {%d", pi[0]);
    for (i = 1; i < PERM_SIZE; ++i)
    {
        printf(", %d", pi[i]);
    }
    puts("}");

    init(PERM_SIZE, pi);
    unrank(PERM_SIZE, PERM_SPACE -1, pi);
    printf("rank = %d, array[] = {%d", PERM_SPACE -1, pi[0]);
    for (i = 1; i < PERM_SIZE; ++i)
    {
        printf(", %d", pi[i]);
    }
    puts("}");
    puts(H_SEP_LINE);

    return 0;
}
/* EOF: ruskey.c */
Ed ecco, infine, il relativo output:

Codice: Seleziona tutto

------------------------------------------------------------
Estrazione di 12 permutazioni pseudocasuali di lunghezza 6:
rank = 191, array[] = {3, 0, 4, 2, 1, 5}
rank = 618, array[] = {4, 1, 2, 5, 3, 0}
rank = 710, array[] = {0, 1, 5, 4, 3, 2}
rank = 627, array[] = {5, 1, 2, 0, 4, 3}
rank = 325, array[] = {5, 0, 3, 2, 4, 1}
rank = 489, array[] = {5, 2, 4, 0, 1, 3}
rank = 571, array[] = {4, 2, 5, 3, 0, 1}
rank = 593, array[] = {0, 2, 1, 4, 3, 5}
rank = 329, array[] = {1, 0, 3, 2, 4, 5}
rank =  59, array[] = {3, 2, 0, 1, 4, 5}
rank = 318, array[] = {1, 5, 4, 2, 3, 0}
rank = 633, array[] = {4, 5, 2, 1, 0, 3}
------------------------------------------------------------
Permutazioni agli estremi del range:
rank =   0, array[] = {1, 2, 3, 4, 5, 0}
rank = 719, array[] = {0, 1, 2, 3, 4, 5}
------------------------------------------------------------
Certi di avere fatto cosa gradita, cogliamo l'occasione per porgere distinti saluti, eccetera eccetera (citazione laterale, anche se volutamente non letterale, dalla scena della segretaria dattilografa ne "Il toro, la vergine e il capricorno" con un irresistibile Lionello). :lol:
Ultima modifica di M_A_W_ 1968 il sabato 7 dicembre 2013, 19:26, modificato 3 volte in totale.
Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo...

"...in una società che sembra sempre più spaventata dai problemi troppo articolati e che rigetta come un corpo estraneo ogni elemento di complessità, sapremo ancora come utilizzare il parere degli esperti?"

Avatar utente
M_A_W_ 1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 856
Iscrizione: venerdì 15 febbraio 2013, 3:57
Desktop: KDE
Distribuzione: SuSE
Sesso: Maschile
Località: Un luogo geometrico
Contatti:

Re: [C] numeri casuali senza ripetizione

Messaggio da M_A_W_ 1968 » sabato 7 dicembre 2013, 19:10

NIHIL
Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo...

"...in una società che sembra sempre più spaventata dai problemi troppo articolati e che rigetta come un corpo estraneo ogni elemento di complessità, sapremo ancora come utilizzare il parere degli esperti?"

Scrivi risposta

Ritorna a “Programmazione”

Chi c’è in linea

Visualizzano questa sezione: 0 utenti iscritti e 7 ospiti