VB.net - Permutationen eines 9 Stück (Auswuchten Speichen eines Rades)

Question

Ich habe ein Rad, das 9 Speichen nimmt, aufgrund von Fertigungstoleranzen jede Speiche hat ein anderes Gewicht.

Ich muss die Speichen am Rad so anordnen, dass es am wenigsten aus dem Gleichgewicht ist.

das Berechnen der Rest I Summe der Vektoren (Komplex System.Numerics), dh

Complex für Speiche # 1 = Complex.FromPolarCoordinates (Gewicht # 1, 0)

und

Komplex für die Speiche # 2 = Complex.FromPolarCoordinates (Gewicht # 2, 2 * math.pi/9)

nach allen Berechnungen durchführen ich die resultierende erhalten und die komplexe Echt sparen, Complex.real

dann ändere ich die Reihenfolge der Speichen und berechne das complex.real neu.

Ich habe 2 Fragen,

1) Wie kann ich die Permutationen berechnen, effizient die Reihenfolge ändern? Ich möchte 9 verschachtelte Schleifen für die (362880) 9 vermeiden! Permutationen?

2) Gibt es eine Abkürzung für die Iteration?

Ich bin mir nicht sicher, welche anderen Permutationsanwendungen es gibt, die als Vergleich verwendet werden könnten.

Meine größte Sorge ist die Effizienz, ich habe heute den Code skizziert und bin im Permutationsbereich steckengeblieben. Ich poste später etwas Code.

Vielen Dank im Voraus

habe ich eine Klasse von Speichen und Gewichte, von diesem I permitations

Answer 1

Hier ist mein Code basiert auf einem klassischen Algorithmus, der von Donald Knuth entwickelt testen. (Er schrieb eine große Reihe von Büchern, übrigens.) Sie können die Bytes wahrscheinlich in ganze Zahlen ändern, da Sie nur 9 haben werden! = 362880 Permutationen. Um zu verwenden, erstellen Sie eine Liste von Bytes mit den Werten 0 - 8. (In dieser Reihenfolge!) Dies ist Ihre erste Permutation. Rufen Sie in einer Do-Schleife den Algorithmus mit Ihrer Liste auf, bis er false zurückgibt. Jedes Mal, wenn der Algorithmus aufgerufen wird, wird die Liste zur nächsten Permutation umgeordnet.

Public Function NextPermutation(numList As List(Of Byte)) As Boolean 
    ' Donald Knuth's algorithm from the "Art of Computer Programming" 
    ' 1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, the permutation is the last permutation. 
    ' 2. Find the largest index l such that a[j] < a[l]. Since j + 1 is such an index, l is well defined and satisfies j < l. 
    ' 3. Swap a[j] with a[l]. 
    ' 4. Reverse the sequence from a[j + 1] up to and including the final element a[n]. 
    ' To get all the permutations, one must start with the 'first' one, which is defined as having all items in ascending order, for example 12345. 
    Dim largestIndex As Integer = -1 
    Dim i, j As Integer 
    For i = numList.Count - 2 To 0 Step -1 
     If numList(i) < numList(i + 1) Then 
      largestIndex = i 
      Exit For 
     End If 
    Next 
    If largestIndex < 0 Then Return False 
    Dim largestIndex2 As Integer = -1 
    For i = numList.Count - 1 To 0 Step -1 
     If numList(largestIndex) < numList(i) Then 
      largestIndex2 = i 
      Exit For 
     End If 
    Next 
    Dim tmp As Byte = numList(largestIndex) 
    numList(largestIndex) = numList(largestIndex2) 
    numList(largestIndex2) = tmp 
    i = largestIndex + 1 
    j = numList.Count - 1 
    While i < j 
     tmp = numList(i) 
     numList(i) = numList(j) 
     numList(j) = tmp 
     i += 1 
     j -= 1 
    End While 

    Return True 
End Function 

Sie sollten auch vorberechnet was Sie können, bevor die Permutationen zu starten. Speichern Sie beispielsweise 2*math.pi/9 in einer lokalen Variablen und verwenden Sie die Variable. Vielleicht können Sie auch wiederholte Aufrufe von Complex.FromPolarCoordinates vermeiden, aber ich habe mich nicht in die Details Ihres Algorithmus vertieft, daher bin ich mir nicht sicher, ob das nicht möglich ist.

Hier ist ein kurzes Beispiel, wie Sie die Funktion verwenden:

Dim spokes As New List(Of Byte) 
    For i As Byte = 0 To 8 
     spokes.Add(i) 
    Next 

    Do 
     'Do you balance calculation here. 


    Loop While NextPermutation(Spokes)