波動均分算法

by leeenx on 2018-01-11

「波動」和「均分」大部分讀者朋友是知道的，但看到「波動均分」應該是一頭霧水的。其實，這個名詞是筆者拼湊出來的。

什么是「波動均分」？

把指定的數(shù)值 A，分成 N 份，此時每份的數(shù)值在一個固定的區(qū)間 [max, min] 內(nèi)。從視覺上看，每份的數(shù)量在平均線上下波動，并帶有隨機性：

這種分配不是嚴格意義上的「均分」，但它卻跟「均分」很相似，按筆者的理解給這個算法取個名字 —— 「波動均分」。

波動均分算法應該具備的特征如下：

分配數(shù)量
波峰高度
波谷深度
隨機分配
組合全面

前三個特征是提供對外配置的接口，保證算法的使用者可以指定分配的數(shù)量和定制波動的波峰和波谷（盡管大部分情況下，波峰 = 波谷）；「隨機分配」表示算法的結果是隨機的；

「組合全面」表示算法的結果是可以覆蓋所有可能的結果。

接下來，筆者將介紹兩種實現(xiàn)「波動均分」的算法：

窮舉法
快速分配

備注：本文算法中使用到的平均值是0

窮舉法

「窮舉法」顧名思義就是列舉所有可能出現(xiàn)的組合，再隨機抽取一個組合作為輸出結果。

下面是一個「波動均分」任務：

有一張 10x10 的表格，需要對格子上5種顏色并要求每種顏色的數(shù)量在區(qū)間 [18, 22] 內(nèi)。

由上述可得：每種顏色都會有5種分配結果（18, 19, 20, 21, 22）。窮舉這些顏色分配數(shù)量的組合其實就是建設一棵高度為 6 的 5 叉樹的過程。

第 6 層的葉子數(shù)就是「所有可能出現(xiàn)的組合」的總數(shù)。換而言之，從樹的第六層的一片葉子到第二層節(jié)點的路徑即是一種分配組合。

以下是「窮舉法」的代碼實現(xiàn)：

function exhaustWave(n = 5, crest = 4, trough = 4) { 
	let root = {parent: null, count: null, subtotal: 0}; // 根節(jié)點
	let leaves = [root]; // 葉子（數(shù)組）
	let level = 0; // 層數(shù) 
	// 檢查當前組合是否合法
	let isOK = subtotal => {
		if(level < n - 1) {
			if(-subtotal <= (n - level) * crest || subtotal <= (n - level) * trough) return true; 
		}
		else if(subtotal === 0) return true; 
		else return false; 
	}
	// 生成組合樹 
	while(level < n) { 
		let newLeaves = []; // 存儲最新葉子
		leaves.forEach(node => {
			for(let count = -trough; count <= crest; ++count) {
				let subtotal = node.subtotal + count; 
				isOK(subtotal) && newLeaves.push(
					{parent: node, count: count, subtotal: subtotal}
				); 
			}
		}); 
		leaves = newLeaves, ++level; 
	}
	// 隨機取一片葉子
	let leaf = leaves[Math.random() * leaves.length >> 0]; 
	let group = [leaf.count]; 
	for(let i = 0; i < 4; ++i) { 
		leaf = leaf.parent; 
		group.push(leaf.count); 
	}
	return group; 
}

窮舉法的局限：

「無窮集合」不適用
窮舉算法效率低下

由于「窮舉法」的這兩個致命限制，所以它不是適用于業(yè)務。事實上，筆者主要是使用「窮舉法」校驗「快速分配」方案的全面性。

快速分配

「快速分配」方案的思路：

獲取可分配波動范圍；
在波動范圍內(nèi)隨機取值

代碼的實現(xiàn)過程如下：

function quickWave(n = 5, crest = 4, trough = 4, isInteger = true) { 
	let list = []; 
	// 無法進行波動均分，直接返回完全平分
	if(crest > (n - 1) * trough || trough > (n - 1) * crest) {
		return new Array(n).fill(0); 
	}
	let base = 0; // 最少需要消除的高度
	let wave = 0; // 波動量
	let high = crest; // 高位
	let low = -trough; // 低位
	let sum = 0; // 累計量 
	let count = n; // 剩余數(shù)量 
	while(--count >= 0) { 
		// 動態(tài)當前的波動量
		if(crest > count * trough - sum) {
			high = count * trough - sum; 
		}
		if(trough > count * crest + sum) {
			low = -sum - count * crest; 
		}
		base = low; 
		wave = high - low; 
		let rnd; // 隨機波動量 
		if(count > 0) {
			rnd = base + Math.random() * (wave + 1); // 隨機波動
		} else {
			rnd = -sum; 
		}
		if(isInteger === true) {
			rnd = Math.floor(rnd); 
		} 
		sum += rnd; 
		list.push(rnd); 
	}
	return list; 
}

波動均分的「快速分配」方案在算法效率上是高效的，并且「快速分配」適用于「無窮集合」。

如何使用「窮舉法」校驗「快速分配」的全面性？

「窮舉法」能直接返回分配組合的總數(shù)，而「快速分配」只能隨機返回一次組合，筆者是通過大數(shù)量地調(diào)用「快速分配」算法并累積不重復組合來驗證「快速分配」的全面性。代碼如下：

console.log(exhaustWave(5, 4, 4)); // 組合總數(shù): 3951
let res = {}, count = 0, len = 10000; 
for(let i = 0; i < len; ++i) { 
	let name = quickWave(5, 4, 4).join("_"); 
	res[name] !== true && (res[name] = true, ++count); 
}
console.log(count); // len次快速分配后的組合總數(shù)

通過調(diào)整變量 len 可以發(fā)現(xiàn)，當 len 越來越大輸出的結果就越逼近 3951，當?shù)竭_一定量級后，輸出的結果就是 3951。