1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
package permutation type TPermutation map[int]int // create a permutation structure func NewPermutation(n int) TPermutation { p := make(map[int]int,n) for i:=1; i<=n; i++ { p[i] = i } return p } // a print function that surpresses the map indices func (p *TPermutation) Println() { for i := 1; i <= len(*p); i++ { print((*p)[i]," ") } println() } // check if the permutation struct contains a specific value func (p *TPermutation) contains(n int) bool { for _, v := range *p { if v == n { return true } } return false } // calculate the next permutation // return false, if the next permutation is the last one // otherwise return true func (p *TPermutation) Next() bool { for marker := len(*p)-1; marker >= 1; marker -- { if (*p)[marker] < (*p)[marker+1] { // clear right of marker for i := marker+1; i <= len(*p); i++ { (*p)[i] = 0 } // increase marker for i := (*p)[marker]; i <= len(*p); i++ { if ! p.contains(i) { (*p)[marker] = i goto done1 } } done1: // add not contained for j := marker+1; j <= len(*p); j++ { for n := 1; n <= len(*p); n++ { if ! p.contains(n) { (*p)[j] = n goto done2 } } done2: } return true } } return false } |