Permutations

Download Permutation.zip (contains c# + vb.net)

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 ubound = chooseK - 1, nMax = fromN - 1, iPivot = 0
  2  Dim resultSet = Enumerable.Repeat(0, chooseK).ToArray ' init resultSet with 0
  3  Do
  4     For n = resultSet(ubound) To nMax ' output-loop
  5        resultSet(ubound) = n
  6        Yield resultSet.ToArray
  7     Next
  8     For iPivot = ubound To 0 Step -1 ' find incrementable position, set others to 0
  9        If resultSet(iPivot) >= nMax Then resultSet(iPivot) = 0 Else Exit For ' pivot: smaller than nMax
 10     Next
 11     If iPivot < 0 Then Return ' possibly terminate
 12     ' "regeneration": values after iPivot are already 0
 13     resultSet(iPivot) += 1
 14  Loop

Line #1 inits the resultSet with k 0s - 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 0s), 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 ubound = chooseK - 1, nMax = fromN - 1, iPivot = 0
  2  Dim resultSet = Enumerable.Repeat(0, chooseK).ToArray ' init resultSet with 0
  3  Do
  4     For n = resultSet(ubound) To nMax ' output-loop
  5        resultSet(ubound) = n
  6        Yield resultSet.ToArray
  7     Next
  8     For iPivot = ubound - 1 To 0 Step -1 ' find incrementable position 
  9        If resultSet(iPivot) < nMax Then Exit For ' pivot-element must be smaller than nMax
 10     Next
 11     If iPivot < 0 Then Return ' possibly terminate
 12     ' "regeneration"
 13     Dim pivotValue = resultSet(iPivot) + 1
 14     For i = iPivot To ubound         ' fill resultSet after pivot with same pivotValue
 15        resultSet(i) = pivotValue
 16     Next
 17  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.

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

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

License-Note about the coctail-images

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