Jag en n*n array som ska fyllas till p% (p i decimal form). Dessa n*n*p element ska ges värdet boolean TRUE. Problemet är elementen ska väljas slumpvis. Jag använder för tillfället följande algoritm.

Do

slumpa fram en ny position i arrayen

om denna position är FALSE så ge värdet TRUE och låt m=m+1

om m = n*n*p exit do

Loop

Problemet med denna algoritm är att den skalar (scale) som n^2 vilket jag helst vill unvika.

Så min fråga är om det finns en mer effektiv algoritm (som skalar t.ex. som n) för att lösa mitt problem.


Pedro

Du kan lösa det på följande sätt:

    Class key
        Public X As Long
        Public Y As Long

        Public Sub New(ByVal X As Long, ByVal Y As Long)
            Me.X = X
            Me.Y = Y
        End Sub
    End Class

    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        Const n As Long = 10
        Const p As Double = 0.5
        Dim data(n, n) As Boolean

        Dim x As Long, y As Long
        Dim keys As New ArrayList(n * n)

        For x = 0 To n
            For y = 0 To n
                keys.Add(New key(x, y))
            Next
        Next

        Dim rnd As New Random
        For x = 1 To n * n * p
            y = rnd.Next(0, keys.Count)
            Dim key As key = keys.Item(y)
            keys.RemoveAt(y)
            data(key.X, key.Y) = True
        Next
    End Sub

<b>Så min fråga är om det finns en mer effektiv algoritm (som skalar t.ex. som n) för att lösa mitt problem. </b>
Exakt vad menar du med "skalar"?
Menar du att du får en komplexitet på O(n^2)?

Det är ju tämligen självklart... det kommer du aldrig ifrån.

Andreas metod är lite snabbare, och användbar om du inte vet hur stort p kommer vara, en "ren" variant tar väldigt lång tid för stora p. Å andra sidan tar ju Andreas metod också längre tid för stora p.

En annan, lite enklare, lösning hade varit att välja mellan två algoritmer beroende på p. För p<0.5 väljer du att lägga till element, för p>0.5 börjar du med en fylld och väljer att ta bort element.

Ytterligare ett alternativ hade varit att specialbehandla ett litet intervall runt 0.5, genom att där slumpa tillståndet på varje, och sen slumpa ut små korrektioner.

Ett alternativ som gör samma sak fast utan arraylist:

    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        Const n As Long = 10
        Const p As Double = 0.5
        Dim data(n, n) As Boolean

        Dim i As Integer, t As Integer
        Dim x As Integer, y As Integer
        Dim count As Integer = n * n
        
        Dim rnd As New Random
        For i = 1 To count * p
            t = rnd.Next(0, count)
            Do
                x = t Mod n
                y = t \ n
                t = (t + 1) Mod count
            Loop While data(x, y)
            data(x, y) = True
        Next
    End Sub

Jo, fast som sagt, den blir löjligt ineffektiv för p i området 0.8.
Det är bättre att ha två separata algoritmer, en för under 0.5 och en för över.