有一条笔直的道路，有“n”个里程碑。您将获得一个数组，其中包含以某种随机顺序排列的所有里程碑对之间的距离。找到里程碑的位置。
例子：
考虑一条有 4 个里程碑 (a,b,c,d) 的道路：
a ---3Km--- b ---5Km--- c ---2Km--- d
a 和 b 之间的距离为 3
a 和 c 之间的距离为 8
a 和 d 之间的距离为 10
b 和 c 之间的距离为 5
b 和 d 之间的距离为 7
c 和 d 之间的距离为 2
所有上述值都以随机顺序给出，例如 7、10、5、2、8、3。
输出必须是 3、5、2 或 2、5、3。
假设给定数组的长度为n。我的想法是：
这个问题有更好的解决方案吗？
我找不到具有良好最坏情况行为的算法。但是，以下启发式方法可能对实际解决方案有用：
a和b是两个可能的地标位置，则要么|a-b|出现在输入数组中，要么至少出现其中一个a并且b不是地标位置。如果出现在输入数组中，则在a和之间画一条边。b|a-b|你最终会遇到一些几乎是一个派系发现问题的东西。找到一个适当大的集团；它对应于地标的定位。检查此定位是否确实产生了正确的距离。
在最坏的情况下，您已将可能的地标位置缩小到更易于管理的集合。
编辑见下面的新实现（有时间）。
关键思想如下：
0里程碑在max(distances)。让我们称它们为端点。以下 Python 程序仅检查是否可以从左端点放置里程碑，如果不能，则尝试从右端点放置里程碑（始终使用已放置的里程碑未考虑的最大距离）。这必须通过回溯来完成，因为之后展示位置可能会出错。
请注意，还有另一个（镜像）解决方案未输出。（我认为不能有超过 2 个解决方案（对称），但我还没有证明它。）
我将里程碑的位置视为OP 所需的输出solution并使用辅助函数。steps
from collections import Counter
def milestones_from_dists(dists, milestones=None):
if not dists: # all dist are acounted for: we have a solution!
return milestones
if milestones is None:
milestones = [0]
max_dist = max(dists)
solution_from_left = try_milestone(dists, milestones, min(milestones) + max_dist)
if solution_from_left is not None:
return solution_from_left
return try_milestone(dists, milestones, max(milestones) - max_dist)
def try_milestone(dists, milestones, new_milestone):
unused_dists = Counter(dists)
for milestone in milestones:
dist = abs(milestone - new_milestone)
if unused_dists[dist]:
unused_dists[dist] -= 1
if unused_dists[dist] == 0:
del unused_dists[dist]
else:
return None # no solution
return milestones_from_dists(unused_dists, milestones + [new_milestone])
def steps(milestones):
milestones = sorted(milestones)
return [milestones[i] - milestones[i - 1] for i in range(1, len(milestones))]
示例用法：
>>> print(steps(milestones_from_dists([7, 10, 5, 2, 8, 3])))
[3, 5, 2]
>>> import random
>>> milestones = random.sample(range(1000), 100)
>>> dists = [abs(x - y) for x in milestones for y in milestones if x < y]
>>> solution = sorted(milestones_from_dists(dists))
>>> solution == sorted(milestones)
True
>>> print(solution)
[0, 10, 16, 23, 33, 63, 72, 89, 97, 108, 131, 146, 152, 153, 156, 159, 171, 188, 210, 211, 212, 215, 219, 234, 248, 249, 273, 320, 325, 329, 339, 357, 363, 387, 394, 396, 402, 408, 412, 418, 426, 463, 469, 472, 473, 485, 506, 515, 517, 533, 536, 549, 586, 613, 614, 615, 622, 625, 630, 634, 640, 649, 651, 653, 671, 674, 697, 698, 711, 715, 720, 730, 731, 733, 747, 758, 770, 772, 773, 776, 777, 778, 783, 784, 789, 809, 828, 832, 833, 855, 861, 873, 891, 894, 918, 952, 953, 968, 977, 979]
>>> print(steps(solution))
[10, 6, 7, 10, 30, 9, 17, 8, 11, 23, 15, 6, 1, 3, 3, 12, 17, 22, 1, 1, 3, 4, 15, 14, 1, 24, 47, 5, 4, 10, 18, 6, 24, 7, 2, 6, 6, 4, 6, 8, 37, 6, 3, 1, 12, 21, 9, 2, 16, 3, 13, 37, 27, 1, 1, 7, 3, 5, 4, 6, 9, 2, 2, 18, 3, 23, 1, 13, 4, 5, 10, 1, 2, 14, 11, 12, 2, 1, 3, 1, 1, 5, 1, 5, 20, 19, 4, 1, 22, 6, 12, 18, 3, 24, 34, 1, 15, 9, 2]
新的实施并入评论中的建议
from collections import Counter
def milestones_from_dists(dists):
dists = Counter(dists)
right_end = max(dists)
milestones = [0, right_end]
del dists[right_end]
sorted_dists = sorted(dists)
add_milestones_from_dists(dists, milestones, sorted_dists, right_end)
return milestones
def add_milestone
s_from_dists(dists, milestones, sorted_dists, right_end):
if not dists:
return True # success!
# find max dist that's not fully used yet
deleted_dists = []
while not dists[sorted_dists[-1]]:
deleted_dists.append(sorted_dists[-1])
del sorted_dists[-1]
max_dist = sorted_dists[-1]
# for both possible positions, check if this fits the already placed milestones
for new_milestone in [max_dist, right_end - max_dist]:
used_dists = Counter() # for backing up
for milestone in milestones:
dist = abs(milestone - new_milestone)
if dists[dist]: # this distance is still available
dists[dist] -= 1
if dists[dist] == 0:
del dists[dist]
used_dists[dist] += 1
else: # no solution
dists.update(used_dists) # back up
sorted_dists.extend(reversed(deleted_dists))
break
else: # unbroken
milestones.append(new_milestone)
success = add_milestones_from_dists(dists, milestones, sorted_dists, right_end)
if success:
return True
dists.update(used_dists) # back up
sorted_dists.extend(reversed(deleted_dists))
del milestones[-1]
return False
def steps(milestones):
milestones = sorted(milestones)
return [milestones[i] - milestones[i - 1] for i in range(1, len(milestones))]
0 到 100000 范围内的随机里程碑的计时：
n = 10: 0.00s
n = 100：0.05s
n = 1000：3.20 秒
n = 10000：仍然需要很长时间。
给定距离集中的最大距离是第一个和最后一个里程碑之间的距离，即在您的示例 10 中。您可以在 O(n) 步骤中找到它。
对于每个其他里程碑（除第一个或最后一个之外的每个里程碑），您可以通过查找总和为最大距离的一对距离来找到它们与第一个和最后一个里程碑的距离，即在您的示例中 7+3 = 10, 8+2 = 10。你可以在 O(n^2) 中轻松找到这些对。
现在，如果您认为道路是从东到西，剩下的就是对于所有内部里程碑（除了第一个或最后一个），您需要知道两个距离中的哪一个（例如 7 和 3，或 8 和2）向东（另一个向西）。
您可以在 O(2^(n-2)) 时间内简单地枚举所有可能性，并针对每个可能的方向检查您是否获得与问题中相同的一组距离。这比枚举集合中最小距离的所有排列要快。
例如，如果假设 7 和 8 朝西，则两个内部里程碑之间的距离为 1 英里，这不在问题集中。所以它必须是 7 向西，8 向东，导致解决方案（或它的镜子）
WEST | -- 2 -- | -- 5 -- | -- 3 -- | EAST
对于更大的里程碑集，您只需开始猜测到端点的两个距离的方向，并且每当您生成两个里程碑之间的距离不在问题集中的距离时，您就会回溯。
好的。我会给出我的想法，这可以减少排列的数量。
找到 n 很简单，您甚至可以运行反向阶乘https://math.stackexchange.com/questions/171882/is-there-a-way-to-reverse-factorials
假设： 目前我不知道如何找到数字。但我假设你已经以某种方式找到了这些数字。在找到 n 和元素后，我们可以将其应用于部分减少计算。
考虑一个问题，例如，
|<--3-->|<--6-->|<--1-->|<--7-->|
A B C D E
现在正如您所说，他们将给出的总和（也以随机顺序）3,9,10,17,6,7,14,1,8,7。
但是你可以采取任何组合（大多数情况下是错误的），
6-3-1-7. (say this is our taken combination)
Now,
6+3 -> 9 There, so Yes //Checking in the list whether the 2 numbers could possibly be adjacent.
3+1 -> 4 NOT THERE, so cannot
1+7 -> 8 There, So Yes
6+7 -> 13 NOT THERE, So cannot be ajacent
心理念：
因为，要相邻的 2 个数字，它们的总和必须在列表中。如果总和不在列表中，则数字不相邻。
优化 ：
所以，3和1不会靠近。而且6和7不会靠近。
因此，在进行排列时，我们可以消除
*31*,*13*,*76* and *67*组合。其中 * 是 0 个或多个前面或后面的数字。
即，而不是尝试排列 4！= 24 次，我们只能检查 3617,1637,3716,1736。即只有4次。即节省了 84% 的计算量。
最坏的情况下 ：
假设你的情况是 5,2,3。现在，我们必须执行这个操作。
5+2 -> 7 There
2+3 -> 5 There
5+3 -> 8 There
糟糕，您的示例是最坏的情况，在这种情况下我们无法优化解决方案。