Site Tools


Differences

This shows you the differences between two versions of the page.

Link to this comparison view

developer:scriptsamples:permutations [2015/09/14] (current)
Line 1: Line 1:
 +====== Calculating Permutations ======
 +> **Developer:​** //​[[developer:​rhinoscript|RhinoScript]]//​
 +> **Summary:​** //​Demonstrates how to calculate permutations using RhinoScript.//​
  
 +===== Background =====
 +The permutation of a set is the number of ways that the items in the set can be uniquely ordered. For example, the permutations of the set {1, 2, 3} are {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2} and {3, 2, 1}. For N objects, the number of permutations is N! (N factorial, or 1 * 2 * 3 * ... N).
 +
 +===== Example =====
 +There are a number of methods for calculating permutation sets. The implementation below uses an ordered, or lexicographic,​ permuation algorithm. This algorithm is based on a a permutation algorithm from the book //Practical Algorithms in C++// by Bryan Flamig.
 +
 +<code vb TestPermute.rvb>​
 +Option Explicit
 +
 +'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''​
 +' TestPermute - the Main subroutine
 +'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''​
 +Sub TestPermute
 +  Dim arr, n
 +  'arr = Array("​One",​ "​Two",​ "​Three",​ "​Four"​)
 +  'arr = Array(1, "​Two",​ 3, "​Four"​) ​
 +  arr = Array(1, 2, 3, 4)
 +  n = UBound(arr) + 1
 +  Rhino.ClearCommandHistory
 +  Call Rhino.Print(PermuteCount(n))
 +  Call Permute(arr,​ 0, n)
 +End Sub
 +
 +'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''​
 +' Permute
 +'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''​
 +Sub Permute(ByRef arr, ByVal start, ByVal n)
 +  Dim i, j
 +  Call PermutePrint(arr)
 +  If (start < n) Then
 +    For i = n-2 To start Step -1
 +      For j = i+1 To n-1
 +        Call PermuteSwap(arr,​ i, j)
 +        Call Permute(arr,​ i+1, n)
 +      Next
 +      Call PermuteRotate(arr,​ i, n)
 +    Next
 +  End If
 +End Sub
 +
 +'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''​
 +' PermutePrint
 +'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''​
 +Sub PermutePrint(ByRef arr)
 +  Dim s, v
 +  s = ""​
 +  For Each v In arr
 +    s = s & CStr(v) & vbTab
 +  Next
 +  Rhino.Print s
 +End Sub
 +
 +'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''​
 +' PermuteSwap
 +'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''​
 +Sub PermuteSwap(ByRef arr, ByVal i, ByVal j)
 +  Dim tmp
 +  tmp = arr(i)
 +  arr(i) = arr(j)
 +  arr(j) = tmp
 +End Sub
 +
 +'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''​
 +' PermuteRotate
 +'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''​
 +Sub PermuteRotate(ByRef arr, ByVal start, ByVal n)
 +  Dim tmp, i
 +  tmp = arr(start)
 +  For i = start To n-2
 +    arr(i) = arr(i+1)
 +  Next
 +  arr(n-1) = tmp
 +End Sub
 +
 +'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''​
 +' PermuteCount (e.g. Factorial)
 +'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''​
 +Function PermuteCount(ByVal n)
 +  If n <= 1 Then
 +    PermuteCount = 1
 +  Else
 +    PermuteCount = n * PermuteCount(n-1)
 +  End If
 +End Function
 +</​code>​
 +
 +\\
 +
 +{{tag>​Developer RhinoScript}}
developer/scriptsamples/permutations.txt ยท Last modified: 2015/09/14 (external edit)