Repository 32bit  Forum
Repository 64bit  Wiki

[C++ Algoritms] Ordinare a caso una lista

Forum dedicato alla programmazione.

Moderatore: Staff

Regole del forum
1) Citare in modo preciso il linguaggio di programmazione usato.
2) Se possibile portare un esempio del risultato atteso.
3) Leggere attentamente le risposte ricevute.
4) Scrivere i messaggi con il colore di default, evitare altri colori.
5) Scrivere in Italiano o in Inglese, se possibile grammaticalmente corretto, evitate stili di scrittura poco chiari, quindi nessuna abbreviazione tipo telegramma o scrittura stile SMS o CHAT.
6) Appena registrati è consigliato presentarsi nel forum dedicato.

La non osservanza delle regole porta a provvedimenti di vari tipo da parte dello staff, in particolare la non osservanza della regola 5 porta alla cancellazione del post e alla segnalazione dell'utente. In caso di recidività l'utente rischia il ban temporaneo.

[C++ Algoritms] Ordinare a caso una lista

Messaggioda Spiros » lun feb 18, 2008 20:23

Qui (http://www.cppreference.com/cppalgorith ... uffle.html) ho trovato un algoritmo che mi serve: ho una lista di tot elementi e vorrei che questi venissero ordinati pseudo-casualmente (non mi interessa molto la vera e propria casualità).
Ho provato così:

Codice: Seleziona tutto
random_shuffle(lista.begin(), lista.end());

ma g++ ha restituito:

Codice: Seleziona tutto
/usr/include/c++/4.1.3/bits/stl_algo.h: In function ‘void std::random_shuffle(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = std::_List_iterator<int>]’:
Tabella.cpp:58:   instantiated from here
/usr/include/c++/4.1.3/bits/stl_algo.h:1905: error: no match for ‘operator+’ in ‘__first + 1’
Tabella.cpp:58:   instantiated from here
/usr/include/c++/4.1.3/bits/stl_algo.h:1906: error: no match for ‘operator-’ in ‘__i - __first’
make: *** [Tabella.o] Error 1



Quindi non ho sbagliato io, ma chi ha scritto la funzione? Oppure devo usare vectors e non posso con le liste?
Spiros
Linux 1.0
Linux 1.0
 
Messaggi: 36
Iscritto il: lun dic 03, 2007 12:58
Località: Zurigo (CH)

Re: [C++ Algoritms] Ordinare a caso una lista

Messaggioda ksniffer » lun feb 18, 2008 23:15

gcc 4.1.3? te lo sei installato da te?

incolla un po' di codice così verifico dov'è l'errore.
Avatar utente
ksniffer
Linux 2.6
Linux 2.6
 
Messaggi: 540
Iscritto il: lun lug 30, 2007 12:18
Kernel: 2.6.34
Desktop: KDE 4.4.4
Distribuzione: ArchLinux

Re: [C++ Algoritms] Ordinare a caso una lista

Messaggioda Spiros » mar feb 19, 2008 7:46

No, da repository (Ubuntu).
Comunque ho risolto con le deque (ho visto qui che è la più completa) al posto della list. Con questa non ho più quel problema.
Ma ora vorrei poter avere una permutazione più casuale. Evidentemente la casualità viene inizializzata sempre nello stesso modo, perché si ottiene sempre lo stesso risultato.
Se volete un po' di codice, ma ci vorrà un po' di spazio per spiegarvelo. Ho derivato una classe dai bitset<961> per aggiungere qualche metodo.
Spiros
Linux 1.0
Linux 1.0
 
Messaggi: 36
Iscritto il: lun dic 03, 2007 12:58
Località: Zurigo (CH)

Re: [C++ Algoritms] Ordinare a caso una lista

Messaggioda lamarozzo » mar feb 19, 2008 9:09

La lista ti viene ordinata sempre allo stesso modo perchè devi inizializzare il generatore di numeri random con un seed diverso ogni volta.

Se usi rand() l'initializzatore è srand(long int seed), altrimenti (scelta consigliata) per drand48 c'è srand48(long int seed). Una tecnica comune consiste nell'inizializzare il generatore con l'ora di sistema cosicchè avrai una lista diversa per ogni secondo del giorno. Ad esempio

Codice: Seleziona tutto
#include <time.h>
...
srand48(time(0));
...


Ciao.
Avatar utente
lamarozzo
Linux 2.6
Linux 2.6
 
Messaggi: 732
Iscritto il: mer lug 13, 2005 23:00
Località: Roma
Desktop: xfce
Distribuzione: archlinux

Re: [C++ Algoritms] Ordinare a caso una lista

Messaggioda Spiros » mar feb 19, 2008 16:44

Si', so come funzionano rand() e srand(). Quindi dovrei inizializzare con srand() o srand48() e la funzione random_shuffle() dara' risultati casuali?
Spiros
Linux 1.0
Linux 1.0
 
Messaggi: 36
Iscritto il: lun dic 03, 2007 12:58
Località: Zurigo (CH)

Re: [C++ Algoritms] Ordinare a caso una lista

Messaggioda lamarozzo » mar feb 19, 2008 18:15

se quelle sono le funzioni utilizzate da random_shuffle(), ogni volta che usi un seed diverso per l'inizializzazione dovresti avere sequenze casuali completamente diverse (o meglio scorrelate).
Avatar utente
lamarozzo
Linux 2.6
Linux 2.6
 
Messaggi: 732
Iscritto il: mer lug 13, 2005 23:00
Località: Roma
Desktop: xfce
Distribuzione: archlinux


Torna a Programmazione

Chi c’è in linea

Visitano il forum: Nessuno e 4 ospiti