应用处理程序的排列，没有缓存的水平?

我想写一个函数，将给定的处理程序应用于输入的所有排列，而不返回整个排列。

(ingo)

找到排列:

// apply given handler on each combination, and return count only,
func FindAllPermutationApplyHandler[T any](ts []T, handler func([]T)) int {
n := 0
combList := [][]T{{}} // when empty input, has 1 empty combination, not 0 combination,
for i := len(ts) - 1; i >= 0; i-- {
isLastLevel := false
if i == 0 {
isLastLevel = true
}
// prefix := ts[0:i]
mover := ts[i]
// fmt.Printf("nprefix = %v, mover = %v:n", prefix, mover)
var combList2 [][]T // combinations with an extra item added,
for _, comb := range combList {
for j := 0; j <= len(comb); j++ { // insert mover at index j of comb,
comb2 := append(append(append([]T{}, comb[0:j]...), mover), comb[j:]...) // new_empty + left + mover + right
if isLastLevel {
n++
handler(comb2)
} else {
combList2 = append(combList2, comb2)
}
}
}
combList = combList2
}
return n
}

测试案例(简单):

func TestFindAllPermutationApplyHandler(t *testing.T) {
assert.Equal(t, FindAllPermutationApplyHandler([]int{1, 2, 3}, func(comb []int) {
fmt.Printf("t%vn", comb)
}), 6)
}

解释

上述函数FindAllPermutationApplyHandler()可以找到排列，并对每个组合应用给定的handler。
它需要缓存以前的n-1级别(最近的2个级别同时)。
我已经避免了final的缓存水平，因为没有更多的水平取决于它。

问题

1. 是否有可能避免最近2个级别的缓存?
  (即。使空间复杂性O(1)或O(n)，甚至O(n^2)更好，我想)。
1. 但这对我来说似乎是不可能的，因为i级别是基于i-1级别的，对吧?
1. 如果是，是否有更好的算法来降低空间复杂度?优选迭代(优于递归)。

听起来你在找Pandita的算法

这是一种按字典顺序迭代生成数组所有排列的简单方法。

但是，要求可以对数组中的元素排序。如果您不能(因为它们是泛型类型)，那么您可以为所有数组索引创建二级数组，并生成该数组的排列。

根据Matt Timmermans的回答，我实现了Pandita's algorithm，这是无缓存,顺序.

(ingo)

查找排列，按顺序:

package permutation_util
import (
"fmt"
"golang.org/x/exp/constraints"
"golang.org/x/exp/slices"
)
// will sort first, in default order,
func FindAllPermutationInOrderApplyHandlerDefaultSort[T constraints.Ordered](ts []T, handler func(ts []T, isComb []int)) int {
return FindAllPermutationInOrderApplyHandlerCustomizedSort(ts, handler, nil)
}
// sort reversely,
func FindAllPermutationInOrderApplyHandlerReversedSort[T constraints.Ordered](ts []T, handler func(ts []T, isComb []int)) int {
return FindAllPermutationInOrderApplyHandlerCustomizedSort(ts, handler, func(a, b T) bool {
return a > b // reversed,
})
}
// sort by given compare function,
func FindAllPermutationInOrderApplyHandlerCustomizedSort[T constraints.Ordered](ts []T, handler func(ts []T, isComb []int), less func(a, b T) bool) int {
if less != nil {
slices.SortFunc(ts, less)
} else {
slices.Sort(ts)
}
return FindAllPermutationInOrderApplyHandlerNoSort(ts, handler)
}
// find all permutation of []T, in order, using Pandita's algorithm,
// ts should be already sorted, in the order you wish,
// apply given handler on each combination, and return count only,
// repeated elements: it also handle the case with repeated elements, aka. it won't generate repeated combination,
// refer:   https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
func FindAllPermutationInOrderApplyHandlerNoSort[T constraints.Ordered](ts []T, handler func(ts []T, isComb []int)) int {
is := genInitialIs(ts)
fmt.Printf("initial order: %vn", is)
n := 1 // include initial combination,
handler(ts, is)
size := len(ts)
for {
var k int
for k = size - 2; ; k-- { // find k,
if k < 0 { // done
return n
}
if is[k] < is[k+1] {
n++
break
}
}
valueK := is[k]
var l int
for l = size - 1; ; l-- { // find l,
if is[l] > valueK {
break
}
}
is[k], is[l] = is[l], is[k] // swap k & l,
sc := (size - 1 - k) >> 1
maxLeft := k + sc
for left, right := k+1, size-1; left <= maxLeft; left, right = left+1, right-1 { // reverse is[k+1:],
is[left], is[right] = is[right], is[left]
}
handler(ts, is)
}
}
// generate initial index, and handle repeated elements, to avoid repeated combination,
// e.g [7 11 11 13] -> [0 1 1 3]
func genInitialIs[T constraints.Ordered](ts []T) []int {
size := len(ts)
is := make([]int, size)
for i, ir := 0, 0; i < size; i++ { // generation initial order,
if i == 0 || ts[i] != ts[i-1] {
ir = i
}
is[i] = ir
}
return is
}

测试用例:

package permutation_util
import (
"fmt"
"github.com/stretchr/testify/assert"
"golang.org/x/exp/constraints"
"testing"
)
// default order
func Test_FindAllPermutationInOrderApplyHandlerDefaultSort(t *testing.T) {
runOnce_FindAllPermutationInOrderApplyHandlerDefaultSort_print(t, []int{0, 1, 2}, 6)
// input not ordered,
runOnce_FindAllPermutationInOrderApplyHandlerDefaultSort_print(t, []int{1, 2, 0}, 6)
/* corner */
// empty
runOnce_FindAllPermutationInOrderApplyHandlerDefaultSort_print(t, []int{}, 1)
// 1
runOnce_FindAllPermutationInOrderApplyHandlerDefaultSort_print(t, []int{0}, 1)
}
func Test_FindAllPermutationInOrderApplyHandlerDefaultSort_RepeatedEle(t *testing.T) {
runOnce_FindAllPermutationInOrderApplyHandlerDefaultSort_print(t, []int{0, 1, 2, 2}, 12)           // A(4) / a(2)
runOnce_FindAllPermutationInOrderApplyHandlerDefaultSort_print(t, []int{0, 1, 2, 2, 2}, 20)        // A(5) / a(3)
runOnce_FindAllPermutationInOrderApplyHandlerDefaultSort_print(t, []int{0, 1, 2, 2, 2, 3, 3}, 420) // A(7) / (A(3) * A(2))
runOnce_FindAllPermutationInOrderApplyHandlerDefaultSort_print(t, []int{11, 13, 7, 11}, 12) // A(4) / a(2)
}
func runOnce_FindAllPermutationInOrderApplyHandlerDefaultSort_print[T constraints.Ordered](t *testing.T, ts []T, expectedN int) {
fmt.Printf("n%v:n", ts)
assert.Equal(t, FindAllPermutationInOrderApplyHandlerDefaultSort(ts, func(ts []T, isComb []int) {
tsComb := make([]T, len(ts))
for i := 0; i < len(ts); i++ {
tsComb[i] = ts[isComb[i]]
}
fmt.Printf("t%vn", tsComb)
}), expectedN)
}
// reversed order,
func TestFindAllPermutationInOrderApplyHandler_reversed(t *testing.T) {
runOnce_FindAllPermutationInOrderApplyHandlerCustomizedSort_reversedPrint(t, []int{0, 1, 2}, 6)
}
func runOnce_FindAllPermutationInOrderApplyHandlerCustomizedSort_reversedPrint[T constraints.Ordered](t *testing.T, ts []T, expectedN int) {
fmt.Printf("n%v:n", ts)
assert.Equal(t, FindAllPermutationInOrderApplyHandlerReversedSort(ts, func(ts []T, isComb []int) {
tsComb := make([]T, len(ts))
for i := 0; i < len(ts); i++ {
tsComb[i] = ts[isComb[i]]
}
fmt.Printf("t%vn", tsComb)
}), expectedN)
}

复杂性时间

:O(n!)或O(n! * n)//TODO:不确定，
维基百科说:3 comparisons and 1.5 swaps per permutation
:O(1)
自从它改变了位置。

重复元素它还处理重复元素的情况，即。不会产生重复的组合

要计算出总数，对于每一个重复组，应除以A(group's size)，公式:

A(n)/(A(r1) * A(r2) *…* (rx))

相关内容

最新更新

热门标签：