Search⌘ K
Home
Courses
Data Structures & Algorithms In Go

Solution Review: All Permutations of an Integer List

Explore how to generate all permutations of an integer list using recursive functions in Go. Understand the process of swapping elements and using base cases to achieve all possible orderings efficiently. This lesson reviews the recursive solution, including its logic and time complexity, enhancing your grasp of recursion and permutation algorithms.

We'll cover the following...

Solution

At each recursive call, we swap the number at index i with all the array elements on its right. We recursively repeat the process for sub-arrays until the sub-array of one element is left.

Let’s look at the illustration to better understand the solution before reviewing its code.

Coding exercise

Go (1.6.2)
package main
import("fmt")
func swap(x, y int) (int, int) {
    return y, x
}
func Permutation(data []int, i int, length int) { 
  if length == i {
        fmt.Printf("%v\n", data) 
        return
   }
    for j := i; j < length; j++ {
        data[i],data[j] = swap(data[i], data[j])
        Permutation(data, i+1, length)
        data[i],data[j] = swap(data[i], data[j])
    } 
}
//Testing code
func main() {
    var data [3]int
    for i := 0; i < 3; i++ {
        data[i] = i
      }
    Permutation(data[:], 0, 3)
}

Time complexity

The time complexity of the solution isO ...