Golang中生成指定长度切片排列的方法

Golang中生成指定长度切片排列的方法 正在尝试找出如何生成特定长度的切片排列。例如在Python中，我可以这样做：

>>> import itertools
>>> l = list(itertools.permutations(range(1, 4), 2))
>>> print(l)
[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

在Go中实现这一目标的最佳方法是什么？我一直在这里寻找一个能给出所有排列的解决方案，但不知道如何指定长度。此外，对于较大的切片，这会迅速消耗资源。


更多关于Golang中生成指定长度切片排列的方法的实战教程也可以访问 https://www.itying.com/category-94-b0.html

2 回复

我去年做了些处理这个问题的东西：https://github.com/skillian/itertools/blob/master/permutation_test.go

编辑：我不确定我是否会再次用同样的方式做，但我认为很多技术仍然适用。

更多关于Golang中生成指定长度切片排列的方法的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


在Go中生成指定长度的切片排列，可以使用递归回溯算法。以下是一个高效实现，支持指定排列长度：

package main

import "fmt"

func permutations(arr []int, length int) [][]int {
    var result [][]int
    var backtrack func([]int, []bool)
    
    backtrack = func(current []int, used []bool) {
        if len(current) == length {
            // 复制当前排列到结果
            temp := make([]int, length)
            copy(temp, current)
            result = append(result, temp)
            return
        }
        
        for i := 0; i < len(arr); i++ {
            if used[i] {
                continue
            }
            used[i] = true
            backtrack(append(current, arr[i]), used)
            used[i] = false
        }
    }
    
    backtrack([]int{}, make([]bool, len(arr)))
    return result
}

func main() {
    // 示例：生成[1,2,3]的长度为2的排列
    arr := []int{1, 2, 3}
    perms := permutations(arr, 2)
    
    for _, p := range perms {
        fmt.Println(p)
    }
    // 输出：
    // [1 2]
    // [1 3]
    // [2 1]
    // [2 3]
    // [3 1]
    // [3 2]
}

对于更大的切片，可以使用迭代器和通道来减少内存消耗：

func permutationsChan(arr []int, length int) <-chan []int {
    ch := make(chan []int)
    
    go func() {
        defer close(ch)
        used := make([]bool, len(arr))
        backtrackChan(arr, length, []int{}, used, ch)
    }()
    
    return ch
}

func backtrackChan(arr []int, length int, current []int, used []bool, ch chan<- []int) {
    if len(current) == length {
        temp := make([]int, length)
        copy(temp, current)
        ch <- temp
        return
    }
    
    for i := 0; i < len(arr); i++ {
        if used[i] {
            continue
        }
        used[i] = true
        backtrackChan(arr, length, append(current, arr[i]), used, ch)
        used[i] = false
    }
}

// 使用示例
func main() {
    arr := []int{1, 2, 3, 4}
    for perm := range permutationsChan(arr, 3) {
        fmt.Println(perm)
    }
}

对于通用类型，可以使用泛型实现：

func Permutations[T any](arr []T, length int) [][]T {
    var result [][]T
    used := make([]bool, len(arr))
    
    var backtrack func([]T)
    backtrack = func(current []T) {
        if len(current) == length {
            temp := make([]T, length)
            copy(temp, current)
            result = append(result, temp)
            return
        }
        
        for i := 0; i < len(arr); i++ {
            if used[i] {
                continue
            }
            used[i] = true
            backtrack(append(current, arr[i]))
            used[i] = false
        }
    }
    
    backtrack([]T{})
    return result
}

// 使用示例
func main() {
    strArr := []string{"a", "b", "c"}
    strPerms := Permutations(strArr, 2)
    fmt.Println(strPerms) // [[a b] [a c] [b a] [b c] [c a] [c b]]
}

这些实现通过回溯算法生成指定长度的排列，第一个示例最直接，第二个使用通道适合大数据集，第三个泛型版本支持任意类型。

回到顶部