波动均分算法

r囧r小猫 2022-05-21 11:11 165阅读 0赞

「波动」和「均分」大部分读者朋友是知道的，但看到「波动均分」应该是一头雾水的。其实，这个名词是笔者拼凑出来的。

什么是「波动均分」？

把指定的数值 A，分成 N 份，此时每份的数值在一个固定的区间 \[max, min\] 内。 从视觉上看，每份的数量在平均线上下波动，并带有随机性：

![正余弦波线图][2017-12-06-waveAverage.gif]

这种分配不是严格意义上的「均分」，但它却跟「均分」很相似，按笔者的理解给这个算法取个名字 —— 「波动均分」。

波动均分算法应该具备的特征如下：

*  分配数量
 *  波峰高度
 *  波谷深度
 *  随机分配
 *  组合全面

前三个特征是提供对外配置的接口，保证算法的使用者可以指定分配的数量和定制波动的波峰和波谷（尽管大部分情况下，波峰 = 波谷）；「随机分配」表示算法的结果是随机的；  
「 组合全面」表示算法的结果是可以覆盖所有可能的结果。

接下来，笔者将介绍两种实现「波动均分」的算法：

*  穷举法
 *  快速分配

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

## 穷举法 ##

「穷举法」顾名思义就是列举所有可能出现的组合，再随机抽取一个组合作为输出结果。

下面是一个「波动均分」任务：

> 有一张 10x10 的表格，需要对格子上5种颜色并要求每种颜色的数量在区间 \[18, 22\] 内。

由上述可得：每种颜色都会有5种分配结果（18, 19, 20, 21, 22）。穷举这些颜色分配数量的组合其实就是建设一棵高度为 6 的 5 叉树的过程。

![5叉树][5]

第 6 层的叶子数就是「所有可能出现的组合」的总数。换而言之，从树的第六层的一片叶子到第二层节点的路径即是一种分配组合。

以下是「穷举法」的代码实现：

<table style="border:none;font-style:inherit;font-family:inherit;font-size:12px;vertical-align:baseline;border-spacing:0px;"> 
 <tbody style="font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
  <tr style="border-top:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
   <td style="font-style:inherit;font-family:inherit;font-size:12px;vertical-align:baseline;color:rgb(51,51,51);"><pre style="border:none;font-style:inherit;font-family:'Input Mono', 'PT Mono', Consolas, Monaco, Menlo, monospace;vertical-align:baseline;background:rgb(247,247,247);color:rgb(102,102,102);line-height:1.6;text-align:right;"></pre> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      1 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      2 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      3 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      4 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      5 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      6 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      7 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      8 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      9 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      10 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      11 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      12 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      13 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      14 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      15 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      16 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      17 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      18 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      19 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      20 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      21 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      22 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      23 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      24 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      25 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      26 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      27 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      28 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      29 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      30 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      31 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      32 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      33 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      34 
    </div></td> 
   <td style="font-style:inherit;font-family:inherit;font-size:12px;vertical-align:baseline;color:rgb(51,51,51);"><pre style="border:none;font-style:inherit;font-family:'Input Mono', 'PT Mono', Consolas, Monaco, Menlo, monospace;vertical-align:baseline;background:rgb(247,247,247);color:rgb(77,77,76);line-height:1.6;"></pre> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(66,113,174);"><span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">function</span> <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(62,153,159);">exhaustWave</span>(<span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(245,135,31);">n = <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">5</span>, crest = <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">4</span>, trough = <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">4</span></span>) </span>{ 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">let</span> root = { 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">parent</span>: 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(245,135,31);">null</span>, 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">count</span>: 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(245,135,31);">null</span>, 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">subtotal</span>: 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">0</span>}; 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 根节点</span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">let</span> leaves = [root]; 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 叶子（数组）</span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">let</span> level = 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">0</span>; 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 层数 </span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 检查当前组合是否合法</span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">let</span> isOK = 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(66,113,174);"><span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(245,135,31);">subtotal</span> =&gt;</span> { 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">if</span>(level &lt; n - 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">1</span>) { 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">if</span>(-subtotal &lt;= (n - level) * crest || subtotal &lt;= (n - level) * trough) 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">return</span> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(245,135,31);">true</span>; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      } 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">else</span> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">if</span>(subtotal === 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">0</span>) 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">return</span> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(245,135,31);">true</span>; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">else</span> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">return</span> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(245,135,31);">false</span>; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      } 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 生成组合树 </span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">while</span>(level &lt; n) { 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">let</span> newLeaves = []; 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 存储最新叶子</span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      leaves.forEach( 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(66,113,174);"><span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(245,135,31);">node</span> =&gt;</span> { 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">for</span>( 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">let</span> count = -trough; count &lt;= crest; ++count) { 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">let</span> subtotal = node.subtotal + count; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      isOK(subtotal) &amp;&amp; newLeaves.push( 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      { 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">parent</span>: node, 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">count</span>: count, 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">subtotal</span>: subtotal} 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      ); 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      } 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      }); 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      leaves = newLeaves, ++level; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      } 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 随机取一片叶子</span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">let</span> leaf = leaves[ 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(245,135,31);">Math</span>.random() * leaves.length &gt;&gt; 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">0</span>]; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">let</span> group = [leaf.count]; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">for</span>( 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">let</span> i = 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">0</span>; i &lt; 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">4</span>; ++i) { 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      leaf = leaf.parent; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      group.push(leaf.count); 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      } 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">return</span> group; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      } 
    </div></td> 
  </tr> 
 </tbody> 
</table>

穷举法的局限：

1.  「无穷集合」不适用
2.  穷举算法效率低下

由于「穷举法」的这两个致命限制，所以它不是适用于业务。事实上，笔者主要是使用「穷举法」校验「快速分配」方案的全面性。

## 快速分配 ##

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

1.  获取可分配波动范围；
2.  在波动范围内随机取值

代码的实现过程如下：

<table style="border:none;font-style:inherit;font-family:inherit;font-size:12px;vertical-align:baseline;border-spacing:0px;"> 
 <tbody style="font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
  <tr style="border-top:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
   <td style="font-style:inherit;font-family:inherit;font-size:12px;vertical-align:baseline;color:rgb(51,51,51);"><pre style="border:none;font-style:inherit;font-family:'Input Mono', 'PT Mono', Consolas, Monaco, Menlo, monospace;vertical-align:baseline;background:rgb(247,247,247);color:rgb(102,102,102);line-height:1.6;text-align:right;"></pre> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      1 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      2 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      3 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      4 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      5 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      6 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      7 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      8 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      9 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      10 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      11 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      12 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      13 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      14 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      15 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      16 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      17 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      18 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      19 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      20 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      21 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      22 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      23 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      24 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      25 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      26 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      27 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      28 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      29 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      30 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      31 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      32 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      33 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      34 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      35 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      36 
    </div></td> 
   <td style="font-style:inherit;font-family:inherit;font-size:12px;vertical-align:baseline;color:rgb(51,51,51);"><pre style="border:none;font-style:inherit;font-family:'Input Mono', 'PT Mono', Consolas, Monaco, Menlo, monospace;vertical-align:baseline;background:rgb(247,247,247);color:rgb(77,77,76);line-height:1.6;"></pre> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(66,113,174);"><span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">function</span> <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(62,153,159);">quickWave</span>(<span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(245,135,31);">n = <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">5</span>, crest = <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">4</span>, trough = <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">4</span>, isInteger = true</span>) </span>{ 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">let</span> list = []; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 无法进行波动均分，直接返回完全平分</span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">if</span>(crest &gt; (n - 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">1</span>) * trough || trough &gt; (n - 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">1</span>) * crest) { 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">return</span> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">new</span> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(245,135,31);">Array</span>(n).fill( 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">0</span>); 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      } 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">let</span> base = 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">0</span>; 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 最少需要消除的高度</span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">let</span> wave = 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">0</span>; 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 波动量</span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">let</span> high = crest; 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 高位</span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">let</span> low = -trough; 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 低位</span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">let</span> sum = 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">0</span>; 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 累计量 </span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">let</span> count = n; 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 剩余数量 </span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">while</span>(--count &gt;= 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">0</span>) { 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 动态当前的波动量</span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">if</span>(crest &gt; count * trough - sum) { 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      high = count * trough - sum; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      } 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">if</span>(trough &gt; count * crest + sum) { 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      low = -sum - count * crest; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      } 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      base = low; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      wave = high - low; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">let</span> rnd; 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 随机波动量 </span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">if</span>(count &gt; 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">0</span>) { 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      rnd = base + 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(245,135,31);">Math</span>.random() * (wave + 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(113,140,0);">1</span>); 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(142,144,140);">// 随机波动</span> 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      } 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">else</span> { 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      rnd = -sum; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      } 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">if</span>(isInteger === 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(245,135,31);">true</span>) { 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      rnd = 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(245,135,31);">Math</span>.floor(rnd); 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      } 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      sum += rnd; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      list.push(rnd); 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      } 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;"> 
     <span style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(137,89,168);">return</span> list; 
    </div> 
    <div style="border:0px;font-style:inherit;font-family:inherit;vertical-align:baseline;">
      } 
    </div></td> 
  </tr> 
 </tbody> 
</table>

波动均分的「快速分配」方案在算法效率上是高效的，并且「快速分配」适用于「无穷集合」。

如何使用「穷举法」校验「快速分配」的全面性？  
「穷举法」能直接返回分配组合的总数，而「快速分配」只能随机返回一次组合，笔者是通过大数量地调用「快速分配」算法并累积不重复组合来验证「快速分配」的全面性。代码如下：

通过调整变量 `len` 可以发现，当 `len` 越来越大输出的结果就越逼近 3951，当到达一定量级后，输出的结果就是 3951。

出处：凹凸实验室（ [https://aotu.io/notes/2018/01/11/waveaverage/][https_aotu.io_notes_2018_01_11_waveaverage]）

[2017-12-06-waveAverage.gif]: https://misc.aotu.io/leeenx/waveAverage/2017-12-06-waveAverage.gif
[5]: https://misc.aotu.io/leeenx/waveAverage/20180110_tree.gif?v=5
[https_aotu.io_notes_2018_01_11_waveaverage]: https://aotu.io/notes/2018/01/11/waveaverage/