13,803,704 members
alternative version

#### Stats

9.4K views
12 bookmarked
Posted 11 Jul 2016
Licenced CPOL

# Permutations

, 11 Jul 2016
understandeable, short and fast code

## The general Formula

Maths sais: "choose `k` elements from `n` different options" - that defines a combinatoric operation.
Additional there is a rule - whether you can choose the same option twice or not (Repetitions),
and a comparison - whether the order of the single choices makes a difference or not (Respect Order).

In the latter case - Respect Order - the operation is called "Variation" - otherwise it's a "Combination".

### So there come up these four:

1. Combination with Repetitions: choose `k` from `n`: "get me three arbitrary drinks from five, please"
2. Combination without Repetition: choose `k` from `n`: "get me three different drinks"
3. Variation with Repetitions: choose `k` from `n`: "get me Margherita, then Gin-Tonic, then Margherita again"
4. Variation without Repetition: choose `k` from `n`: "get me Margherita, then Gin-Tonic, then Bloody Mary"

### The special and the very special case

If we vary without Repetition: choose `all` from `n` ( a special case of 4. in the above list ), this is called also "Permutation", in the specific maths-meaning.

But especially Permutations can become very special: (Only) for Permutations Repetitions may occur in the Source-Option-Set! :wtf:
permutate me! ;)

Note the Paradox: As "Variation without Repetition" Repetitions are not allowed. But for Permutations in specific they are allowed, as long as they replicate Source-Option-Set-Repetitions.

This exception in combinatoric-definitions wasn't arbitrarily made, but is derived from real-world-problems:

• Imagine you want vary the (known) letters of a password, and they include doubles.
• Or lastly a musician was interested in all rythms, buildable from a given set of beat-durations.
• Or just play Scrabble! ;)

## Try out them all

As programmers we have the natural urge to try out all possibilities, (of course only in virtual ;) ), and for that we need appropriate Algorithms.

### Lexicographic Order - the cruicial concept

On each position the elements get compared, and the first occurance of a difference determines which elementSet is seen as later than the other.
eg `{3, 5, 2, 6}` is earlyer than  `{3, 5, 3, 0}` because of the difference at 3rd position.

The lexicographic minimal Variation of the left Set is `{2, 3, 5, 6}`, and it is `{2, 2, 2, 2}` if Repetitions are allowed.

You can increment the lexicographic rank for exact one step, when you increment the last Element.
Eg. `{3, 5, 2, 6}` -> `{3, 5, 2, 7}`

Smart combinatoric Algorithms run from the lexicographic Minimum to Maximum, and also apply that point of view to subsets of the sequence.

## The Code

You can imagine the "Permutator" as a mechanical counter, or a Number-Lock, with `k` digits, and each digit has `n `options.
In my system I understand the general Algo as divided in two parts, executed alternating:

1. Count up the last digit to the charsets upperbound (`n`) - each change causes an output of a different resultSet.
When Upperbound is reached the digits are "exhausted",
2. The second Algo-Part is "to regenerate" them - means: find the next lexicographic rank by incrementing an earlier digit, and reset the range behind it to lexicographic minimum.

While the Output-Part always is the same, the regeneration-part differs, according to the combinatoric conditions (order_respecting, repetition_validity)

Variation with Repetitions:

```  1  Dim resultSet = Enumerable.Repeat(0, chooseK).ToArray
2  Do
3     For n = resultSet(ubound) To nMax ' output-loop
4        resultSet(ubound) = n
5        Yield resultSet.ToArray
6     Next
7     For iPivot = ubound To 0 Step -1 ' find incrementable position, set others to 0
8        If resultSet(iPivot) >= nMax Then resultSet(iPivot) = 0 Else Exit For ' pivot: smaller than nMax
9     Next
10     If iPivot < 0 Then Return
11     resultSet(iPivot) += 1
12  Loop
```

Line #1 inits the resultSet with `k 0`s - the lexicographic Minimum, when Repetitions are valid.
#3 starts the output-loop: the last digit counts up, and each loop yields a result
#7 begins "regenerating": First a backwards-loop, searching the "pivot-element".
#8 says the pivot-condition: `Exit For` if element `< nMax`. Otherwise set the element to `0`
#10 terminates the algo, if no pivot could be found
#11 Since the backward-search already has "regenerated" the range behind pivot (with `0`s), there is only left to increment the pivot-element itself.
Now on the left of pivot the lexicographic rank is incremented exact one step, and on the right its all set to `0` - the lexicographic Minimum. Thus means, the whole sequence has incremented to the exact next lexicographic rank. And now it's ready for the next output-loop-cycle.

Combination with Repetitions:

```  1  Dim resultSet = Enumerable.Repeat(0, chooseK).ToArray ' init resultSet with 0
2  Do
3     For n = resultSet(ubound) To nMax ' output-loop
4        resultSet(ubound) = n
5        Yield resultSet.ToArray
6     Next
7     For iPivot = ubound - 1 To 0 Step -1 ' find incrementable position
8        If resultSet(iPivot) < nMax Then Exit For ' pivot-element must be smaller than nMax
9     Next
10     If iPivot < 0 Then Return
11     Dim pivotValue = resultSet(iPivot) + 1
12     For i = iPivot To ubound         ' fill resultSet after pivot with same pivotValue
13        resultSet(i) = pivotValue
14     Next
15  Loop
```

Combination_R is allmost identic to Variation_R, the first 10 lines!
Then, line #11: get the `pivotValue `and increment it
#12: the loop assigns that pivotValue to all positions from `iPivot` on.
That is how an "exhausted" Combination_R migrates to the next lexicographic position.

The difference between Combination_R and Variation_R: Variation regenerates with `0`, while Combination regenerates with the incremented `pivotValue`.
The reason is, that the sukzessive order, in which combinations are generated, ensures, that all options with smaller Values already are permutated through.

Variation Combination
Variations and Combinations with Repetitions: "choose 3 from 5"
```000 001 002 003 004
010 011 012 013 014
020 021 022 023 024
030 031 032 033 034
040 041 042 043 044
100 101 102 103 104
110 111 112 113 114
120 121 122 123 124
130 131 132 133 134
140 141 142 143 144
200 201 202 203 204
210 211 212 213 214
220 221 222 223 224
230 231 232 233 234
240 241 242 243 244
300 301 302 303 304
310 311 312 313 314
320 321 322 323 324
330 331 332 333 334
340 341 342 343 344
400 401 402 403 404
410 411 412 413 414
420 421 422 423 424
430 431 432 433 434
440 441 442 443 444```
```000 001 002 003 004
011 012 013 014
022 023 024
033 034
044
111 112 113 114
122 123 124
133 134
144
222 223 224
233 234
244
333 334
344
444```

Meditate a bit over the left table and about what really happens, when your child has learned counting upto 100:
namely "vary with repititions: choose 2 from 10, in lexicographic order".
On the right you see shrinking threeangles of choices, each "using up one digit": First Threeangle consumes `0`, second `1`, upto the fifths, for which is left only one single value: `444`.

Combination without Repetiton

```  1  Dim resultSet = Enumerable.Range(0, chooseK).ToArray ' init resultSet with ascending sequence
2  Do
3     For n = resultSet(ubound) To nMax
4        resultSet(ubound) = n
5        Yield resultSet.ToArray
6     Next
7     ' find incrementable pivot-element: must have a gap to its successor
8     For iPivot = ubound - 1 To 0 Step -1
9        If resultSet(iPivot) < resultSet(iPivot + 1) - 1 Then Exit For
10     Next
11     If iPivot < 0 Then Return ' possibly terminate
12     ' "regeneration"
13     Dim diff = resultSet(iPivot) + 1 - iPivot ' difference between pivotValue and its index
14     For i = iPivot To ubound     ' fill resultSet from pivot on with ascending sequence
15        resultSet(i) = i + diff
16     Next
17  Loop
```

The lexicographic minimum of a sequence without Repetition is an ascending sequence.
And the condition to match a pivot-value (line #9) is, if there is a gap to its successor.
(To explain "gap": On `123` incrementing the `1` would cause a (invalid) Repetition, but on `134` it can (because of the gap between `1` and `3`)).
And also the "regenerating" is more complex - the range from iPivot on must be filled with an ascending sequence, starting with the incremented pivotValue (line #14 ff)

Variation without Repetition

This cannot be achieved with my "alternate output-regeneration"-algo. Here we need Help from the lexicographic Permutation-Algo as described by Dijkstra.
I first show the "helped" algo:

```For Each result In ChooseKfromN(chooseK, fromN, CombinatoricMode.Combination_NoRepetition)
For Each perm In Permutation(result)
Yield perm
Next
Next```

You see: It calls the other algo - Combination without Repetition - and permutates eaches of its result.

Combination Variation
Combinations and Variations without Repetitions: choose 3 from 5
```012
013
014
023
024
034
123
124
134
234 ```
```012 021 102 120 201 210
013 031 103 130 301 310
014 041 104 140 401 410
023 032 203 230 302 320
024 042 204 240 402 420
034 043 304 340 403 430
123 132 213 231 312 321
124 142 214 241 412 421
134 143 314 341 413 431
234 243 324 342 423 432```

Note, that each line on the right is the complete permutation of the three digits of the left.

Lexicographic Permutation as described by Dijkstra

Remember: Permutation was generally defined as "Variation without Repetition: choose all from `n`". A more specific definition is not to define `n`, the number of different options, but to pass the options themselves to the Algo. This because of the Permutations "special-feature": that the Options (not only the results) can have Repetitions!
Code:

```  1  Dim perm = sortedElements.ToArray()
2  Dim ubound = perm.Length - 1
3  Dim pivot, iPivot As Integer
4  Do
5     Yield perm.ToArray()
6     For iPivot = ubound - 1 To 0 Step -1
7        pivot = perm(iPivot)
8        If pivot < perm(iPivot + 1) Then Exit For
9     Next
10     If iPivot < 0 Then Return
11     Dim iSwap = Array.FindLastIndex(perm, Function(p) p > pivot)
12     perm(iPivot) = perm(iSwap)
13     perm(iSwap) = pivot
14     Array.Reverse(perm, iPivot + 1, ubound - iPivot)
15  Loop
```

Line #1: initiate perm with the sorted option-array
#5: output one result
#6 - #9: search `pivot`, which must be smaller than its successor, #10: possibly terminate
#11: but now - search a swap-candidate, as the last one, which is bigger than `pivot`!
#12, #13: swap them.
Note: this swapping does not change the descending order of the range after pivot!
#14: reverse the array-range after pivot.
Now that range is ordered ascending, and it's the same story: the (pivot-including) left side has incremented exact one lexicographic step while the right resetted to its lexicographic minimum.

The Algo looks complicated, but is very fast: For instance every second loop the first search-step matches immediately. You can optimize, eg. omit `Array.Reverse()` when the range is of length of 1 (which occurs every second loop).
But that are Micro-Optimizations. The performance-bottle-neck is, that each result must be cloned, to avoid side-effects. And when cloning a small Array is a "bottleneck", you can imagine: That algo propably will be fast enough for allmost every use-case.

Output: Permutate `12334` (note the sortation, and note the double `3`)

```12334 12343 12433 13234 13243 13324 13342 13423 13432 14233 14323 14332
21334 21343 21433 23134 23143 23314 23341 23413 23431 24133 24313 24331
31234 31243 31324 31342 31423 31432 32134 32143 32314 32341 32413 32431
33124 33142 33214 33241 33412 33421 34123 34132 34213 34231 34312 34321
41233 41323 41332 42133 42313 42331 43123 43132 43213 43231 43312 43321```

You can see the correct sort-order, and of course the last element is the inversion of the first.

## Make it generic

This is quite simple: Just take the numbers as Indicees of a generic `List(Of T)`, or an Array of the DataType you want - here a Sample with Strings:

```  1  Private Sub PermutateWords()
2     Dim words = _rgxWords.Split(txtInput.Text.Trim())
3     Dim sb = New StringBuilder()
4     For Each result In Combinatorics.Permutation(Enumerable.Range(0, words.Length))
5       sb.AppendLine(String.Join(" ", result.Select(Function(i) words(i))))
6     Next
7     txtOutput.Text = sb.ToString
8  End Sub
```

Line#2: get the words.
#4: permutate an Integer-Sequence of `words.Length` length.
#5: select each result-Integer as Index to access one of the `words`.

##### Update: With doubles in the source-set a bit more tricky

Meridas pointed out a bug in the attached sources, when Doubles occur in the word-input.
Because then the word-list and the indicees must be prepared a bit more than as shown above.
For instance the input: `one two three two four`

must lead to indicees as: `0 1 1 2 3`
and Words as: `one two three four`

Means: Words must be distinct, while indicees replicate the Doubles, and contain them in the order of lexicographic minimum.
See fixed code (hopefully you are familliar with linq-Grouping-technique):

```  1  Private Sub PermutateWords()
2  	Dim words = _rgxWords.Split(txtInput.Text.Trim)
3  	Dim wordCounts = From w In words Group By w Into Count() Select Count
4      Dim indicees = wordCounts.SelectMany(Function(cnt, i) Enumerable.Repeat(i, cnt))
5  	Dim distinctWords = words.Distinct.ToArray
6  	Dim sb = New StringBuilder()
7  	For Each result In Combinatorics.Permutation(indicees)
8  		sb.AppendLine(String.Join(" ", result.Select(Function(i) distinctWords(i))))
9  	Next
10     txtOutput.Text = sb.ToString
11  End Sub
```

## The Sample-Application

The images of the coctails in this Article are taken as they were, from german Wikipedia, where they were licensed under several similary creative common - licenses.

For that I re-publish them under an equivalent license, namely under CC BY-SA A 3.0

## Share

 Germany
No Biography provided

## You may also be interested in...

 First Prev Next
 Question about Permutation with Repetition meridas9-Feb-18 0:56 meridas 9-Feb-18 0:56
 Re: Question about Permutation with Repetition Mr.PoorEnglish23-Apr-18 9:43 Mr.PoorEnglish 23-Apr-18 9:43
 very useful for me !!! tks alot !!! Member 1004987122-Jun-17 8:29 Member 10049871 22-Jun-17 8:29
 My vote of 4 Jimmy_Olano12-Jul-16 14:06 Jimmy_Olano 12-Jul-16 14:06
 Re: My vote of 4 Mr.PoorEnglish16-Jul-16 2:33 Mr.PoorEnglish 16-Jul-16 2:33
 Last Visit: 18-Dec-18 14:15     Last Update: 18-Dec-18 14:15 Refresh 1