Permute an array of integers, finding the largest number represented by concatinating the array values

Permutation

package main

import (
	"fmt"
)

func orderOfMagnitude(magnitude, val int) int {
	for {
		if val == 0 {
			break
		}
		val /= 10
		magnitude += 1
	}
	return magnitude
}

// when flattening a number, shift and then add the values together
// based on the right hand side numbers magnitude
func appendNumber(left, right int) int {
	magnitude := 0
	magnitude = orderOfMagnitude(magnitude, right)

	for i := 0; i < magnitude; i++ {
		left = left * 10
	}
	return left + right
}

// flatten an array into a number
func numberFromArray(number int, remainingNumbers []int) int {
	if len(remainingNumbers) == 0 {
		return number
	}
	number = appendNumber(number, remainingNumbers[0])
	remainingNumbers = remainingNumbers[1:len(remainingNumbers)]

	return numberFromArray(number, remainingNumbers)
}

// this algorithm is moving left to right over the array swapping values as it goes
// - permute an array of positive integers
// - flatten each permuted result into a number
// - push those flattened numbers into an array
// result: "permuted" contains the flattened results of the permutation of "numbers"
func permutations(at int, numbers []int, permuted *[]int) {
	// once we have advanced to the point where we have two more values in our array
	// we just need to swap and store two results as flattened values
	if at == len(numbers)-2 {
		n := make([]int, len(numbers))
		copy(n, numbers)

		n1 := numberFromArray(n[0], n[1:len(n)])
		*permuted = append(*permuted, n1)

		s1 := n[len(n)-1]
		s2 := n[len(n)-2]
		n[len(n)-2] = s1
		n[len(n)-1] = s2

		n2 := numberFromArray(n[0], n[1:len(n)])
		*permuted = append(*permuted, n2)
		return
	}

	// this recusive call is branching out so it can be dangerous to run on large arrays of numbers
	newAt := at + 1
	for i := 0; i < len(numbers)-at; i++ {
		var prefix []int
		if at > 0 {
			prefix = numbers[:at]
		}
		number := numbers[at]
		numbers = numbers[at+1 : len(numbers)]
		numbers = append(numbers, number)

		if at > 0 {
			numbers = append(prefix, numbers...)
		}
		permutations(newAt, numbers, permuted)
	}
	return
}

func main() {
	largest := 0
	numbers := []int{1, 2, 3, 4}
	permuted := []int{}

	permutations(0, numbers, &permuted)
	fmt.Println(permuted)

	for _, p := range permuted {
		if p > largest {
			largest = p
		}
	}
	fmt.Println(numbers, "->", largest)
}