Wave Distribution Algorithms: Exhaustive Search vs. Fast Random Allocation

What Is Wave Distribution?

Wave distribution splits a total value A into N parts, each part constrained within a fixed interval [min, max]. Visually the quantities fluctuate around the average line with randomness, resembling ordinary equal division but with controlled variance.

Key Features of a Wave Distribution Algorithm

Configurable number of parts

Adjustable crest (maximum deviation)

Adjustable trough (minimum deviation)

Randomized allocation

Full combinatorial coverage

The first three features act as interfaces for callers to set the count and the amplitude of the wave; "random allocation" ensures each execution yields a different result, while "full combinatorial coverage" guarantees that every possible combination can be produced.

Exhaustive Search Method

The exhaustive approach enumerates every feasible combination and then randomly selects one as the output.

Example task: a 10×10 grid must be filled with five colors, each color’s count must lie in [18, 22] .

Each color can take five possible counts (18‑22), so the problem reduces to building a 5‑ary tree of height 6. The leaf nodes at level 6 represent all possible allocation combinations.

function exhaustWave(n = 5, crest = 4, trough = 4) {
    let root = {parent: null, count: null, subtotal: 0};
    let leaves = [root];
    let level = 0;
    const isOK = subtotal => {
        if (level < n - 1) {
            if (-subtotal <= (n - level) * crest || subtotal <= (n - level) * trough)
                return true;
        } else if (subtotal === 0) {
            return true;
        }
        return false;
    };
    while (level < n) {
        let newLeaves = [];
        leaves.forEach(node => {
            for (let count = -trough; count <= crest; ++count) {
                let subtotal = node.subtotal + count;
                if (isOK(subtotal)) {
                    newLeaves.push({parent: node, count, 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;
}

Limitations of the Exhaustive Method

Unsuitable for infinite sets

Very low efficiency, making it impractical for production use

Because of these drawbacks, the exhaustive method is mainly used to verify the completeness of the fast allocation algorithm.

Fast Allocation Method

The fast method works by first determining the feasible wave range and then picking a random value within that range for each part.

Obtain the allowable wave interval

Randomly select a value inside the interval

function quickWave(n = 5, crest = 4, trough = 4, isInteger = true) {
    // If the wave range is impossible, return a perfectly even split
    if (crest > (n - 1) * trough || trough > (n - 1) * crest) {
        return new Array(n).fill(0);
    }
    let base = 0, wave = 0, high = crest, low = -trough, sum = 0, count = n;
    const list = [];
    while (--count >= 0) {
        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) rnd = Math.floor(rnd);
        sum += rnd;
        list.push(rnd);
    }
    return list;
}

This fast algorithm runs in linear time and works for infinite sets, making it suitable for real‑world applications.

Validating Fast Allocation with Exhaustive Search

To ensure the fast method can generate every possible combination, the author repeatedly calls quickWave and records distinct results until the count matches the total number of combinations returned by exhaustWave (3951 for the example parameters).

console.log(exhaustWave(5, 4, 4)); // Combination total: 3951
let res = {}, count = 0, len = 10000;
for (let i = 0; i < len; ++i) {
    let name = quickWave(5, 4, 4).join("_");
    if (res[name] !== true) {
        res[name] = true;
        ++count;
    }
}
console.log(count); // Number of unique combos after len runs

Increasing len makes the observed unique count approach 3951; once it stabilizes, the fast algorithm is confirmed to be exhaustive.

Conclusion

The author coined the term "wave distribution" to describe a random yet bounded partitioning technique. While the exhaustive approach is too slow for production, it serves as a correctness benchmark for the efficient fast allocation method, which can handle both finite and infinite domains.