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:
- Combination with Repetitions: choose
k
from n
: "get me three arbitrary drinks from five, please" - Combination without Repetition: choose
k
from n
: "get me three different drinks" - Variation with Repetitions: choose
k
from n
: "get me Margherita, then Gin-Tonic, then Margherita again" - 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:
- 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", - 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
3 Do
4 For n = resultSet(ubound) To nMax
5 resultSet(ubound) = n
6 Yield resultSet.ToArray
7 Next
8 For iPivot = ubound To 0 Step -1
9 If resultSet(iPivot) >= nMax Then resultSet(iPivot) = 0 Else Exit For
10 Next
11 If iPivot < 0 Then Return
12
13 resultSet(iPivot) += 1
14 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 ubound = chooseK - 1, nMax = fromN - 1, iPivot = 0
2 Dim resultSet = Enumerable.Repeat(0, chooseK).ToArray
3 Do
4 For n = resultSet(ubound) To nMax
5 resultSet(ubound) = n
6 Yield resultSet.ToArray
7 Next
8 For iPivot = ubound - 1 To 0 Step -1
9 If resultSet(iPivot) < nMax Then Exit For
10 Next
11 If iPivot < 0 Then Return
12
13 Dim pivotValue = resultSet(iPivot) + 1
14 For i = iPivot To ubound
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.
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 ubound = chooseK - 1, nMax = fromN - 1, iPivot = 0
2 Dim resultSet = Enumerable.Range(0, chooseK).ToArray
3 Do
4 For n = resultSet(ubound) To nMax
5 resultSet(ubound) = n
6 Yield resultSet.ToArray
7 Next
8
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
13
14 Dim diff = resultSet(iPivot) + 1 - iPivot
15 For i = iPivot To ubound
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.
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
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
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.