TOC
前置工具代码
一些前置的工具 下面代码不会再给出
// 求N的阶乘
const factorial = (() => {
var f = [1, 1]
var i = 2
return function factorial(n) {
if (typeof f[n] != 'undefined') return f[n]
var result = f[i - 1]
for (; i <= n; i++) f[i] = result = result * i
return result
}
})()
// 找出目标arr内 start end 闭区间内 大于 base基准值 的最小数
function findMinForBigIndex(arr, start, end, base) {
let minIndex = start
for (let i = start + 1; i <= end; i++) {
if (arr[i] < arr[minIndex] && arr[i] > base) {
minIndex = i
}
}
return minIndex
}
// 交换数组内的两个元素
function swap(arr, i, j) {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
// 对数组的某个闭区间进行反转顺序
function reverse(arr, start, end) {
return arr.slice(0, start).concat(arr.slice(start, end + 1).reverse())
}
/**
* 根据下标字典隐对原始数组进行 Mapping
* @param {Array} origin 原始的排列数组
* @param {Array} dict 字典数组
*/
function match(origin, dict) {
return dict.map((index) => origin[index])
}
生成排列
排列（英语：Permutation）是将相异对象或符号根据确定的顺序重排。每个顺序都称作一个排列。例如，从一到六的数字有720种排列，对应于由这些数字组成的所有不重复亦不阙漏的序列，例如”4, 5, 6, 1, 2, 3” 与1, 3, 5, 2, 4, 6。
比如我们拥有集合A A = {1,2,3} 那么
[ 1, 2, 3 ]
[ 1, 3, 2 ]
[ 2, 1, 3 ]
[ 2, 3, 1 ]
[ 3, 1, 2 ]
[ 3, 2, 1 ]
就是他的全排列，所谓全排列，就是从集合 A 中取 r 个元素(并且r = |A| , 也就是集合A的个数)所组成的全部排列。
所有某个集合的排列都能通过下标字典来表示，比如我们拥有集合 {香蕉,苹果,橘子} ，那么 [1,3,2] 就代表了 [香蕉，橘子，苹果] 这一子排列。你可以认为只要生成一系列的字典，就等于生成了我们的排列，每一个字典都能与某个排列一一对应(所以你完全可以把这个字典跟排列具体进行等价替换)。那么为了生成我们的字典，我们还需要引入字典的顺序!
我们假设我们拥有两个排列A B, 那么我们从前往后对两个集合的相对应的元素进行比较，直到发现两个元素不相等，那么我们就以这两个元素的大小关系来定义这两个排列集合的先后顺序。 比如 [ 2, 3, 4, 5, 1 ] < [ 2, 3, 5, 1, 4 ] 因为两者虽然1、2 位相同，但是在第三位上 第一个集合(4)小于第二个(5), 你可以看作是前面的位具有更高的权重。
现在我们有了顺序，假设我们为一个集合(A = {1,2,3})建立了一个最小的字典 dict = [1,2,3],我们应该如何从这个字典计算出下一个 在所有大于该字典的字典里面最小的那个 也就是下一个相邻字典呢?
现在考虑我们拥有一个初始字典[a1,a2,a3,...,an]，首先假设 a[n-1] < a[n], 那么显然我们只要交换 a[n-1] 和 a[n] 就能得到一个大于初始字典的字典，并且这个新字典是所有大于该字典的所有字典里面最小的哪一个(因为其他可能的字典都是需要替换前面更高权重的位)，另外如果 a[n-1] > a[n] 那么显然交互之后会得到一个比原字典更小的一个字典。继续考虑三个元素进行交换的情况，假设 a[n-2] < a[n-1], 我们同样可以通过更改后三位的顺序来找到下一个相邻字典,首先对比 a[n] 和 a[n-1] ，找出相对较小的那个数，把他放到 n-2的位置上，接着对原来的 a[n-2] 和 剩余数进行从小到大的顺序，重新放置到 a[n-1] 和 a[n]的位置上,比如说 [ 2, 3, 4, 1, 6, 5] 的下一个 相邻字典 是 [ 2, 3, 4, 5, 1, 6 ]。
接下来我们可以给出一般性方法，来给出如何通过一个字典找出下一个 相邻字典,假设拥有字典 [a1,a2,a3,...,an], 那么从后往前开始查询，直到发现 a[j] < a[j+1] 并且 j < n , 那么我们找出 a[j+1] a[j+2] ... a[n] 里面大于a[j]并且最小的那个数 a[m], 交换 a[j] 与 a[m]的值，接着对 a[j+1] a[j+2] ... a[n] 进行递增顺序进行重排序，如此我们就得到了下一个字典。
代码实现
这里给出简单的代码实现
/**
* @description 求数组的所有排列
*/
function p(arr) {
let n = arr.length - 1
let result = []
// 创建初始字典字典
let currentDict = []
for (let i = 0; i <= n; i++) {
currentDict[i] = i
}
result.push(match(arr, currentDict))
// 枚举出所有字典
let loop = true
while (loop) {
// 找出 currentDict 的下一个字典
for (let j = n - 1; j >= 0; j--) {
if (currentDict[j] < currentDict[j + 1]) { // 找出一个低谷
// 替换上面说到的 j 和 m
swap(currentDict, j, findMinForBigIndex(currentDict, j + 1, n, currentDict[j]))
/**
* 这里比较有意思，你可以把整个从后向前查询的过程，看作是不断往高处走
* 尝试寻找一个比当前位置更低的位置
* 也正是因为这个原因 在替换之前 a[j+1] ... a[n] 本身就是有序的 而且是降序
* 那么当a[j] 和 a[m] 进行swap之后，其实顺序仍然是成立的
* 因为本来就有降序，那么必然 a[m-1] > a[m] > a[m+1]
* 而 a[m] 因为我们的限定条件 a[j] < a[m]
* 所以替换完毕之后 a[m-1] > a[m] 依然成立(因为换了一个比m更小的值来)
* 另一方面由于我们的限定条件 寻找到的 a[m] 必然 大于 a[j]
* 而 a[m + 1] 本身小于 a[m] 但是没被选中，说明 a[m+1] 必然小于 a[j]
* 简单来说就是 我们的条件的两部分 正好让swap之后 有序依然成立
* 那么我们自然只要进行反转数组就能转成递增排序了
*/
currentDict = reverse(currentDict, j + 1, n)
result.push(match(arr, currentDict))
break
} else if (j === 0 && currentDict[j] >= currentDict[j + 1]) {
// 无法寻找到下一个更大的字典 生成结束
loop = false
}
}
}
console.log(result)
}
p([1,2,3])
/**
[ [ 1, 2, 3 ],
[ 1, 3, 2 ],
[ 2, 1, 3 ],
[ 2, 3, 1 ],
[ 3, 1, 2 ],
[ 3, 2, 1 ],
]
/*
这个过程非常类似于 二进制的进位操作 比如 10000111 的下一位就是 从后往前找一个为0的位，设置为1，然后后面的全部归零(这个过程类似我们上面的重排序)，也就是 10001000 ，本质都是类似于权重的原理，只不过因为我们排列是从某个集合中获取到元素，所以不能随意设置，只能进行替换。
生成组合
组合可以认为是排列失去顺序维度之后的结果，比如 [1,2,3] 和 [3,2,1] 是在组合里面是完全相同的。
这是集合 {1,2,3,4} 的 3 组合 ，也就是拥有四个元素的集合取三个元素，所能组成的所有组合方式
[ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]
与排列相同，我们也用字典的方式来代表一个组合
下面给出 集合 {1,2,3,4...n} 的 r 组合的生成方法。利用同样的字典排序方法，我们可以看出其最小组合为 [1,2,3,4...n] 最大为 [n-r+1 , n-r+2 ,...n]，其生成下一个字典的方法为，从后向前扫描元素，直到找到 a[i] != n - r + i 的元素（这个过程可以看作是从后往前找一个还没加到最大的数）接着把 a[i] = a[i] + 1，且对于 j = i +1 ,i + 2 ,i + 3 ... r 也就是 a[i] 后面的每一个数，都执行 a[j] = a[i] + 1 + j - i, 这里由于我们上面已经对 a[i]进行了+1操作，所以可以进行替换，变成 a[j] = a[i](已经+1之后的) + j - i.
代码实现
let array = [1, 2, 3, 4]
function c(arr, r) {
let n = arr.length - 1
r = r - 1
let result = []
// 创建初始字典
let currentDict = []
for (let i = 0; i <= r; i++) {
currentDict.push(i)
}
result.push(match(arr, currentDict))
let loop = true
while (loop) {
for (let i = r; i >= 0; i--) {
if (currentDict[i] !== n - r + i) {
currentDict[i] = currentDict[i] + 1
for (let j = i + 1; j <= r; j++) {
currentDict[j] = currentDict[i] + j - i
}
result.push(match(arr, currentDict))
} else if (i === 0 && currentDict[i] === n - r + i) {
// done
loop = false
}
}
}
console.log(result)
}
// 求 数组 array 的 3 组合
c(array, 3)
// [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]
更实用的生成
这里给出更加贴近实际代码的做法，相对更快，更简单
function p(choose, options, r) {
if (r === 0) {
return console.log(choose)
}
for (let i = 0, len = options.length; i < len; i++) {
let newChoose = choose.slice()
let newOptions = options.slice()
newChoose.push(options[i])
newOptions.splice(i, 1)
p(newChoose, newOptions, r - 1)
}
}
function c(choose, options, r) {
if (options.length < r) { // 剪枝
return
}
if (r === 0) {
return console.log(choose)
}
for (let i = 0, len = options.length; i < len; i++) {
let newChoose = choose.slice()
let newOptions = options.slice(i + 1, len)
newChoose.push(options[i])
c(newChoose, newOptions, r - 1)
}
}
总结
我觉得这种建立字典顺序，然后进行不断的迭代出下一个相邻字典的方式还是相当有意思的， 当然这两个方法其实相对而言并不是很快，用递归能更快的计算，可能数学上面的意义更多一些。
参考
离散数学及其应用