Permutations

Print all the permutations of the given unique natural numbers.

Input Format

The fist line contains a single integer N denoting the amount of numbers.

The second line is a space-separated list of unique integers numbers.

Constraints:

  • 2 <= N <= 10

  • 0 <= numbers[i] <= 9

Output Format

The output should be a line-separated list of permutations. The order is not relevant.

Sample 00

input00.txt
2
0 1
output00.txt
0 1
1 0

Sample 01

input01.txt
3
1 2 3
output01.txt
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Sample 02

input02.txt
5
7 3 1 9 5
output02.txt
1 3 5 7 9
1 3 5 9 7
1 3 7 5 9
1 3 7 9 5
1 3 9 5 7
1 3 9 7 5
1 5 3 7 9
1 5 3 9 7
1 5 7 3 9
1 5 7 9 3
1 5 9 3 7
1 5 9 7 3
1 7 3 5 9
1 7 3 9 5
1 7 5 3 9
1 7 5 9 3
1 7 9 3 5
1 7 9 5 3
1 9 3 5 7
1 9 3 7 5
1 9 5 3 7
1 9 5 7 3
1 9 7 3 5
1 9 7 5 3
3 1 5 7 9
3 1 5 9 7
3 1 7 5 9
3 1 7 9 5
3 1 9 5 7
3 1 9 7 5
3 5 1 7 9
3 5 1 9 7
3 5 7 1 9
3 5 7 9 1
3 5 9 1 7
3 5 9 7 1
3 7 1 5 9
3 7 1 9 5
3 7 5 1 9
3 7 5 9 1
3 7 9 1 5
3 7 9 5 1
3 9 1 5 7
3 9 1 7 5
3 9 5 1 7
3 9 5 7 1
3 9 7 1 5
3 9 7 5 1
5 1 3 7 9
5 1 3 9 7
5 1 7 3 9
5 1 7 9 3
5 1 9 3 7
5 1 9 7 3
5 3 1 7 9
5 3 1 9 7
5 3 7 1 9
5 3 7 9 1
5 3 9 1 7
5 3 9 7 1
5 7 1 3 9
5 7 1 9 3
5 7 3 1 9
5 7 3 9 1
5 7 9 1 3
5 7 9 3 1
5 9 1 3 7
5 9 1 7 3
5 9 3 1 7
5 9 3 7 1
5 9 7 1 3
5 9 7 3 1
7 1 3 5 9
7 1 3 9 5
7 1 5 3 9
7 1 5 9 3
7 1 9 3 5
7 1 9 5 3
7 3 1 5 9
7 3 1 9 5
7 3 5 1 9
7 3 5 9 1
7 3 9 1 5
7 3 9 5 1
7 5 1 3 9
7 5 1 9 3
7 5 3 1 9
7 5 3 9 1
7 5 9 1 3
7 5 9 3 1
7 9 1 3 5
7 9 1 5 3
7 9 3 1 5
7 9 3 5 1
7 9 5 1 3
7 9 5 3 1
9 1 3 5 7
9 1 3 7 5
9 1 5 3 7
9 1 5 7 3
9 1 7 3 5
9 1 7 5 3
9 3 1 5 7
9 3 1 7 5
9 3 5 1 7
9 3 5 7 1
9 3 7 1 5
9 3 7 5 1
9 5 1 3 7
9 5 1 7 3
9 5 3 1 7
9 5 3 7 1
9 5 7 1 3
9 5 7 3 1
9 7 1 3 5
9 7 1 5 3
9 7 3 1 5
9 7 3 5 1
9 7 5 1 3
9 7 5 3 1

Solution

main.go
package main

import "fmt"

func main() {
  var N int
  fmt.Scan(&N)

  numbers := make([]int, N)

  for i := 0; i < N; i++ {
    fmt.Scan(&numbers[i])
  }

  Permutations(numbers)
}

func Permutations(numbers []int) {
  perms := make(chan []int, len(numbers))
  go permutations(numbers[1:], perms)

  for perm := range perms {
    for _, prefix := range numbers {
      fmt.Print(prefix)

      for _, i := range perm {
        if numbers[i] == prefix {
          i = len(numbers) - 1
        }

        fmt.Print(" ", numbers[i])
      }

      fmt.Println()
    }
  }
}

func permutations(numbers []int, perms chan<- []int) {
  N := len(numbers)

  indexes := make([]int, N)
  for i := 0; i < N; i++ {
    indexes[i] = i
  }

  facts := genFactorials(numbers)

  for pi, max := 0, fact(N); pi < max; pi++ {
    if pi == 0 {
      perms <- append([]int{}, indexes...)
      continue
    }

    if pi%2 == 1 {
      swap(indexes, N-2, N-1)
      perms <- append([]int{}, indexes...)
      continue
    }

    for i, v := range facts {
      if pi%v != 0 {
        continue
      }

      if i == N-3 {
        // Since the order doesn't matter for the last three elements, this
        // avoids some extra computation.
        swap(indexes, i, N-1)
        break
      }

      j := i + 1 + findNextIndex(indexes[i+1:], indexes[i])
      swap(indexes, i, j)

      // Sort until the last three elements
      for x := range indexes[i+1 : N-3] {
        x += i + 1
        y := x + 1 + findLowestIndex(indexes[x+1:])
        swap(indexes, x, y)
      }

      break
    }

    perms <- append([]int{}, indexes...)
  }

  close(perms)
}

func fact(n int) int {
  if n == 0 {
    return 1
  }

  r := 1

  for ; n > 1; n-- {
    r *= n
  }

  return r
}

func findLowestIndex(s []int) int {
  var lowest, index int

  for i, v := range s {
    if i == 0 || v < lowest {
      lowest = v
      index = i
    }
  }

  return index
}

func findNextIndex(s []int, c int) int {
  var lowest, index int = 0, -1

  for i, v := range s {
    if v > c && (index == -1 || v < lowest) {
      lowest = v
      index = i
    }
  }

  return index
}

func genFactorials(s []int) []int {
  l := len(s)

  if len(s) < 3 {
    return nil
  }

  facts := make([]int, 0, l-2)

  for i := l - 1; i > 1; i-- {
    facts = append(facts, fact(i))
  }

  return facts
}

func swap(s []int, i, j int) {
  s[i], s[j] = s[j], s[i]
}