|
| 1 | +package main |
| 2 | + |
| 3 | +import ( |
| 4 | + "fmt" |
| 5 | + "sort" |
| 6 | +) |
| 7 | + |
| 8 | +/**************************************************************************** |
| 9 | +Generates permutations of sortable sequence changing it in place. |
| 10 | +****************************************************************************/ |
| 11 | + |
| 12 | +// PermutationsIter returns a closure, each call to the returned function |
| 13 | +// generates the next permutations of the sequence (changing it in place). |
| 14 | +// Uses Non-recursive lexicographic order (Knuth's L-Algorithm), thus |
| 15 | +// the sequence passed as argument must be sortable. |
| 16 | +func PermutationsIter(a sort.Interface) func() bool { |
| 17 | + current := int64(0) |
| 18 | + n := a.Len() |
| 19 | + return func() bool { |
| 20 | + if current == 0 { |
| 21 | + sort.Sort(a) |
| 22 | + current++ |
| 23 | + return true |
| 24 | + } |
| 25 | + // Find largest index k such that a[k] < a[k + 1] |
| 26 | + k := -1 |
| 27 | + for j := n - 2; j >= 0; j-- { |
| 28 | + if a.Less(j, j+1) { |
| 29 | + k = j |
| 30 | + break |
| 31 | + } |
| 32 | + } |
| 33 | + if k == -1 { // if k not found, all done |
| 34 | + return false |
| 35 | + } |
| 36 | + // Find largest index l greater than k such that a[k] < a[l] |
| 37 | + l := -1 |
| 38 | + for j := n - 1; j >= k+1; j-- { |
| 39 | + if a.Less(k, j) { |
| 40 | + l = j |
| 41 | + break |
| 42 | + } |
| 43 | + } |
| 44 | + // swap a[k] <-> a[l] |
| 45 | + a.Swap(k, l) |
| 46 | + // Reverse a[k+1:n] |
| 47 | + for i, j := k+1, n-1; i < j; i, j = i+1, j-1 { |
| 48 | + a.Swap(i, j) |
| 49 | + } |
| 50 | + current++ |
| 51 | + return true |
| 52 | + } |
| 53 | +} |
| 54 | + |
| 55 | +/*************** Create a sortable type ***************/ |
| 56 | + |
| 57 | +// MyPermSeq satisfy interface sort.Interface |
| 58 | +type MyPermSeq []byte |
| 59 | + |
| 60 | +// Len of the sequence |
| 61 | +func (ps MyPermSeq) Len() int { |
| 62 | + return len(ps) |
| 63 | +} |
| 64 | + |
| 65 | +// Less implements < |
| 66 | +func (ps MyPermSeq) Less(i, j int) bool { |
| 67 | + return ps[i] < ps[j] |
| 68 | +} |
| 69 | + |
| 70 | +// Swap in place |
| 71 | +func (ps MyPermSeq) Swap(i, j int) { |
| 72 | + ps[i], ps[j] = ps[j], ps[i] |
| 73 | +} |
| 74 | + |
| 75 | +func main() { |
| 76 | + |
| 77 | + // Let's permutate ABCD in-place: output will be ordered in lexicographical order |
| 78 | + mySeq := MyPermSeq([]byte("ABCD")) |
| 79 | + next := PermutationsIter(mySeq) |
| 80 | + fmt.Println("Generating permutations for", string(mySeq), ": ") |
| 81 | + for next() { |
| 82 | + fmt.Print(string(mySeq), " ") |
| 83 | + } |
| 84 | + fmt.Println("") |
| 85 | + |
| 86 | + // Let's permutate ABBB in-place: shows algorithm handles repeated elements well |
| 87 | + mySeq = MyPermSeq([]byte("ABBB")) |
| 88 | + next = PermutationsIter(mySeq) |
| 89 | + fmt.Println("Generating permutations for", string(mySeq), ": ") |
| 90 | + for next() { |
| 91 | + fmt.Print(string(mySeq), " ") |
| 92 | + } |
| 93 | + fmt.Println("") |
| 94 | + |
| 95 | +} |
0 commit comments