前言

一次交流中被問到如何實(shí)現(xiàn)一組數(shù)字的全排列，比如【1，2，3】有多少種排列組合方式，如果拓展到【1，2，3，4，5】呢？

回顧

1.由于【1，2，3】有6種排列組合方式 1 * 2 * 3 = 6

2.得到【1，2，3，4，5】有 1 * 2 * 3 * 4 * 5 = 120 種組合方式

3.想到曾經(jīng)在學(xué)習(xí)時(shí)總是接觸到排列，想到用代碼去實(shí)現(xiàn)，于是很感興趣，對(duì)此問題感覺與其他問題不同，

4.直覺確定需要寫成遞歸邏輯，但是如何直接寫入一個(gè)遞歸函數(shù)？？？

5.想到過去總是寫樹的遍歷，實(shí)時(shí)上這種代碼都是背下來的，如何寫入一個(gè)遞歸函數(shù)。

for

import kotlin.collections.ArrayList

fun main() {

    val list = arrayListOf(1, 2, 3, 4)

    for (i in 0..3) {
        swap(0, i, list)
        for (j in 1..3) {
            swap(1, j, list)
            for (k in 2..3) {
                swap(2, k, list)
                printlnList(list)
                swap(k, 2, list)
            }
            swap(j, 1, list)
        }
        swap(i, 0, list)
    }
}

fun swap(a: Int, b: Int, c: ArrayList<Int>) {
    val temp = c[a]
    c[a] = c[b]
    c[b] = temp
}

fun printlnList(c: ArrayList<Int>) {
    for (a in c) {
        print("$a ")
    }
    print("\n")
}

遞歸

import kotlin.collections.ArrayList

fun main() {

    val list = arrayListOf(1, 2, 3, 4)

    test1(0, 3, list)
}

fun test1(start: Int, end: Int, list: ArrayList<Int>) {
    if (start + 1 == end) {
        for (i in start..end) {
            swap(start, i, list)
            printlnList(list)
            swap(i, start, list)
        }
        return
    }
    for (i in start..end) {
        swap(start, i, list)
        test1(start + 1, end, list)
        swap(i, start, list)
    }
}

回顧

此時(shí)有些想起動(dòng)態(tài)規(guī)劃，曾經(jīng)一直覺得遞歸函數(shù)很難實(shí)現(xiàn)，很多復(fù)雜遞歸函數(shù)也看不懂。我的理解，遞歸函數(shù)本就是計(jì)算機(jī)語言，更適合計(jì)算機(jī)去理解，而我們需要做的就是寫出for循環(huán)的demo，轉(zhuǎn)換它為遞歸，至于理解遞歸，需要做的只是有能力寫出對(duì)的for循環(huán)解決問題。理解轉(zhuǎn)換后的遞歸麻煩且只強(qiáng)行記憶。