# Generating Permutations in Excel

Yesterday my brother was asking about generating permutations that could be used as an input to a project risking tool in Excel. It took me a little while to crack it (including some relatively fruitless Google searches 🙂 ) but the answer is really simple and elegant.

There are various uses for generating permutation runs–one of which I wrote a post on here about 6yrs ago! Mostly they are used for optimization problems. I had to dip into my stats book‘s first chapter to refresh my memory on ‘combinatorial methods’.

I wanted to find all possible sets of outcomes (call them runs) where there are 5 variables and 2 possible scenarios per variable (in this case the variables were oil_production, gas_production, capex, opex, abex; and the scenarios for each are low and high).

I started by drawing out the decision tree associated with the problem (see below).

Let’s refer to our variables as A,B,C,D,E and scenarios as 1 and 2. I realized that for each of the 2 possible outcomes of A, there are 2 possible outcomes for B (now, 4 combined possible outcomes). Then for each of those 4 outcomes, there are 2 possible outcomes for C (2*4=8 total outcomes). So I concluded that for x sets of y possible outcomes there are y^x potential runs.

### Getting Excel to write the Permutations

Now I needed to get Excel to write all these permutations (using VBA). The way I did this was to just use 5 (x=5 here, right) nested For-Next loops of 2 iterations (2 to 3 here) per loop with the output step located at the innermost loop.

The output is printed to the Immediate Window (Ctrl+G). But I have included the slightly altered file HERE that contains this code as well as some extra code to write the permutation runs to cells directly in Excel.

###### Excel Permutations Code (cut and paste to VBA Editor)
```Sub gpermuts() 'subroutine for generating all possible permutations of 5 sets of 2 outcomes
Dim v1, v2, v3, v4, v5 As Integer
For v1 = 2 To 3
For v2 = 2 To 3
For v3 = 2 To 3
For v4 = 2 To 3
For v5 = 2 To 3
Debug.Print v1, v2, v3, v4, v5
Next v5
Next v4
Next v3
Next v2
Next v1
End Sub```

# Mail-box route design

Having previously worked as a postal courier—and having often wondered if the senior management used any kind of cluster optimization model for designing pick-up routes—I once casually asked a friend (who has a Phd in mathematics from Berkeley) about the possibility of deriving an optimal route for emptying mail boxes and collecting office pick-up points. Probably because of the way I framed the problem he told me it was not possible and that it was essentially the “post-round” problem. But last year while studying probability and permutations I thought of a model that might work.

# A similar problem

In Provo I used to go and play “pick up” soccer (football) with the Latinos or whoever was playing. The problem was that there were a number of local areas where a game might be going on—and so if you weren’t in the know you just had to scout around until you found a game to join. Maybe I could have saved some time if I’d conceived of this model (below) earlier. Here’s what I have come up with. (I suppose similar models could be applied to various types of problems).

#### 1.      Think of all the locations and then map them to a matrix like the one below

Basically I just considered the driving times (in minutes) between all the locations where there may be a game going on that I could join. I have to start and finish at “home”. In this case it takes the same number of minutes to go from one place to the next in both directions (i.e. “home” to “rock canyon park” = “rock canyon park” to “home”). I’ve indexed each location with a number (1 – 7). In this case I always leave from home, and I’ll just say I always return to home (e.g. for a shower). So, I’ll always start at “1” and end at “1”. That leaves a string of six other locations I can scout out in any order I want. How many possible ways can I scout out these locations? Using probability theory’s function or Excel’s =PERMUT(6,6), I get 720 possible combinations. If I can generate a list of all the possible permutations—i.e. {1,2,3,4,5,6}, {1,2,3,4,6,5}, {1,2,3,5,4,6}… then I can link it to the matrix to find the shortest route.

#### 3.      Generate the permutations

The only way I found to do this efficiently is to use VBA code. The following code that I got from walkenbach’s site worked great here. What I got is a list of all 720 possible permutations for the numbers 2,3,4,5,6,7. The reason I used digits 2 – 7 is because 1=home, which is always starting and ending the sequence—so its position is always fixed in the sequence. The list is 720 rows long and looks like this: … and so on.

4.      Link each sequence to the time distance matrix (above)

The next thing to do is tack on the home element, creating an permutations array of all possible location sequences… … and then link each possible journey to the original distance matrix. To do this I used =VLOOKUP(location#1,initial matrix table,location#2+2,FALSE) to create another array to the right of the permutations array, where “location#1” is the first location in the permutations array and “location#2” is the subsequent location in the permutations array. To see how the formula works for the first cell in this new array consider the following screen shot from Excel: You can see that D13 is “home”, the table reference for VLOOKUP is the initial travel time matrix, and since what we want to refer to is the distance between the initial location (“home”) and the next location in the sequence (“2” or “hospital field”) we use E13+2 as the column reference. (The reason for the “+2” here is so that VLOOKUP refers to the correct corresponding column location reference—since it recognizes the first column in the selected [green] array as “1”).

#### 5.      Summing all possible travel routes

Dragging to the right and then down produces a series of calculations showing the distances between each stage of each corresponding permutation. All that is left to do now is sum these distances for each permutation to get a “total scouting time” metric for each scenario. You can then simply sort these (A – Z) to see which route is shortest.

#### 6.      Some complications

This is not an application where we necessarily need to visit every stop. Basically the goal is to find a game as quickly as possible—so perhaps when deciding on a route more weight should be allocated to the initial stops. This can be done by building a formula to the right that incorporates that consideration (I’ve done so here, where more weight is allocated to the time taken in the initial three stops than the subsequent ones—the result is a new metric to minimize). There may also be some locations that are better quality, or where there is a higher probability that people are playing there. So these things could be built in also or just considered intuitively. This technique could easily be replicated for other excel optimization problems.