Loolob

welcome to Loolob

0%

递归取全排列

发表于 更新于

(线性代数相关) 递归取全排列

  1. 两个数排列，两两交换
1
2
3
4
5
swap(1, 2) => \begin{cases}
1, 2 \\
\\
2, 1
\end{cases}

  1. 三个数排列，三三交换（提取一个数，剩下的两两交换，然后与提取出的数合成新排列）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    swap(1, 2, 3) => \begin{cases}
    1 + swap(2, 3) => 1 + \begin{cases}
    2, 3 => 1, 2, 3 \\
    \\
    3, 2 = > 1, 3, 2
    \end{cases}\\
    \\
    2 + swap(1, 3) => 2 + \begin{cases}
    1, 3 => 2, 1, 3 \\
    \\
    3, 1 = > 2, 3, 1
    \end{cases}\\
    \\
    3 + swap(1, 2) => 3 + \begin{cases}
    1, 2 => 3, 1, 2\\
    \\
    2, 1 => 3, 2, 1
    \end{cases}\\
    \end{cases}

  2. 四个数排列，四四交换（提取一个数，剩下的三三交换，然后与提取出的数合成新排列）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    swap(1, 2, 3, 4) =>  \begin{cases}
    1 + swap(2, 3, 4)\\
    \\
    2 + swap(1, 3, 4)\\
    \\
    3 + swap(1, 2, 4)\\
    \\
    4 + swap(1, 2, 3)\\
    \end{cases}

  3. 依次类推，有N个数排列时，提取1个，剩下的(N-1)个数进行交换，然后与提取出的数合成新排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
swap(1, 2, 3 ... N) =>  \begin{cases}
1 + swap(2, 3 ... N)\\
\\
2 + swap(1, 3 ... N)\\
\\
3 + swap(1, 2 ... N)\\
.
\\
.
\\
.
\\
N + swap(1, 2, 3 ... N-1)\\
\end{cases}
  1. 借助递归思想，有N个数时，可以逐层展开，直到剩下两个数互相交换后返回

python实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 递归取全排列，输入为数组
def permutation(array):
    if len(array) < 2:
        return [array]
    elif len(array) == 2:
        # 当输入的数组仅有两个数时，返回原数组和两两交换后的数组
        return [array, [array[1], array[0]]]
    else:
        # 当输入的数组长度为n时，提取1个数，剩下的(n-1)个数组成新数组再次调用permutation
        allArray = []
        for index in range(0, len(array), 1):
            for arrayList in permutation(array[0:index] + array[index+1:]):
                allArray.append([array[index]] + arrayList)
        return allArray