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]
}
Privacy policy

This site uses tracking cookies when:

  • Comments are loaded. If you don’t want them, just don’t click «Show comments».

If you use only Open Source products, sorry about using cookies, I will replace Disqus as my comments platform in the future.

If you use private source products, worrying about privacy and using this products is like worrying about global warming and not recycling.. So just don’t.. 😒