algorithm - 将一组数字划分为序列？查找通用术语？

Question

我们如何将一组数字划分为序列？并找到通用术语？

1 - 数字总是有序的

2 - 如果我们有 n 个数字，则总是存在 n/2 个数字

例如我们有:

Input: 0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30
Output--> 2*X, x=[0..15]

或

Input: 0,2,4,5,6,8,10,12,14,15,16,18,20,22,24,26,28,30

分成两组

A: 0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30

B: 5,10,15,20

Output--> 2*X, x=[0..15] AND 5*X, x=[1..4]

我觉得这很难，有什么意见吗？

什么计算机领域或算法可以帮助我？

Answer 1

我理解的问题是这样的:给定一个数字序列，找到从零开始并以覆盖该集合的常数倍增加的序列集。

以下是我将要执行的操作的大纲:

我会列出集合中的所有数字，并从前两个元素开始迭代，以生成满足您的标准的所有可能集合，这些集合在此处。如果您在列表中遇到一个元素，您可以将其作为生成数字从考虑中删除，因为任何将该数字作为常量倍数的列表都是您之前遇到的列表的子集。完成后，您将获得可用于覆盖该集合的可能集合的列表。例如:

0,2,4,5,6,8,10,12,14,15,16,18,20,22,24,26,28,30

我们将从 0 和 2 开始。我们将寻找连续大于 2 的元素，并将它们从将被视为可能倍数的元素列表中删除。一旦我们找到不在此列表中的 2 的倍数，我们将停止生成。我们开始吧:

s(2) = [0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30]

哪个叶子:

[5,15] 

作为另外两个潜在的候选人。您是否看到任何可被 2 整除的元素(例如 4)将构成该列表的子集，因此不需要考虑？

集合中的剩余列表将从 0 开始并增加 5，我们的最小元素:

[0,5,10,15,20]

(请记住，我们正在检查这些倍数的原始列表而不是截断列表 - 截断列表只是剩余候选列表。当候选列表为空时，我们知道我们将找到包含的所有集合在这个集合中谁没有超集。

更复杂的例子:

[0 2 3 4 5 6 7 8 9 10 12 13 14 15]

我们将从:

开始

[0 2 4 6 8 10 12 14]

哪个离开 [3 5 7 9 13 15]

作为候选人，这反过来会产生:

[0 3 6 9 12 15]

离开

[5 7 13]

产生

[0 5 10 15]

离开

[7 13]

产生

[0 7 14]

离开

[13]

产生

[0 13].

集合的总组合是:

[0 2 4 6 8 10 12 14]
[0 3 6 9 12 15]
[0 5 10 15]
[0 7 14]
[0 13].

此时，您拥有覆盖您的集合所需的所有集合的最小列表。从这里生成适当的 [0,1...n]/a*n 描述符应该是微不足道的。