解决分配珠子难题的算法？

Question

假设您有一个圆圈（如下所示），其中有 N 个点，您在插槽中分布了 N 个珠子。

这是一个例子： 每个珠子可以顺时针移动 X 个插槽，这需要花费 X ^ 2 美元。 您的目标是最终在每个插槽中放置一个珠子。 您需要花费的最少金额是多少？

此问题的更有趣的变体：分配珠子难题的算法（2）？

- Bob Billy

---

我真的很困惑。我有一个暴力解决方案，其中我重复移动每个珠子，直到它进入空格，但这不起作用，因为这不会给出最小金额。 - Bob Billy

我可以多次移动珠子吗？ - Daniel Jour

很遗憾只允许顺时针移动。如果没有这个限制，问题会更有趣。 - trincot

“X个插槽，需要花费X的平方美元。” 这种限制本身没有意义。如果移动X次1个插槽，比一次移动X个插槽要便宜，如果X>1。现在，如果您不能两次移动同一个珠子... - n. m.

只是为了澄清，每个珠子只能移动一次。之前可能不够清楚，非常抱歉。 - Bob Billy

Answer 1

在本答案中，我假设珠子只能移动一次。否则，珠子应该只能一次移动一个方格，这使得这个问题变得不那么有趣：平方的总和将降级为简单的移动总和。

这个问题可以在O(n)时间内解决，在第4点中我提供了一个JavaScript实现。如果你想跳过导致算法的推理，只需滚动到该部分。

编辑：我添加了一个B部分，在那里分析了该问题的一个变体。

但以下是导致建议的算法的观察：

1. 不超车

应该观察到，在最优解中，珠子永远不会被移动，以便其中一个珠子“超车”另一个珠子。这两个珠子交换目标槽的替代解决方案将始终给出较低的平方和。

为了稍微形式化一下，假设一个珠子从槽号a移动到b，另一个珠子从c移动到d。要求它们不能逆时针移动。现在让我们假设第一个超过了另一个，然后我们就有了所有这些真相：

1. a < b
2. c < d
3. a < c
4. b > d

那么，追击版本移动的方块数的平方和、以及替代版本（珠子交换目标）移动的方块数的平方和，应该像这样进行比较：

(b-a)² + (d-c)² > (d-a)² + (b-c)²

证明上述不等式失效的方法如下：

将不等式改写为：

b²-2ab+a² + d²-2cd+c² > d²-2ad+a² + b²-2bc+c²
-2ab + -2cd > -2ad + -2bc
ab + cd < ad + bc
a(b-d) < c(b-d)
a < c
true

因此，在开始处共享同一插槽的珠子在最优解中将总是出现在相邻插槽中。

更一般地说：

2. 只考虑珠子顺序不变的解决方案

因此，如果我们为开始于同一插槽的珠子给定（任意）顺序，我们可以说可以找到一个最优解，其中珠子的顺序与原始输入相同（因为禁止了超车）。

这也意味着，我们可以很容易地找到一个候选解决方案，我们按顺序号拾起珠子，并将它们放入具有相同顺序号的插槽中。这可能不是最优解，但可能是。如果包含逆时针移动甚至可能无效。但仍然有用作为起点。

3. 循环解决方案到最优解

任何其他保持相同顺序的潜在解决方案只需将所有珠子移至下一个插槽，直到找到有效且最佳的解决方案即可。我将这样的移动称为一个循环。

如果第一个候选解决方案由于逆时针移动而无效，则可以轻松找到最佳解决方案：选择最大的逆时针移动，并将其相反地添加到所有移动中，包括该移动。这将使所有违规移动不逆时针（至少有一个为零移动）。继续循环显然会使平方和更大。因此，这是最优解。

另一方面，如果候选解决方案有效，但没有珠子保持在位置，则可以通过沿另一个方向循环来改进解决方案，即通过使移动更小，直到至少有一个珠子保持在位置。

4. 算法

有了以上所有信息，我在此介绍了用JavaScript实现的算法，可以在此实时段代码中进行测试：

function optimalSpread(beadCounts) {
    // Initialisation
    var n = beadCounts.length;
    var solution = {
        // Keep track of sum of squares of moves
        // A move is a number of slots and only be positive (clockwise).
        sumSquares: 0,
        // Keep track of sum of moves.
        sumMoves: 0,
        // Per slot, keep an array with one element per bead, but
        // we start with empty arrays
        movesPerSlotPerBead: [],
    };
    // Build a first a non-optimised solution. 
    // Assign beads in FIFO order to consecutive slots.
    // *move*, when added to the current slot number, identifies the first slot where
    // a bead needs to end up in this solution. Note that this initial solution
    // may do counter-clockwise moves. This will be corrected later.
    // =O(n)
    var move = 0,
        totalBeadCount = 0,
        minMove = 0;
    beadCounts.forEach(function(beadCount, slotId) {
        // check sum
        totalBeadCount += beadCount;
        // See where the next bead would be moved (relative to slot)
        move += beadCount - 1;
        // and keep the minimum value. Can be negative, meaning a 
        // counter clockwise move.
        if (move < minMove) minMove = move;
    });
    // abort if number of beads is not equal to number of slots
    if (totalBeadCount !== n) return {error: "invalid input"}; 
    // Improve solution by making sure there are no counter-clockwise
    // moves, and at least one bead stays unmoved (0).
    // Apply correction we got from previous loop to ensure this.
    // =O(n)
    move = -minMove;
    beadCounts.forEach(function(beadCount, slotId) {
        solution.movesPerSlotPerBead[slotId] = [];
        // Move each bead into next available slot
        for (; beadCount > 0; beadCount--, move++) {
            // Store the move for this bead
            solution.movesPerSlotPerBead[slotId].push(move);
            solution.sumMoves += move;
            solution.sumSquares += move*move;
        }
        // Compensate the increment of slotId
        move--;
    });
    // The solution is now optimal:
    // Cycling counter-clockwise would make at least one bead go that way;
    // Cycling clockwise would increase the sum of squares (as all moves are
    //    non-negative values)
    return solution;
}

function randomInput(n) {
    // Start with slots having all zero beads:
    beadCounts = Array.from({length: n}, x => 0);
    // Randomly assign beads to slots, keeping a count per slot
    for (var i = 0; i < n; i++) {
        beadCounts[Math.floor(Math.random() * n)]++;
    }
    return beadCounts;
}

// Link with I/O
var input = document.getElementById('input');
var randomize = document.getElementById('randomize');
var calculate = document.getElementById('calculate');
var output = document.getElementById('output');

// Capture events
randomize.onclick = function() {
    var n = 5 + Math.floor(Math.random() * 20);
    input.value = randomInput(n).join(',');
    calculate.onclick();
};

calculate.onclick = function() {
    var beadCounts = input.value.split(',').map(Number);
    var solution = optimalSpread(beadCounts);
    if (solution.error) {
        output.textContent = 'Error: ' + solution.error;
        return;
    }
    output.textContent = 
        '\nInput: ' + JSON.stringify(beadCounts) +
        '\nSum of squares of moves: ' + solution.sumSquares +
        '\nSum of moves: ' + solution.sumMoves +
        '\nMoves[slot][bead]: ' + JSON.stringify(solution.movesPerSlotPerBead);
};

Comma-separated list of number of beads per slot:<br/>
<input id="input" size="40" value="3,0,1,0,1,0,2,2,2,1,1,0,1,0">
<button id="randomize">Randomize</button><br/>
<button id="calculate">Find optimal spread</button></br>
<pre id="output"></pre>

这段代码接受一个数组，每个索引代表一个插槽，值代表该插槽中珠子的数量。它输出原始数组、可选方案平方和以及珠子移动列表。

问题示例的输出为：

Input: [3,0,1,0,1,0,2,2,2,1,1,0,1,0]
Sum of squares of moves: 60
Sum of moves: 26
Moves[slot][bead]: [[1,2,3],[],[2],[],[1],[],[0,1],[1,2],[2,3],[3],[3],[],[2],[]]

因此，对于示例配置的答案是：60美元。

---

B. 附录：无需顺时针要求

如果去除顺时针移动的要求，移动可以朝任何方向进行，这个问题并没有被提出，但我认为这是一个有趣的变体。

以下是适用于该情况的其他观察结果：

B.1. 可以使用一种解决方案的平方和来计算下一个解决方案

为了找到新配置的平方和，不需要实际执行循环：

假设我们有三个珠子和三个插槽，并且通过将它们分别移动x，y和z个插槽来将珠子移动到目标插槽。例如，如果它们都在插槽0中，我们可以获得0、1、2（甚至-1、0、1或5、6、7，如果我们想夸张）的x，y，z值。

平方和为：

x²+y²+z²

如果现在我们循环这个解决方案，并为每个珠子的移动增加一个插槽，那么方块将变为：

(x+1)²+(y+1)²+(z+1)²

或者：

x²+y²+z²   +3    +2(x+y+z)

通常情况下，像这样循环具有 n 个珠子的配置会增加平方和的值：

n + 2.sum(moves)

因此，该算法可以利用这一点，并快速计算从一个周期得出的解的平方和。这可以在随后的周期中重复进行。

B.2. 平方和只有一个局部最小值

最后，每个连续周期（解决方案）的平方和将是一个抛物线形状的函数，即一旦找到一个局部最小值，就不需要再寻找另一个了；不存在多个局部最小值。我们可以从上面对于sum(moves)增加的公式看出这一点。至多，相邻两个周期可能会有相等的平方和。

B.3. 算法

以下是JavaScript实现的算法：

function optimalSpread(beadCounts) {
    // Initialisation
    var n = beadCounts.length;
    var solution = {
        // Keep track of sum of squares of moves
        // A move is a number of slots and can be negative or positive.
        sumSquares: 0,
        // Keep track of sum of moves.
        sumMoves: 0,
        // Per slot, keep an array with one element per bead, but
        // we start with empty arrays
        movesPerSlotPerBead: [],
    };
    // Build a first a non-optimised solution. 
    // Assign beads in FIFO order to consecutive slots.
    // *move*, when added to the current slot number, identifies the first slot where
    // a bead needs to end up in this solution.
    // =O(n)
    var move = 0,
        totalBeadCount = 0;
    beadCounts.forEach(function(beadCount, slotId) {
        solution.movesPerSlotPerBead[slotId] = [];
        // check sum
        totalBeadCount += beadCount;
        // Move each bead into next available slot
        for (; beadCount > 0; beadCount--, move++) {
            // Store the move for this bead
            solution.movesPerSlotPerBead[slotId].push(move);
            solution.sumMoves += move;
            solution.sumSquares += move*move;
        }
        // Compensate the increment of slotId
        move--;
    });
    // abort if number of beads is not equal to number of slots
    if (totalBeadCount !== n) return {error: "invalid input"}; 
    // See if solution can be improved by shifting all beads in one direction.
    // =O(n)
    bestMoveCorrection = 0;
    while (true) {
        // Improvement is only possible in the direction dictated by sumMoves 
        moveCorrection = (solution.sumMoves < 0 ? 1 : -1);
        // Calculate the delta this brings to sumSquares:
        // (a+1)²+(b+1)²+ ... +(x+1)² = a²+b²+...+x² +n  +2(a+b+...+x) 
        sumSquaresChange = n + moveCorrection * 2 * solution.sumMoves;
        // Stop if this brings no improvement anymore
        if (sumSquaresChange >= 0) break;
        // It is an improvement; keep it
        solution.sumMoves += moveCorrection * n;
        solution.sumSquares += sumSquaresChange;
        bestMoveCorrection += moveCorrection;
    }
    // Apply correction to solution, to make it optimal
    // =O(n)
    solution.movesPerSlotPerBead.forEach(function(moves) {
        moves.forEach(function(move, idx) {
            moves[idx] += bestMoveCorrection;
        });
    });
    return solution;
}

function randomInput(n) {
    // Start with slots having all zero beads:
    beadCounts = Array.from({length: n}, x => 0);
    // Randomly assign beads to slots, keeping a count per slot
    for (var i = 0; i < n; i++) {
        beadCounts[Math.floor(Math.random() * n)]++;
    }
    return beadCounts;
}

// Link with I/O
var input = document.getElementById('input');
var randomize = document.getElementById('randomize');
var calculate = document.getElementById('calculate');
var output = document.getElementById('output');

// Capture events
randomize.onclick = function() {
    var n = 5 + Math.floor(Math.random() * 20);
    input.value = randomInput(n).join(',');
    calculate.onclick();
};

calculate.onclick = function() {
    var beadCounts = input.value.split(',').map(Number);
    var solution = optimalSpread(beadCounts);
    if (solution.error) {
        output.textContent = 'Error: ' + solution.error;
        return;
    }
    output.textContent = 
        '\nInput: ' + JSON.stringify(beadCounts) +
        '\nSum of squares of moves: ' + solution.sumSquares +
        '\nSum of moves: ' + solution.sumMoves +
        '\nMoves[slot][bead]: ' + JSON.stringify(solution.movesPerSlotPerBead);
};

Comma-separated list of number of beads per slot:<br/>
<input id="input" size="40" value="3,0,1,0,1,0,2,2,2,1,1,0,1,0">
<button id="randomize">Randomize</button><br/>
<button id="calculate">Find optimal spread</button></br>
<pre id="output"></pre>

这段代码接收一个数组，其中每个索引表示一个槽位，值表示该槽内珠子的数量。输出原始数组、可选解的平方和以及珠子移动的列表。

对于问题中的示例，输出结果如下：

Input: [3,0,1,0,1,0,2,2,2,1,1,0,1,0]  
Sum of squares of moves: 12  
Sum of moves: -2  
Moves[slot][bead]: [[-1,0,1],[],[0],[],[-1],[],[-2,-1],[-1,0],[0,1],[1],[1],[],[0],[]]

注意：这不是问题的答案，因为它允许逆时针移动。要查看答案，请参见此响应的前半部分。

- trincot

---

这个解决方案非常简洁、快速和优雅。令人惊讶的是，这个问题可以在O(n)时间内解决。我正在考虑这个问题的一个变种，或许你能给我一些思路吗？你不需要再次输入如此惊人、详细的解决方案（但欢迎 :-) ） https://dev59.com/B5Tfa4cB1Zd3GeqPO1Dm - Bob Billy

Answer 2

我在MATLAB中实现了这个。它依赖于与trincot的优秀答案相同的逻辑。在这个实现中，也在O(n)时间内运行，第一步是找到一个空间，其中一个珠子应该保持不动。我还没有证明这总是能得出最优解，但也许我会回来看看。

哦，这段代码还依赖于平方金字塔公式https://en.wikipedia.org/wiki/Square_pyramidal_number。

clear; 
%// inputBps (beads per space) will be our starting point.
%// inputBps=[2 0 3 0 0 0 4 0 1 0 1 0 1 2];
%// inputBps=[2 0 2 0 0 2];
%// inputBps=[1 1 1 1 1];
inputBps=[3 0 1 0 1 0 2 2 2 1 1 0 1 0];

%// This first block of code finds a good place to start.
%// We find a candidate for a bead that should not move.
okStart = 1;
stack = 0;
for i=1:length(inputBps)
    if inputBps(i)>1
        stack = stack + inputBps(i)-1;
    end
    if inputBps(i)==0 && stack<=0
        okStart = i+1;
    end
    if inputBps(i)==0 && stack>0
        stack=stack-1;
    end
end

%// This lets us start at the space we found above.
bps = [inputBps(okStart:end) inputBps(1:okStart-1)];

sum=0;
nextFree=1;
for k=1:length(bps)
    %// firstMoves are the moves that all the beads
    %// in a space have to take because they were "forced out."
    firstMoves = nextFree-k;

    %// Say firstMoves=3 and bps(k)=2. Then our our two beads
    %// moved three spaces and four spaces, like this:
    %// sum = sum + 3^2 + 4^2.  Rewriting:
    %// sum = sum + (1^2 + 2^2 + 3^2 + 4^2) - (1^2 + 2^2)
    sum = sum + squares( bps(k) + firstMoves - 1 ) - squares( firstMoves-1 );

    %// Now calculate the next space that can accept a bead.
    nextFree = nextFree+bps(k);
end

.

function [ y ] = squares( x )
%SQUARES Returns sqaure payramid of input
y = x*(x+1)*(2*x+1) / 6 ;
end

问题的结果如下：

sum =

    60

- wdickerson

---

工作得很好！选择不可移动的珠子确实会导致最优解：（1）最优解至少会留下一个珠子不动，否则通过将所有珠子向前移动一步来获得改进；（2）您通过要求没有珠子向后移动来选择了不可移动的珠子。这对我来说似乎是一个证明（我在我的答案的第3点也有同样的观察）。我进行了一些随机结果的比较，我们的解决方案总是给出相同的结果。使用正方形金字塔是一个不错的优化！ - trincot