source: code/trunk/vendor/modernc.org/mathutil/permute.go@ 823

// Copyright (c) 2014 The mathutil Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package mathutil // import "modernc.org/mathutil"

import (
        "sort"
)

// PermutationFirst generates the first permutation of data.
func PermutationFirst(data sort.Interface) {
        sort.Sort(data)
}

// PermutationNext generates the next permutation of data if possible and
// return true.  Return false if there is no more permutation left.  Based on
// the algorithm described here:
// http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
func PermutationNext(data sort.Interface) bool {
        var k, l int
        for k = data.Len() - 2; ; k-- { // 1.
                if k < 0 {
                        return false
                }

                if data.Less(k, k+1) {
                        break
                }
        }
        for l = data.Len() - 1; !data.Less(k, l); l-- { // 2.
        }
        data.Swap(k, l)                             // 3.
        for i, j := k+1, data.Len()-1; i < j; i++ { // 4.
                data.Swap(i, j)
                j--
        }
        return true
}