过滤不包含所有类型元素的组的有效方法

Question

我有一个这样的 3 个数组：

var blues = new int[] {10, 100, 200};
var reds = new int[] {50, 105, 150};
var greens = new int[] {80, 110, 250};

每个数字表示水平线上的一个点。

如果我将所有内容都放在一个数组中，它将如下所示：

{ 10, 50, 80, 100, 105, 110, 150, 200, 250}
  b   r   g   b    r    g    r    b    g
              | group 1 |

我需要找到组，其中每组有三种颜色[蓝色和红色和绿色]，而组中的项目之间的距离之间不大于20blue和red，而不是在大于25red和green。

这种算法有已知的名称吗？如果是这样，那是什么？

在 C# 中实现此算法的最佳方法是什么？

该算法需要考虑以下几点：

1. 可以在 1 到 1000 种颜色之间

2. 颜色是有顺序的，每种颜色必须按照指定的最大距离与前面的颜色足够接近

3. 到前一个颜色的距离可以是正数或负数，除非明确说明距离必须是正数

4. 每种颜色都有自己独特的最大距离，可以远离它前面的颜色

5. 每种颜色的点数在 1 到 100 万之间，并且每种颜色可以不同。

6. 每个组都必须包含所有颜色，除非明确说明可选的特定颜色，或者声明组中包含 40% 或 60% 的颜色就足够了，等等。

我试图像这样实现它：

class ColorPoints
{
    public string Name; // the color name

    public int[] Points;

    public int MaxDistance;

    public bool CanBeNegativeDistance;

    public int[] FinalPoints; // Points that did not fall out of the group
}

public static void GetFinalPoints(ColorPoints[] colorPoints)
{
    if (colorPoints.Length == 1)
    {
        colorPoints[0].FinalPoints = colorPoints[0].Points;
    }

    // ....
}

在上面的测试数据中，预期的结果是100 105 110是一个很好的组，其他所有的点都在该组之外，被取消资格。

使用此算法的一个示例可能是在文本搜索中。如果用户想搜索N个不同的词，词之间的距离不超过X。这叫W/N operator——N字以内，看这里。

这是一个处理主题的项目，并且有一个算法，但它只适用于两种颜色。

这是另一个例子：

var blues = new int[] {10, 20, 100, 200};
var reds = new int[] {50, 105, 150};
var greens = new int[] {80, 110, 250};


{ 10, 20, 50, 80, 100, 105, 110, 150, 200, 250}
  b   b   r   g   b    r    g    r    b    g
                  | group 1 |

在这个例子中，我在蓝色中添加了 20，它说明了每种颜色可以有不同数量的项目。

另一个澄清，要创建所有颜色的水平线，只需从所有颜色中取出所有数字并对其进行排序，并记住每个数字属于哪种颜色。并且只有在所有数字都按升序排序之后，您才能开始按距离和其他标准查找组。

另一个澄清2，组内的顺序无关紧要，我提到的颜色红蓝绿这只是一个例子，可以是世界上任何颜色也可以是白色和任何颜色。

编辑

在 Konstantin Borisov 问题之后，我删除了要求 6 的一部分。现在我想有可能带来更快更好的算法。

负距离示例：

var blues  = new int[] {10, 105, 200};
var reds   = new int[] {50, 100, 150};
var greens = new int[] {80, 110, 250};


{ 10, 50, 80, 100, 105, 110, 150, 200, 250}
  b   r   g   r    b    g    r    b    g
              | group 1 |

在这个例子中，blue是第一个和red第二个，但它们之间的距离可以是负数，所以即使blue是 105 和red100，他们也可以加入一个组，然后green在 25 以内red。

此外，在我的第一个示例中，如果我们允许red和之间的负距离，green那么80 100 105将是一个有效的组。

Answer 1

我不是 C# 程序员。

但如果你想找到所有这样的组，你FinalPoints应该被替换为看起来更像这样的东西：

class PointOptions
{
    public int Point;
    public int[] PreviousPointIndexes;
}
class ColorPoints
{
    public string Name; // the color name
    public int[] Points;
    public int MaxDistance;
    public bool CanBeNegativeDistance;
    public PointOptions[] FinalPointsWithOptions;
}     

现在，您FinalPointsWithOptions使用第一种颜色的每个点和一个空的来初始化第一个PointOptionIndexes。

然后，依次针对每种颜色，遍历其点，扫描前一种颜色FinalPointsWithOptions以查找每个点，以前的选项可以作为此选项的选项。该逻辑看起来像这样的伪代码：

Lower = 0
for Point in ThisColor.Points:
    while PrevColor.PointOptionIndexes[Lower].Point is too small:
        Lower++
        if Lower = PrevColor.PointOptionIndexes.length:
            break
    if Lower = PrevColor.PointOptionIndexes.length:
        break
    i = Lower
    Options = []
    while PrevColor.PointOptionIndexes[i].Point exists and is not too large:
        options.append(i)
    if 0 < options.length:
        ThisColor.PointOptionIndexes.append(PointOptions(Point, Options))

现在，PointOptionIndexes从最后一种颜色开始就像一个向后的链接列表，每条向后的路径都会给你另一个组。

现在您可以对它们进行计数、返回它们、全部生成它们或随机采样它们。（可以有很多组。）