解决这个分配珠子难题的算法？
Algorithm for solving this distributing beads puzzle?
假设您有一个带有 N 个点的圆圈（如下所示），并且您有 N 个珠子分布在插槽中。
举个例子：
每个珠子可以顺时针移动 X 个槽位，花费 X^2 美元。您的目标是在每个插槽中放置一颗珠子。完成这个任务你最少要花多少钱？
这个问题更有趣的变体：Algorithm for distributing beads puzzle (2)?
在这个回答中，我假设珠子只能移动一次。否则很明显，珠子一次只能移动一个方格，这会使这个问题变得不那么有趣：平方和将降级为简单的移动总和。
问题可以在O(n)时间解决，在第4点我给出一个JavaScript实现。如果您想跳过导致算法的推理，只需滚动到该部分。
编辑： 我添加了一个部分 B，其中分析了问题的变体。
但以下是导致针对手头问题的建议算法的观察结果：
1。禁止超车
应该观察到，在最佳解决方案中，珠子永远不会移动，使得一个珠子 "overtakes" 另一个。这两个珠子的替代解决方案
交换他们的目标位置总是会给出较低的平方和。
为了形式化一点，假设一个珠子从槽号 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。循环最优解
只需将所有珠子移动到下一个插槽，即可找到保持相同顺序的任何其他潜在解决方案，直到找到有效且最佳的解决方案。我将这样的举动称为一个循环。
如果第一个候选解因为逆时针走法无效，直接求最优解：取最大的逆时针走法，把这个走法的相反数加到所有的走法中，包括那个。这将使所有违规移动都不是逆时针方向的（至少有一个是零移动）。进一步循环显然会使平方和变大。所以这是最优解。
如果另一方面候选解是有效的，但 none 个珠子留在原位，则可以通过相反的方式循环来改进解，即通过减小移动，直到至少一颗珠子留在原位。
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.1。一个解的平方和可以用于下一个
无需实际执行循环即可找到该新配置的平方和：
假设我们有三个珠子和三个插槽，每个珠子都通过移动 x、y 和 z[ 移动到它们的目标插槽中=129=] 插槽分别。例如，如果它们都在插槽 0 中，我们可以获得 x, y, z 值 0, 1, 2（但也有 -1, 0, 1 甚至 5, 6 , 7 如果我们想夸大）。
平方和为：
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],[]]
注意：这不是问题的答案，因为它允许逆时针移动。答案见本回复前半部分。
我在 MATLAB 中实现了这个。它依赖于与 trincot 的出色答案大致相同的逻辑。在这个同样以 O(n) 时间运行的实现中，第一步是找到一个 space 以从一个珠子应该保持不动的地方开始。我还没有证明这总能找到最佳解决方案，但也许我会回来的。
哦，而且这段代码还依赖于四方金字塔公式
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
假设您有一个带有 N 个点的圆圈（如下所示），并且您有 N 个珠子分布在插槽中。
举个例子：
每个珠子可以顺时针移动 X 个槽位，花费 X^2 美元。您的目标是在每个插槽中放置一颗珠子。完成这个任务你最少要花多少钱？
这个问题更有趣的变体：Algorithm for distributing beads puzzle (2)?
在这个回答中，我假设珠子只能移动一次。否则很明显，珠子一次只能移动一个方格，这会使这个问题变得不那么有趣：平方和将降级为简单的移动总和。
问题可以在O(n)时间解决，在第4点我给出一个JavaScript实现。如果您想跳过导致算法的推理，只需滚动到该部分。
编辑： 我添加了一个部分 B，其中分析了问题的变体。
但以下是导致针对手头问题的建议算法的观察结果：
1。禁止超车
应该观察到，在最佳解决方案中，珠子永远不会移动，使得一个珠子 "overtakes" 另一个。这两个珠子的替代解决方案 交换他们的目标位置总是会给出较低的平方和。
为了形式化一点，假设一个珠子从槽号 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。循环最优解
只需将所有珠子移动到下一个插槽，即可找到保持相同顺序的任何其他潜在解决方案，直到找到有效且最佳的解决方案。我将这样的举动称为一个循环。
如果第一个候选解因为逆时针走法无效，直接求最优解：取最大的逆时针走法，把这个走法的相反数加到所有的走法中，包括那个。这将使所有违规移动都不是逆时针方向的（至少有一个是零移动）。进一步循环显然会使平方和变大。所以这是最优解。
如果另一方面候选解是有效的，但 none 个珠子留在原位，则可以通过相反的方式循环来改进解，即通过减小移动，直到至少一颗珠子留在原位。
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.1。一个解的平方和可以用于下一个
无需实际执行循环即可找到该新配置的平方和：
假设我们有三个珠子和三个插槽，每个珠子都通过移动 x、y 和 z[ 移动到它们的目标插槽中=129=] 插槽分别。例如，如果它们都在插槽 0 中，我们可以获得 x, y, z 值 0, 1, 2（但也有 -1, 0, 1 甚至 5, 6 , 7 如果我们想夸大）。
平方和为：
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],[]]
注意：这不是问题的答案，因为它允许逆时针移动。答案见本回复前半部分。
我在 MATLAB 中实现了这个。它依赖于与 trincot 的出色答案大致相同的逻辑。在这个同样以 O(n) 时间运行的实现中，第一步是找到一个 space 以从一个珠子应该保持不动的地方开始。我还没有证明这总能找到最佳解决方案，但也许我会回来的。
哦，而且这段代码还依赖于四方金字塔公式 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