Lotplace

剛好Leetcode有一樣的題目 46. Permutations ，
在沒上過離散數學之前真的完全沒頭緒，直接skip掉，
現在一年過去了，有離散跟資結算法的基礎，解起來輕鬆很多。

解題思路

排列n個相異物，即n!種排法，
可以得知排法的總數為
n! = (n – 1)! * n
1! = 1

但要把每種排法列舉出來，就必須更仔細推敲，
以顏色不同的球舉例，
排序依左至右的紅黃綠三顆球，可將紅球抽出，剩下兩顆球有:
1. 黃左綠右
2. 黃右綠左
這2種排法，
最後把紅球放回去，會變成
1. 紅黃綠
2. 紅綠黃
這2種排法，
之後將黃球、綠球用一樣的方法取出，可以得到
3. 黃紅綠
4. 黃綠紅
5. 綠紅黃
6. 綠黃紅
總共可以得3 * 2 = 6 = 3!種排列方式，
以此類推，排第n個相異物時，
只須將n個相異物輪流抽走，
排列完後再放回去，
就可以得到每一種的排列方法。

條件歸納

假設要排的數字有n個，
當n == 1時，回傳自身，
當n > 1時，輪流將第i個數字”固定”住，
並將其他剩餘的數字做排列組合後的結果加上去，
即為當下的解。

Golang

package main

import "fmt"

//將陣列往後推1格，藉此達到各數字依序當頭(第1個位置)的效果
func push_back(nums []int) []int {
    tmp := nums[0]
    for i := 0; i < len(nums)-1; i++ {
        nums[i] = nums[i+1]
    }
    nums[len(nums)-1] = tmp
    return append(nums)
}

//排列組合
func permute(nums []int) [][]int {
    if len(nums) == 1 {
        return [][]int{nums}
    }

    if len(nums) == 2 {
        return [][]int{nums, swap(nums)}
    }

    var result [][]int
    for i := 0; i < len(nums); i++ {
        //陣列首的數字固定，其餘的數字用遞迴做排列
        prev_result := permute(nums[1:])
        for j := 0; j < len(prev_result); j++ {
            //把其餘數字排列的結果加上當下固定的(陣列首)的數字即為所求
            prev_result[j] = append([]int{nums[0]}, prev_result[j]...)
            result = append(result, prev_result[j])
        }
        nums = push_back(nums)
    }
    return result
}

func main() {
    var length int
    fmt.Println("Enter the number of inputs")
    fmt.Scanln(&length)
    fmt.Println("Enter the inputs")
    nums := make([]int, length)
    for i := 0; i < length; i++ {
        fmt.Scanln(&nums[i])
    }
    fmt.Printf("permute(%d) = \n", nums)
    fmt.Println(permute(nums))
}

---

Filed under: 演算法 - @ 2021 年 7 月 19 日 下午 3:00

標籤: algo