[c++] Sempre coi casuali, ce la posso fare..
Ho sempre problemi a generare numeri causuali fatti COME VOGLIO IO 
In questo caso non mi cambia le permutazioni come vorrei, riga dopo riga.
Il mio desiderio è avere qualcosa del genere:
Come si nota non si possono ripetere numeri uguali sulla stessa riga ed il range va da 1 al numero di righe totali 4.
Ovviamente il numero prima dei : è solo il numero di riga indicativo.
Quello che riesco a generare CON LE MIE CAPACITA' CRETINE sarebbe:
Come si può notare, non riesco a fare cambiare la scelta casuale per ciascuna riga... Mi sembrava di essermi posto un qualcosa si facile ma non ce la faccio.
Secondo me sbaglio a "pensare" la funzione srand() che produce numeri pseudo-casuali ma non è possibile produrre la casualità naturale... Quindi non mi "azzera" e rigenera tutto come vorrei...
Spero di capire come lavorarci che sono diversi giorni alle prese con questi "algoritmi casuali"
In questo caso non mi cambia le permutazioni come vorrei, riga dopo riga.
Il mio desiderio è avere qualcosa del genere:
1 : 4 3 1 2 2 : 2 1 3 4 3 : 1 3 4 2 4 : 4 3 1 2
Come si nota non si possono ripetere numeri uguali sulla stessa riga ed il range va da 1 al numero di righe totali 4.
Ovviamente il numero prima dei : è solo il numero di riga indicativo.
Quello che riesco a generare CON LE MIE CAPACITA' CRETINE sarebbe:
1 : 4 1 3 2 2 : 4 1 3 2 3 : 4 1 3 2 4 : 4 1 3 2
Come si può notare, non riesco a fare cambiare la scelta casuale per ciascuna riga... Mi sembrava di essermi posto un qualcosa si facile ma non ce la faccio.
Secondo me sbaglio a "pensare" la funzione srand() che produce numeri pseudo-casuali ma non è possibile produrre la casualità naturale... Quindi non mi "azzera" e rigenera tutto come vorrei...
Spero di capire come lavorarci che sono diversi giorni alle prese con questi "algoritmi casuali"
Risposte
Che compilatore usi? Che funzione? Lo dico perché ieri ho notato che mingw con random non funziona bene e ha un random_device deterministico. Mingw-w64 con GCC 4.9.2 non ha il problema se non ricordo male.
Prova ad usare
Con rand non dovresti avere questo problema.
Comunque se vuoi generare tutte le permutazioni il problema è differente. La libreria standard l'hai guardata? Penso abbia qualcosa per le permutazioni come per fare lo shuffle.
Comunque cerca matters computational su google. C'è un libro che potresti apprezzare. Nota che c'è la versione online legalmente scaricabile, non hai bisogno di comprarlo. Il prezzo della versione stampata è incomprensibilmente alto.
Prova ad usare
std::default_random_engine<int> dre{time(0)}; invece che std::default_random_engine<int> dre{rd()}; dove rd è il random device.Con rand non dovresti avere questo problema.
Comunque se vuoi generare tutte le permutazioni il problema è differente. La libreria standard l'hai guardata? Penso abbia qualcosa per le permutazioni come per fare lo shuffle.
Comunque cerca matters computational su google. C'è un libro che potresti apprezzare. Nota che c'è la versione online legalmente scaricabile, non hai bisogno di comprarlo. Il prezzo della versione stampata è incomprensibilmente alto.
Vic senza di voi (te ed Apa) non saprei davvero che fare... Grazie davvero prima di tutto! E non mi stancherò mai di scriverlo, dirlo e pensarlo.
Ti posto il codice ma è in continuo cambiamento quindi ti metto qualcosa da cui partire.
Compilo semplicemente con g++ nome.cpp
Che poi è sempre lo stesso che produco senza fare copia incolla..
Ora pensavo di fare una matrice ma mi sto innervosendo non poco
Ti posto il codice ma è in continuo cambiamento quindi ti metto qualcosa da cui partire.
Compilo semplicemente con g++ nome.cpp
Che poi è sempre lo stesso che produco senza fare copia incolla..
#include <fstream>
#include <time.h>
#include <vector>
using namespace std;
void casualesenzaripet(vector < int >&v, int n){
int r;
bool ripeti = false;
for (int i = 0; i < n; i++)
{
r = rand () % n + 1;
for (int c = 0; c < i; c++)
{
if (v[c] == r)
{
ripeti = true;
c = i;
}
}
if (ripeti == true)
{
i = i - 1;
}
else
{
v[i] = r;
//cout<<r<<endl;
}
ripeti = false;
}
}
int
main (void)
{
ofstream out ("provetta.txt");
int N = 4;
//forse la funzione srand() è una funzione che produce numeri pseudo-casuali e non è possibile produrre la casualità che vorrei
for (int ii=0; ii<N; ii++){
out<<ii+1<<" : ";
for (int jj=0; jj<N; jj++){
srand (time (NULL));
vector < int > v (N);
casualesenzaripet(v,N);
out<< v[jj] <<" ";
}
out<<endl;
}
return 0;
}
Ora pensavo di fare una matrice ma mi sto innervosendo non poco
Ora sono con il tablet ma srand dovresti toglierlo metterlo prima del ciclo, basta inizializzare una sola volta.
Sì l'avevo provato ma poi mi ripete i numeri e non voglio ripetizioni.
Cioé su ogni riga non voglio ripetizioni ma su una riga nuova tutto inizia da zero.
Sembrava una cavolata invece, per me, non lo è.
Cioé su ogni riga non voglio ripetizioni ma su una riga nuova tutto inizia da zero.
Sembrava una cavolata invece, per me, non lo è.
Per n=4 ci sono n!=4! = 24 permutazioni diverse. In questo caso ti conviene probabilmente generare tutte le permutazioni e poi estrarne 4 con uno shuffle. Se avessi n=100 allora sarebbe molto improbabile trovare due volte la stessa permutazione e quindi ti conviene generarli separatamente (inoltre il numero di permutazioni non starebbe in memoria).
Anche questo caso ho provato VIC 
Come vedi l'impegno lo metto ma non HO MAI IN MANO QUELLO CHE MI FISSO COME OBIETTIVO!!!!
Anche il codice ultimo postato "potrebbe" andare bene ma non genero casuali riga per riga... E' come imbrogliare così
#include <fstream>
#include <stdlib.h>
#include <time.h>
#include <vector>
using namespace std;
void scambia (int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void frulla ( int arr[], int n )
{
srand ( time(NULL) );
for (int i = n-1; i > 0; i--){
int j = rand() % (i+1);
scambia(&arr[i], &arr[j]);
}
}
int main(void){
ofstream out ("provetta2.txt");
int arr[10];
for(int i=0; i<10; i++)
arr[i] = i+1;
int n = sizeof(arr)/ sizeof(arr[0]);
for(int j=0; j<10; j++){
frulla (arr, n);
out<<j+1<<" : ";
for (int i = 0; i < n; i++)
out<< arr[i]<<" ";
out<<endl;
}
return 0;
}
Come vedi l'impegno lo metto ma non HO MAI IN MANO QUELLO CHE MI FISSO COME OBIETTIVO!!!!
Anche il codice ultimo postato "potrebbe" andare bene ma non genero casuali riga per riga... E' come imbrogliare così
Perché non iniziare con le cose semplici? Genera una riga per volta in modo casuale e confrontala con le precedenti. Se non va bene ne generi una nuova. Per \(n\) basso la probabilità di dover generare una nuova permutazione è alta, ma con il crescere di \(n\) questo evento diventa sempre meno probabile. Per velocizzare i confronti potrebbe essere comodo generarti un qualche tipo di hash dalla permutazione (ma si tratta di una ottimizzazione che potresti considerare più avanti).
Apa forse è il rand che non so usare bene ancora o forse, come dice Vic, c'é qualcosa che non va.
La seconda versione che ho scritto li mescola ma fa pietà....
Con i numeri casuali veramente è sempre un bordello però!
La seconda versione che ho scritto li mescola ma fa pietà....
Con i numeri casuali veramente è sempre un bordello però!
Il problema continua ad essere srand. Va chiamato solo quando necessario. E se viene inizializzato con time va chiamato con almeno un secondo di differenza tra le diverse chiamate. Chiamare due volte srand con lo stesso valore porta a generare esattamente la stessa sequenza. L'unico vero elemento casuale di un generatore pseudocasuale è il seed (quello che setti con srand). Il resto è un metodo deterministico con particolari proprietà statistiche.
Ok, allora su consigli di addormentare il processo in questo caso? Non so bene come farlo correttamente.
Grazie
Grazie
No, chiama srand una volta all'inizio del programma..
#include <fstream>
//#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>
using namespace std;
void casualesenzaripet(vector < int >&v, int n){
int r;
bool ripeti = false;
for (int i = 0; i < n; i++)
{
r = rand () % n + 1;
for (int c = 0; c < i; c++)
{
if (v[c] == r)
{
ripeti = true;
c = i;
}
}
if (ripeti == true)
i = i - 1;
else
v[i] = r;
//cout<<r<<endl;
ripeti = false;
}
}
int
main (void)
{
srand (time (NULL));
ofstream out ("prova_n.txt");
int N = 4;
for (int ii=0; ii<N; ii++){
out<<ii+1<<" : ";
for (int jj=0; jj<N; jj++){
vector < int > v (N);
casualesenzaripet(v,N);
out<< v[jj] <<" ";
}
out<<endl;
}
return 0;
}
Questo è l'output e ripete i numeri sulle righe (ossia dove vorrei non si ripetessero).
1 : 3 1 1 2 2 : 1 4 3 1 3 : 3 3 3 3 4 : 2 4 1 2
Ma allora sbaglio, vergognosamente, il rimpimento del vettore?
Alcuni commenti:
1. Non c'è alcuna ragione di scrivere if (ripeti == true). if (ripeti) è del tutto equivalente.
2. Nel seguente codice forse volevi mettere una parentesi:
3. Cerca di scrivere il codice perfettamente formattato (ci sono tool specifici). Quasi tutti gli editor hanno in effetti questa funzionalità. Permette di risolvere alcuni errori semplicemente guardando il codice.
1. Non c'è alcuna ragione di scrivere if (ripeti == true). if (ripeti) è del tutto equivalente.
2. Nel seguente codice forse volevi mettere una parentesi:
else
v[i] = r;
//cout<<r<<endl;
ripeti = false;
3. Cerca di scrivere il codice perfettamente formattato (ci sono tool specifici). Quasi tutti gli editor hanno in effetti questa funzionalità. Permette di risolvere alcuni errori semplicemente guardando il codice.
No la parentesi è come se fosse:
Si uso: indent nomeprogramma.cpp
..
else
{
v[i] = r;
//cout<<r<<endl;
}
ripeti = false;
..
Si uso: indent nomeprogramma.cpp
#include <fstream>
//#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>
using namespace std;
void
casualesenzaripet (vector < int >&v, int n)
{
int r;
bool ripeti = false;
for (int i = 0; i < n; i++)
{
r = rand () % n + 1;
for (int c = 0; c < i; c++)
{
if (v[c] == r)
{
ripeti = true;
c = i;
}
}
if (ripeti == true)
{
i = i - 1;
}
else
{
v[i] = r;
//cout<<r<<endl;
}
ripeti = false;
}
}
int
main (void)
{
srand (time (NULL));
ofstream out ("prova_n.txt");
int N = 4;
for (int ii = 0; ii < N; ii++)
{
out << ii + 1 << " : ";
for (int jj = 0; jj < N; jj++)
{
vector < int >v (N);
casualesenzaripet (v, N);
out << v[jj] << " ";
}
out << endl;
}
return 0;
}
Per prima cosa puoi semplicemente usare una funzione come std::random_shuffle/std::shuffle per ottenere il risultato voluto. Volendo però implementarla, credo sia opportuno conoscere il metodo corretto di implementare tale funzione. Cercare tale valore all'interno dell'array NON è il metodo corretto. Supponiamo di avere una successione di simboli qualsiasi:
\[ s_1, s_2 \dots s_N \]
Vogliamo ottenere una permutazione
\[ s_{\sigma(1)}, s_{\sigma(2)} \dots s_{\sigma(N)} \]
a partire da una successione di numeri casuali
\[ r_1, r_2, \dots r_N \]
Ovviamente non è sufficiente impostare qualcosa come \( \sigma(i) = r_i \) perché ci potrebbero essere delle ripetizioni.
Possiamo però ragionare in questo modo. Una permutazione di \(N\) simboli può essere costruita a partire da una permutazione qualsiasi di \(N-1\) di questi simboli inserendo l'N-esimo valore alla fine (o in qualsiasi altra posizione). Possiamo quindi scegliere un simbolo casuale (generando un valore da 1 a N) e spostarlo con uno swap alla fine della nostra sequenza. A questo punto non ci resta che generare una permutazione casuale del resto della sequenza. Generiamo quindi un valore da \(1\) a \(N-1\) e facciamo un swap per spostare quest'altro valore nella penultima posizione dell'array. Proseguendo così fino alla fine abbiamo generato una permutazione casuale del nostro array. Questo algoritmo prende il nome di Fisher–Yates shuffle.
\[ s_1, s_2 \dots s_N \]
Vogliamo ottenere una permutazione
\[ s_{\sigma(1)}, s_{\sigma(2)} \dots s_{\sigma(N)} \]
a partire da una successione di numeri casuali
\[ r_1, r_2, \dots r_N \]
Ovviamente non è sufficiente impostare qualcosa come \( \sigma(i) = r_i \) perché ci potrebbero essere delle ripetizioni.
Possiamo però ragionare in questo modo. Una permutazione di \(N\) simboli può essere costruita a partire da una permutazione qualsiasi di \(N-1\) di questi simboli inserendo l'N-esimo valore alla fine (o in qualsiasi altra posizione). Possiamo quindi scegliere un simbolo casuale (generando un valore da 1 a N) e spostarlo con uno swap alla fine della nostra sequenza. A questo punto non ci resta che generare una permutazione casuale del resto della sequenza. Generiamo quindi un valore da \(1\) a \(N-1\) e facciamo un swap per spostare quest'altro valore nella penultima posizione dell'array. Proseguendo così fino alla fine abbiamo generato una permutazione casuale del nostro array. Questo algoritmo prende il nome di Fisher–Yates shuffle.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo