[VB.net]Evitare ripetizione numero con random

[oregon]

Non mi pare tu abbia seguito il mio consiglio ...

[U235]

Non può ripetersi l'ultimo uscito (che è quello che volevi fare nel tuo codice), se quello che invece vuoi è che chi è uscito non ri-esca fino al giro successivo devi fare come ha detto oregon (anche se si può anche ottimizzare un po', non c'è necessariamente bisogno di togliere gli elementi).

Ciao MItaly,
questo interessa anche a me come fai senza rimuovere gli elementi?
io ad esempio avrei fatto così : (lo scrivo in c# per non dare la pappa pronta a Gian01, anche se basta un traduttore...)

        List<int> nGiocatori;
        int nTotGiocatori = 5;
        public void button_Click(object sender, EventArgs e)
        {
            if (nGiocatori == null || nGiocatori.Count() < 1)
            {
                Random r = new Random();
                nGiocatori = Enumerable.Range(1, nTotGiocatori).OrderBy(o => r.Next(nTotGiocatori)).ToList();
            }
            int nSorteggiato = nGiocatori.First();
            nGiocatori.Remove(nSorteggiato);
        }

[oregon]

Penso basti spostare l'elemento che è stato scelto al posto dell'ultimo e ripetere cercando tra il primo e (l'ultimo-1).
Dopo scambi quello scelto con il penultimo e cerchi tra il primo e (l'ultimo-2) ... chiaro?

[U235]

Penso basti spostare l'elemento che è stato scelto al posto dell'ultimo e ripetere cercando tra il primo e (l'ultimo-1).
Dopo scambi quello scelto con il penultimo e cerchi tra il primo e (l'ultimo-2) ... chiaro?

Si.
Quanto si guadagna in termini di prestazioni e leggibilità in questo modo? si potrebbe vedere un esempio? Perché come lo sto immaginando io non mi pare un gran che...

[oregon]

Mah ... dipende da quanto più impegnativa è l'operazione di Remove rispetto allo scambio di due Item e di quanti Item ci sono nella lista. Adesso non saprei quantificare.

[U235]

Mah ... dipende da quanto più impegnativa è l'operazione di Remove rispetto allo scambio di due Item e di quanti Item ci sono nella lista. Adesso non saprei quantificare.

Per quello volevo vedere un esempio fatto bene, per quantificare con dei test. Per come l'ho immaginato io non andrebbe affatto meglio, ma il punto è che sicuramente c'è un modo migliore.

[Gian01]

Scusate se non ho seguito il consiglio di nessuno di voi... Ho ricominciato tutto da capo e ce l'ho fatta

Public Function Sort()
        SoartedNum = Random.Next(1, DefinitivePlayer)
        If PrecNum <> 0 Then
            If PrecNum = SoartedNum Then
                RepeatSort()
            Else
                SoartedPlayer.Text = "Giocatore " & SoartedNum
                SelObbligo.Enabled = True
                SelVerita.Enabled = True
            End If
        End If
        PrecNum = SoartedNum
    End Function


    Public Function RepeatSort()
        SoartedNum = Random.Next(1, DefinitivePlayer)
        If PrecNum <> 0 Then
            If PrecNum = SoartedNum Then
                Sort()
            Else
                SoartedPlayer.Text = "Giocatore " & SoartedNum
                SelObbligo.Enabled = True
                SelVerita.Enabled = True
            End If
        End If
        PrecNum = SoartedNum
    End Function

Quando premo Sorteggia parte la funzione Sort

[oregon]

Ma che senso ha questo "rimbalzo" tra le due funzioni che sono praticamente uguali??

[Gian01]

L'ho fatto per creare un loop e comunque anche se non ha senso funziona.

[MItaly]

Si.
Quanto si guadagna in termini di prestazioni e leggibilità in questo modo? si potrebbe vedere un esempio? Perché come lo sto immaginando io non mi pare un gran che...

Il concetto è esattamente quello espresso da oregon, e se vuoi deriva da una mentalità da programmatore C dove la "fatica computazionale" per rimuovere un elemento dall'array ricade anche un po' sul programmatore.

Un algoritmo naif che rimuove elementi dal centro di un array "costa" in media i/2 per ogni estrazione (dato che se rimuovi un elemento dal centro di un array devi shiftare di un posto tutti quelli che vengono dopo), dove i è il numero di elementi rimasti, per cui un giro completo "costa"


Al contrario, un algoritmo come quello citato da oregon è O(n), dato che ad ogni giro ti limiti ad effettuare uno scambio (tempo costante) e fai in totale n giri.

L'uso di una lista linkata (che ha rimozione di un elemento qualunque in O(1)) non risolve il problema, perché a quel punto l'O(i) si sposta sul raggiungere l'elemento nella lista (oltre al fatto che in genere le liste concatenate hanno diversi altri svantaggi, tipicamente in termini di continuare a rompere le balle all'allocatore e di avere una data locality molto peggiore).

---

Un'implementazione semplice in C++ dell'agoritmo di cui sopra può essere del tipo:

class PlayersExtractor
{
    unsigned int totPlayers;
    std::vector<unsigned int> players;
    unsigned int remaining;
public:
    PlayersExtractor(unsigned int TotPlayers)
        : totPlayers(TotPlayers), remaining(TotPlayers), players(TotPlayers)
    {
        for(unsigned int i=0; i<totPlayers; ++i)
            players[i]=i;
    }
    
    unsigned int extract()
    {
        if(remaining==0)
            remaining=totPlayers;

        unsigned int chosen=rand()%remaining;  // attenzione, una rand usata in questa maniera ha un bias se totPlayers è grande
        std::swap(players[--remaining], players[chosen]);
        return players[remaining];
    }
};