Comment l'algorithme de Heap peut-il générer toutes les permutations en Go ?

Générer toutes les permutations dans Go

Introduction

Générer toutes les permutations possibles d'une liste de Les éléments sont un problème courant en programmation. Cet article explore l'algorithme de Heap, l'une des approches les plus simples pour générer toutes les permutations. Les permutations générées ne seront pas triées lexicographiquement.

Algorithme de Heap

L'algorithme de Heap génère chaque permutation en choisissant une paire d'éléments à échanger. Cela commence par un cas de base où le tableau ne contient qu'un seul élément. Pour les tableaux plus grands, il parcourt les éléments, en échangeant des paires pour générer de nouvelles permutations de manière récursive.

Implémentation Go

Vous trouverez ci-dessous une implémentation Go de l'algorithme de Heap :

func permutations(arr []int) [][]int {
    res := [][]int{}
    helper := func(arr []int, n int) {
        if n == 1 {
            tmp := make([]int, len(arr))
            copy(tmp, arr)
            res = append(res, tmp)
        } else {
            for i := 0; i < n; i++ {
                helper(arr, n-1)
                if n%2 == 1 {
                    tmp := arr[i]
                    arr[i] = arr[n-1]
                    arr[n-1] = tmp
                } else {
                    tmp := arr[0]
                    arr[0] = arr[n-1]
                    arr[n-1] = tmp
                }
            }
        }
    }
    helper(arr, len(arr))
    return res
}

Exemple d'utilisation

Ici est un exemple d'utilisation de la fonction de permutations :

arr := []int{1, 2, 3}
fmt.Println(permutations(arr))

Sortie

[[1 2 3] [2 1 3] [3 2 1] [2 3 1] [3 1 2] [1 3 2]]

Notes supplémentaires

• Les permutations sont générées mais non triées lexicographiquement.
• Pour tri lexicographique, pensez à utiliser un système de numération factorielle pour générer les permutations.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!