假设你有一个圆圈（如下所示）N点，并且你有N珠子分布在槽中。
Here's an example:
每个珠子都可以顺时针移动X插槽，这需要花费X^2美元。您的目标是最终在每个槽中获得一颗珠子。完成这项任务至少需要花多少钱？
这个问题更有趣的变体：分配珠子难题的算法（2）？ https://stackoverflow.com/questions/35539630/algorithm-for-distributing-beads-puzzle-2
在这个答案中，我假设珠子只能移动一次。否则，显然珠子一次只能移动一格，这使得这个问题变得不那么有趣：平方和将降级为简单的移动总和。
问题可以解决O(n)时间，在第 4 点我给出了一个 JavaScript 实现。如果您想跳过导致该算法的推理，只需滚动到该部分即可。
Edit:我添加了一个部分B，其中分析了问题的变体。
但以下是针对当前问题提出建议算法的观察结果：
应该观察到，在最佳解决方案中，珠子永远不会移动以致一个珠子“超过”另一个珠子。这两个珠子的替代解决方案 交换他们的目标槽位总是会得到较低的平方和。
为了形式化一点，假设一颗珠子从槽号移动a to b，另一个来自c to 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
因此，在开始时共享同一槽的珠子将始终位于最佳解决方案中的相邻槽中。
更普遍：
因此，如果我们给在同一槽中开始的珠子一个（任意）顺序，我们可以说可以找到一个最佳解决方案，其中珠子的顺序与原始输入中的顺序相同（因为排除了超车） ）。
这也意味着我们可以很容易地找到一个候选解决方案，我们可以按订单号拾取珠子并将它们放入具有相同订单号的插槽中。这可能不是最佳解决方案，但有可能是。如果它包含逆时针移动，它甚至可能无效。但作为开始还是很有用的。
通过将所有珠子移动到下一个槽，可以找到保持相同顺序的任何其他潜在解决方案，直到找到有效且最佳的解决方案。我将这样的举动称为循环。
如果第一个候选解因逆时针移动而无效，则可以直接找到最佳解决方案：采取最大的逆时针移动，并将该移动的相反移动添加到所有移动（包括该移动）中。这将使所有有问题的移动都变成非逆时针方向（至少有一个移动为零）。骑得越远显然会使平方和变大。所以这是最优解。
另一方面，如果候选解决方案有效，但没有一个珠子保持在适当的位置，则可以通过相反的方式循环来改进解决方案，即通过使移动更小，直到至少一个珠子保持在适当的位置。
有了上述所有信息，我在这里展示了用 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 美元。
如果取消了顺时针移动的要求，并且可以向任何方向移动怎么办？没有人问这个问题，但我认为这是一个有趣的变体。
以下是适用于该案例的其他观察结果：
不需要实际执行循环即可找到该新配置的平方和：
假设我们有三个珠子和三个插槽，并且每个珠子都通过移动它们移动到了目标插槽x, y and z分别为插槽。例如，如果它们都在槽 0 中，我们可以得到x, y, z值 0、1、2（如果我们想夸大的话，也可以是 -1、0、1，甚至 5、6、7）。
平方和为：
x²+y²+z²
如果现在我们循环这个解决方案，从而为每个珠子的移动添加一个槽，那么方块将变为：
(x+1)²+(y+1)²+(z+1)²
or:
x²+y²+z² +3 +2(x+y+z)
一般来说，循环具有 n 个珠子的配置会增加此项的平方和：
n + 2.sum(moves)
因此，该算法可以利用这一点并快速计算循环所得解的平方和。这可以在后续循环中重复。
最后，每个连续循环（解）的平方和将是一个具有抛物线形状的函数，即一旦找到局部最小值，就无需寻找另一个局部最小值；没有。从上面的增加值的公式我们可以看出sum(moves)。最多两个相邻周期的平方和可能相等。
下面是用 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],[]]
注意：这不是问题的答案，因为它允许逆时针移动。有关答案，请参阅此回复的前半部分。