c# - 过滤不包含所有类型元素的组的有效方法
问题描述
我有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 |
我需要找到组，其中每组有三种颜色[蓝色和红色和绿色]，并且组中的项目之间的距离在和之间不大于20 ，并且在blue和之间red不大于25 。redgreen
这种算法有已知的名称吗？如果是这样，那是什么？
在 C# 中实现此算法的最佳方法是什么？
该算法需要考虑以下几点：
可以是 1 到 1000 种颜色
颜色是有顺序的，每个颜色都必须按照规定的最大距离与前面的颜色足够接近
到前一个颜色的距离可以是正数也可以是负数，除非明确说明距离必须是正数
每种颜色都有自己独特的最大距离，可以远离它前面的颜色
每种颜色的点数在 1 到 100 万之间，并且每种颜色都可以不同。
每个组必须包含所有颜色
，除非明确说明可选的特定颜色，或者说明在组中有 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。
此外，在我的第一个示例中，如果我们允许 和 then 之间的距离为负数red，green那么80 100 105它将是一个有效的组。
解决方案
由于有关于负距离处理的附加信息，该算法被完全重新设计以使用递归。
一些注意事项：
- 随着点数的增长，它的速度非常快。时间复杂度受 sortig 限制（非常快，O(ln*log n)）；
- 距离会显着影响性能。如果您有覆盖整个阵列的距离，那么您将需要检查所有点组合。这是没有办法的。希望不是这样，而且这些团体有点紧凑。
- 我添加了 100 万种随机 RGB 颜色，它在我的桌面上工作了 30 秒；
class Program
{
class ColorPoints
{
public string Name; // the color name
public int[] Points;
public int MaxDistance;
public bool CanBeNegativeDistance;
}
class IndexesRange
{
public int indexMin { get; set; }
public int indexMax { get; set; }
}
class Item
{
public string Color { get; set; }
public int Number { get; set; }
}
class GroupFinder
{
public List<Item[]> groups { get; set; } = new List<Item[]>();
Item[] array;
List<ColorPoints> colors;
public GroupFinder()
{
Random rnd = new Random();
var blues = /*Enumerable.Range(0, 333333).Select(s => rnd.Next(1000000)).ToArray();*/new int[] { 10, 20, 100, 200 };
var reds = /*Enumerable.Range(0, 333333).Select(s => rnd.Next(1000000)).ToArray();*/ new int[] { 50, 105, 150/*,76,82*/ };
var greens = /*Enumerable.Range(0, 333333).Select(s => rnd.Next(1000000)).ToArray();*/ new int[] { 80, 110, 250/*,79,81*/ };
colors = new List<ColorPoints>();
colors.Add(new ColorPoints() { Name = "Blue", Points = blues });
colors.Add(new ColorPoints() { Name = "Red", Points = reds, MaxDistance = 20, CanBeNegativeDistance = true });
colors.Add(new ColorPoints() { Name = "Green", Points = greens, MaxDistance = 25, CanBeNegativeDistance = true });
// Transform input in a one-array form
array = colors.SelectMany(sm => sm.Points.Select(s => new Item() { Color = sm.Name, Number = s })).OrderBy(o => o.Number).ToArray();
//Console.WriteLine("{0}", string.Join(",", array.Select(s => s.Color[0]+s.Number.ToString())));
}
public void FindGroups()
{
var index = 0;
while (index < array.Length)
{
if (array[index].Color == colors[0].Name) // Finde the firtst color
{
var curColor = 0;
IndexesRange range = GetIndexesRange(index, curColor);
for (var i = range.indexMin; i <= range.indexMax; i++)
{
ProcessColor(curColor + 1, i, new List<Item>() { array[index] });
}
}
index++;
}
}
public void ProcessColor(int curColor, int index, List<Item> currentGroup)
{
if (array[index].Color == colors[curColor].Name)
{
currentGroup.Add(array[index]);
if (curColor < colors.Count - 1)
{
IndexesRange range = GetIndexesRange(index, curColor);
for (var i = range.indexMin; i <= range.indexMax; i++)
{
ProcessColor(curColor + 1, i, currentGroup);
}
}
else
{
groups.Add(currentGroup.ToArray());
currentGroup.RemoveAt(colors.Count - 1); // Remove the last color since we are moving backward now
return;
}
}
}
/// <summary>
/// Get the possible indexes for the next color.
/// </summary>
/// <param name="index">Current index.</param>
/// <param name="curColor">Current color index.</param>
/// <returns></returns>
private IndexesRange GetIndexesRange(int index, int curColor)
{
var range = new IndexesRange();
// Search for the left side of the indexes range
range.indexMin = index;
var nextColor = colors[curColor + 1];
if (nextColor.CanBeNegativeDistance) // The next color might be bofore this one
{
while (range.indexMin > 0 && array[index].Number - array[range.indexMin].Number <= nextColor.MaxDistance)
{
range.indexMin--;
}
}
else
{
range.indexMin++;
}
range.indexMin++; // We found an element which is already doesn't fit and we need the leftest possible
// Search for the right side of the indexes range
range.indexMax = index;
while (range.indexMax < array.Length && array[range.indexMax].Number - array[index].Number <= nextColor.MaxDistance)
{
range.indexMax++;
}
range.indexMax--; // We found an element which is already doesn't fit and we need the rightest possible
return range;
}
}
static void Main(string[] args)
{
Stopwatch sw = new Stopwatch();
sw.Start();
var groupFinder = new GroupFinder();
groupFinder.FindGroups();
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds/1000);
foreach (var group in groupFinder.groups)
Console.WriteLine(string.Join(",", group.Select(s => $"{s.Color}{s.Number}")));
Console.WriteLine("Done!");
}
}
推荐阅读
- javascript - 单击javascript中的两个不同单选按钮时如何显示不同的消息？
- python - Django 身份验证 LDAP
- python - 用于 Python 的 SGE 数组作业从循环中获取输入
- java - 用 Java 替换 AVI 中的帧
- android - 在 Unity 3d 中从图库中选择图像和视频
- r - How to remove multiple columns from a dataframe with column list
- python - TensorFlow Ai 没有进展，gym breakout-ram-v4
- openmdao - 从记录器停止的位置和迭代次数重新开始
- r - 从某个时间范围内的最高先前值中减去一个值，以 r 为单位
- python - 根据数据框之间的距离和 id 创建数据框