algorithm - 如何构造具有任何连续数字的唯一总和的正整数序列？

Question

例如:1,2,4,5 的总和如下:

1,2,4,5

3,6,9

7,11

12

而且每笔金额都是独一无二的。

现在，1,2,3 的总和如下:

1,2,3

3,5

6

而且显然不是每笔金额都是唯一的。

是否有任何有效的方法来生成与第一个示例相似的序列，目标是选择每个数字尽可能小(不仅仅是 1、2、4、8、16 ...)？我知道我可以编写一个程序来暴力破解，但我很好奇是否可以用更好的方式完成。

Answer 1

我认为您在这里寻找的是 Golomb Ruler .如果您将上面描述的数字作为标记之间的距离，那么您就描述了哥伦尺。正如您所描述的，当尺子上的一组标记没有重复时，这就是它成为 Golomb 尺子的原因。

看来描述哥伦布标尺的标准方法是表示每个标记的位置，而不是它们之间的距离。因此，您的 1,2,4,5 将被描述为哥伦尺 0-1-3-7-12。

引用维基百科:

Currently, the complexity of finding OGRs of arbitrary order n (where n is given in unary) is unknown. In the past there was some speculation that it is an NP-hard problem. Problems related to the construction of Golomb Rulers are provably shown to be NP-hard, where it is also noted that no known NP-complete problem has similar flavor to finding Golomb Rulers.