Jag har en array med ett okänt antal platser i. Kan någon beskriva hur jag ska göra för att "blanda om" den så att platserna byter plats?

Yay! Hittade en lösning:


För att köra funktionen:__________________________

Dim items() As String = {"Item 1", "Item 2", "Item 3", "Item 4", "Item 5"}
ShuffleArray(items)






Funktionen:__________________________



Public Function ShuffleArray(ByRef Obj())
Dim xCount As Integer = 0
Dim TmpArray()
ReDim TmpArray(0)
Dim xVal As Integer

Randomize()
Do Until xCount = Obj.Length
xVal = CInt(Int(Obj.Length * Rnd()))
If Not Obj(xVal) Is Nothing Then
If xCount > 0 Then ReDim Preserve TmpArray(xCount)
TmpArray(xCount) = Obj(xVal)
xCount += 1
Array.Clear(Obj, xVal, 1)
End If
Loop

Dim i As Integer = 0
For i = 0 To xCount - 1
Obj(i) = TmpArray(i)
Next

End Function

Ett enklare alternativ:

    Public Sub ShuffleArray(ByRef Obj())
        Dim Keys(Obj.Length - 1) As Long
        Randomize()
        For i As Long = 0 To Obj.Length - 1
            Keys(i) = Obj.Length * Rnd()
        Next
        Array.Sort(Keys, Obj)
    End Sub

Det där kan väl knappast vara bra?
Sort måste väl rimligtvis vara stabil och får du då samma Key på två positioner kommer de alltid hamna i rätt "intern ordning". Även om den inte är stabil är det lite lätt obehagligt, då går det att hitta tydliga mönster i slumpen.

Frågeställaren har inte uttryckt några kvalitetskrav på en kryptografisk säker pseudoslumpmässig nummer generator (http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator).
Detta skulle t.ex vara att rekommendera om det handlade om en spelsajt om pengar där det då skulle kunna utnyttjas.
Om det handlar om att slumpa baners, bilder eller något liknande så spelar det ingen större roll.

Men för att göra dig lycklig antar jag, att man kan använda RNGCryptoServiceProvider:

    Public Sub ShuffleArray(ByRef Obj())
        Dim rnd As System.Security.Cryptography.RandomNumberGenerator = New System.Security.Cryptography.RNGCryptoServiceProvider()
        Dim data(7) As Byte
        Dim Keys(Obj.Length - 1) As Long

        For i As Long = 0 To Obj.Length - 1
            rnd.GetBytes(data)
            Keys(i) = System.BitConverter.ToInt64(data, 0)
        Next
        Array.Sort(Keys, Obj)
    End Sub

Om man jämför min kod med Emil Axelsson, så kommer min kod komplexiteten O(n log n), där n är antalet element i arrayen. I värsta fall är den O(n ^ 2).

Det är osäkert på hur lång tid Emil Axelsson kod tar. Ju närmare slutet av arrayen, ju fler träffar kommer man få. T.ex. Om du har en array med en miljon element så kommer det ta lång tid innan den "hittar" till sista luckan.

En rutin som har komplexiteten O(n) är:

    Public Sub ShuffleArray(Of t)(ByRef Obj() As t)
        Dim data(7) As Byte
        Dim rnd As System.Security.Cryptography.RandomNumberGenerator = New System.Security.Cryptography.RNGCryptoServiceProvider()

        For x As Long = 0 To Obj.Length - 1
            Dim tmp As t = Obj(x)

            rnd.GetBytes(data)
            Dim y As Long = System.BitConverter.ToUInt64(data, 0) Mod Obj.Length

            Obj(x) = Obj(y)
            Obj(y) = tmp
        Next
    End Sub

Den är snabb, men jag skulle inte säg att den är "bra".

Om man vill öka säkerheten ytterligare kan man kombinera rutinerna:

    Public Sub ShuffleArray(Of t)(ByRef Obj() As t)
        Dim data(7) As Byte
        Dim Keys(Obj.Length - 1) As Long
        Dim rnd As System.Security.Cryptography.RandomNumberGenerator = New System.Security.Cryptography.RNGCryptoServiceProvider()

        For x As Long = 0 To Obj.Length - 1
            Dim tmp As t = Obj(x)

            rnd.GetBytes(data)
            Keys(x) = System.BitConverter.ToInt64(data, 0)

            rnd.GetBytes(data)
            Dim y As Long = System.BitConverter.ToUInt64(data, 0) Mod Obj.Length

            Obj(x) = Obj(y)
            Obj(y) = tmp
        Next
        Array.Sort(Keys, Obj)
    End Sub

Då missförstod du nog vad jag skrev - slumptalsgeneratorn är nog av så pass kvalitet att den fungerar ändå.

Den första har fortfarande exakt samma problem.

Låt säga att du har 10 värden, från början {0,1,2,3,4,5,6,7,8,9}
Sen råkar du få ut index enligt {3,7,3,7,3,7,3,7,3,7}.
Då får du {0,2,4,6,8,1,3,5,7,9}, givet att sort är stabil. Det krävs inte speciellt avancerade program för att inse att vissa saker kommer oproportionerligt ofta i början resp. i slutet.

Din andra variant fungerar däremot bättre.

Vad kommer till din tredje variant är jag uppriktigt förvånad... Det är ingen som helst skillnad i säkerhet mellan den och tvåan. Den gör ett extra steg bara...


Den i mitt tycke snyggaste varianten är istället att gå via en lista som man plockar bort ur - då är man säker på att det blir rätt.

<b>Då missförstod du nog vad jag skrev - slumptalsgeneratorn är nog av så pass kvalitet att den fungerar ändå.</b>
Vi är överens att den finns en risken för kollision, att två värden i nyckelarrayen.

<b>Den första har fortfarande exakt samma problem.</b>
Det var en stor risk för kollision första varianten, då intervallet på numren i nyckelarrayen var begränsade till antalet element.

<b>Vad kommer till din tredje variant är jag uppriktigt förvånad... Det är ingen som helst skillnad i säkerhet mellan den och tvåan. Den gör ett extra steg bara...</b>
Lite skillnad är det. ;-)