permute.go (1009B)
1 // Copyright (c) 2014 The mathutil Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 package mathutil // import "modernc.org/mathutil" 6 7 import ( 8 "sort" 9 ) 10 11 // PermutationFirst generates the first permutation of data. 12 func PermutationFirst(data sort.Interface) { 13 sort.Sort(data) 14 } 15 16 // PermutationNext generates the next permutation of data if possible and 17 // return true. Return false if there is no more permutation left. Based on 18 // the algorithm described here: 19 // http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order 20 func PermutationNext(data sort.Interface) bool { 21 var k, l int 22 for k = data.Len() - 2; ; k-- { // 1. 23 if k < 0 { 24 return false 25 } 26 27 if data.Less(k, k+1) { 28 break 29 } 30 } 31 for l = data.Len() - 1; !data.Less(k, l); l-- { // 2. 32 } 33 data.Swap(k, l) // 3. 34 for i, j := k+1, data.Len()-1; i < j; i++ { // 4. 35 data.Swap(i, j) 36 j-- 37 } 38 return true 39 }