Systematic Generation of Permutations

(Total Enumeration)

Determine the number of Objects, n.

Set np = 1, where np is the tally of the total number of permutations. Notice that np is initialized at 1 because the first permutation is given as the simple enumeration of Objects, 1...n.

Set the current position under consideration, Position = n - 1.

for i = 1:n

Objects(i) = i {Enumerate the objects in a vector. Notice that the initial enumeration inherently places the object positions from least to greatest. These are the initial positions of the objects and the assigned values of the objects during the permutation generation process.}

Selection(i) = 1 {Initialize a vector to be used in the systematic selection of Objects--1 if already selected in a permutation, else 0. In this case, all positions are assigned at the start.}

end

Evaluate the Current statistic/equation for the initial ordering. If a statistic is being evaluated, then initialize Index at 1 to be used to track the number of permutations yielding better/equal indices (values) than the Current (Actual) statistic.

while Position > 0

if Objects(Position) > Objects(Position + 1)

Position = Position - 1

continue {This pushes the Objects in the final positions towards the beginning of the permutations being generated. If the assigned value of the target in Position is greater than the assigned value of the object in the next position, then skip the "else" and try again.}

else

Marker = Objects(Position) {The Marker is the object in the position under consideration}

for j = Position:n

Selection(Objects(j)) {De-select the objects holding the higher positions.}

end

for j = Marker + 1:n

if Selection(j) = 0

Objects(Position) = j {Set the object in Position to its next largest available value.}

Selection(j) = 1

break {Prevent selection of more than 1 target.}

end

end

Marker2 = Position {Marker2 assists in assigning unselected Objects to unoccupied positions.}

for j = 1:n

if Selection(j) = 0

Marker2 = Marker2 + 1

Objects(Marker2) = j

Selection(j) = 1

end

end

np = np + 1

Evaluate the index/equation given the full permutation of Objects. If the generated permutation produced a value more extreme than the Current, then adopt the better value in the Current value. If a statistic is being evaluated, then increment Index.

Position = n - 1

{If Position was decremented at the beginning of the while loop on a previous pass, then reset it to n - 1.}

end

end

Finally, if a statistic is being calculated, calculate the one-tailed p-value.
 

General Branch and Bound Algorithm

 

This algorithm assumes that the number of objects, n, has been previously determined. Three functions—EVALUATION (Real), ADJACENCYTEST (Boolean), and BOUNDTEST (Boolean)—are dependent on the criteria being implemented. The Boolean functions are fathoming rules. ADJACENCYTEST tests whether or not the objective function would be improved by exchanging permutation(Position – 1) with permutation(Position). BOUNDTEST calculates an upper bound on the possible objective function value given a partial sequence of n objects; if the upper bound is less than or equal to LowerB, then the partial sequence can not possibly lead to the optimal solution and the branch is pruned.

Position = 1 : permutation(Position) = 1{Initialize position locator in first position.}

for k= 2 to n {Initialize all other positions as "unchosen".}

permutation (k) = 0

next k

LowerB = {0 or determined by heuristic} {Set lower bound on objective function value.}

while (Position <> 1 or permutation(Position) <= n) {Continue until termination criteria is met.}

Position = Position + 1 {Increment position locator.}

BT = false

while not BT {Fathom next branch. Previous branch is pruned when BOUNDTEST is false.}

permutation(Position) = permutation(Position) + 1 {Fathom next branch by incrementing value in "Position" of permutation.}

Redundancy = false {Check Redundancy.}

for k= 1 to p-1

if permutation(Position) = permutation(k) then Redundancy = true

next k

if not Redundancy then

if (Position = 1 and permutation(Position) > n) then exit loop {If termination criteria are met, then exit loop and algorithm.}

Retract = false

if (Position > 1 and permutation(Position) > n) then {Depth retraction retries previous "Position".}

Retract = true

permutation(Position) = 0

Position = Position – 1

end if

if not Retract {If retracted, then remainder of loop is ignored.}

if Position = n – 1 then

incumbent = EVALUATION {Evaluate when complete sequence is ready.}

if incumbent > LowerB then

LowerB = incumbent

BestSolution = permutation

end if

else

if ADJACENCYTEST then BT = BOUNDTEST {Perform fathoming tests.}

end if

end if /* not Retract */

end if /* not Redundancy */

loop /*BT loop */

loop /* Termination loop */

{Return BestSolution and LowerB as objective function value}
 

General Dynamic Programming Algorithm

This algorithm is given as a Visual BASIC function designed to accommodate multi objective/criterion problems. Declarations of appropriate variables and bolded comments are included.  M[q, n, n] holds q n x n matrices. Although the number of matrices q has not been set, the number of objects n is set at 22. The weights applied the matrices are denoted as w(q). The optimal solution and results are reported in a textbox "Results.Text". The results include a table illustrating the process of backtracking after the final stage of the DP process has been performed.

Dim subset(22) As Integer

' subset(n) is the subset (S[k]) of the whole set of objects, S; 1 if chosen, 0 o/w.

Dim subcomp(22) As Integer

' S\S(k) is stored in subcomp, the "complement" of S(k) in S

Dim rowsum As Double

Dim index, current_index, p As Long

' index keeps track of last-added objects and their relative contributions to the objective function

Dim last_added(4194304) As Integer

' stores the last-added object to the optimal subset using the array indices for tracking

Dim obj_val(4194304) As Double

' stores the optimal values of each S(k) to the objective function as per the associated index for last_added

Dim AddedValue, current_val, stored_val As Double

' AddedValue is the contribution of a object to the objective function, i.e. the least-squares loss function; rowsum helps AddedValue

Dim AddOn As Integer

'holds the current object in S/S(k) being considered for the next position in the sequence

Dim nsum As Long

' used after recursion; it is 2^n; that's as big as the arrays get

Dim CumObj(22) As Double

' CumOF holds the cumulative values of the objective function for the successive placements of the objects in the optimal permutation

Dim M2(22, 22) As Double

Dim ObjectTemp(22) As String

nsum = power(2, n) - 1

For i = n + 1 To nsum

obj_val(i) = 0

Next i

For i = 1 To n 'Init the recursion for subsets of size 1

rowsum = 0

For q = 1 To mn

For j = 1 To n

If j <> i Then rowsum = rowsum + w(q) * M(q, i, j)

Next j

Next q

index = power(2, i - 1)

last_added(index) = i

obj_val(index) = rowsum

Next i

For i = 1 To n 'nothing chosen yet; init w/zeros

subset(i) = 0

Next i

'***************************

'***** Begin Recursion *****

'***************************

stagek = False

For k = 1 To (n - 1)

nfirst = 0

If (stagek = False) Then

mm = 0: nh = k

For j = 1 To nh

subset(k + j - nh) = mm + j

Next j

If subset(1) <> (n - k + 1) Then stagek = True

End If

 

Do Until (stagek = False)

If nfirst = 1 Then

If (mm < (n - nh)) Then nh = 0 'k<=n-1; so, n-nh always >0; if mm=0: nh set to 0, then add 1 below

nh = nh + 1 ' nh runs from k to 1

mm = subset(k + 1 - nh) ' need to init subset w/zeros

For j = 1 To nh

subset(k + j - nh) = mm + j

Next j

If subset(1) = (n - k + 1) Then stagek = False ' if n=(k+1) + subset(1), then done with k

End If

If nfirst = 0 Then nfirst = 1

'*********************************

'***** Generate S\S(k) in subcomp*****

'*********************************

For i = 1 To n 'init subcomp

subcomp(i) = 0

Next i

jj = 1

For i = 1 To n ' note that subset and subcomp are integral

Selected = False

For j = 1 To k ' objects are loaded in subset in permuted order

If subset(j) = i Then Selected = True

Next j

If Not Selected Then 'remaining objects are loaded in subcomp in numeric order

subcomp(jj) = i: jj = jj + 1

End If

Next i

'****************************************************************************

'***** Add objects to the end of subset one at a time to find the best last object for S(k+1)

'*****************************************************************************

index = 0

For i = 1 To k

index = index + power(2, subset(i) - 1) 'Used to store best values of S(k)+AddOn in the jj loop

Next i

nk = n - k

For jj = 1 To nk

AddOn = subcomp(jj)

rowsum = 0

For q = 1 To mn

For i = 1 To nk

If AddOn <> subcomp(i) Then

{Perform partial evaluation added to rowsum. This partial evaluation depends on the criterion being applied. For example, to calculate a dominance index, we would use rowsum = rowsum + (w(q) * M(q, AddOn, subcomp(i)) to complete the conditional statement.}

End If

Next i

Next q

AddedValue = rowsum

current_val = obj_val(index) + AddedValue

current_index = index + power(2, AddOn - 1)

stored_val = obj_val(current_index)

If current_val > stored_val Then

obj_val(current_index) = current_val

last_added(current_index) = AddOn

End If

Next jj

Loop

Next k

'***************************

'***** Begin BackTrack *****

'***************************

permutation(n) = last_added(nsum)

CumObj(n) = obj_val(nsum)

F_val(mn + 1) = obj_val(nsum)

index = nsum

lastint = permutation(n)

Results.Text = Results.Text & vbCrLf & "====================================================" & vbCrLf

Results.Text = Results.Text & "Ind" & vbTab & "2^(n - 1)" & vbTab & "ObjF" & vbTab & "Last Added" & vbCrLf

Results.Text = Results.Text & Str$(index) & vbTab & Str$(nsum) & vbTab & Str$(obj_val(index)) & vbTab & Str$(last_added(index)) & vbCrLf

For i = 1 To n - 1

p = power(2, lastint - 1)

index = index - p

lastint = last_added(index)

permutation(n - i) = lastint

CumObj(n - i) = obj_val(index)

Results.Text = Results.Text & Str$(index) & vbTab & Str$(p) & vbTab & Str$(obj_val(index)) & vbTab & Str$(last_added(index)) & vbCrLf

Next i

Function Power(x, y)

Power = 1 For i = 1 To x

'Note: If x=0, then Power=1. Power = Power * y

next i

End Function

 

.::Home : Monograph Programs::.