排列數(shù)組

• 前言
• 一、隔板法
• 二、分組分配法

前言

排列組合在算法求解中尤為重要，特別是對(duì)于方案數(shù)的求解，以及我們知道本質(zhì)之后可以對(duì)其進(jìn)行深入的挖掘。如 $x+y=4$，求解的數(shù)量，如果數(shù)據(jù)小，我們可以枚舉，但是如果數(shù)據(jù)量大我們什么辦呢？首先我們需要對(duì)這個(gè)問題進(jìn)行抽象，把 x ，y 看成兩個(gè)盒子，4看成有4個(gè)小球，那么這題就轉(zhuǎn)換為了，將4個(gè)相同的球分配到2個(gè)盒子(允許有空盒)的方案數(shù)，那么就是$C(4+2?1,1)=5$

一、隔板法

相同元素的分配問題
1、條件和直接用法

轉(zhuǎn)變?yōu)樵趎-1個(gè)空隙中，放入k-1個(gè)板子的排列組合問題(k是盒子數(shù)量)

2、變式一，放入的個(gè)數(shù)不是1的時(shí)候而是m的時(shí)候什么辦

我們以2個(gè)先來講，因?yàn)楦舭宸ǘ际?個(gè)，那么我們就可以先將m個(gè)球放入m個(gè)盒子里，這樣剩余的球就又變成了隔板問題。相當(dāng)于分解子問題，那么分出的m個(gè)球我們也利用隔板法 ，不過在這個(gè)例子是1，所以間隔數(shù)與隔板數(shù)一樣因此就是1，剩余就是(n-m)個(gè)進(jìn)行隔板法。

那如果是每一個(gè)盒子至少放k個(gè)了，在這里我們可以發(fā)現(xiàn)我們先放的數(shù)量就是和盒子要求的至少少一個(gè)是一樣的，因此我們這一部分的發(fā)的方法都是1.

3、變式二，小球個(gè)數(shù)不是1，但是不都是一樣的，如下

我們的做法如圖還是先放一部分，讓剩余的滿足條件，那么這里就說一說，先放的為什么方法是1，我們可以都先放的再進(jìn)行一次分割子問題，變成不小于編號(hào)-1的球，然后再將這幾個(gè)球按照同樣的方式先放一部分，最后我們發(fā)現(xiàn)，這樣一直分，沒一個(gè)部分的分的方法都是1按照乘法原理最后就是1了。

4、有空盒的情況
我們是借與盒子數(shù)量相同的球，然后再進(jìn)行隔板法

二、分組分配法

1、分組

2、分組加分配
前一步是分組問題，后一步是分配問題，因此我們?cè)诮鉀Q的時(shí)候，先分組*分配

總結(jié)

以上是生活随笔為你收集整理的算法基础数学知识篇(1)之----- 排列数组的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。