Menu
I have a 3 arrays like this:
var blues = new int[] {10, 100, 200};
var reds = new int[] {50, 105, 150};
var greens = new int[] {80, 110, 250};
Each number indicates a point across a horizontal line.
And if I put everything in one array it will look like this:
{ 10, 50, 80, 100, 105, 110, 150, 200, 250}
b r g b r g r b g
| group 1 |
I need to find groups, in which each group has three colors [both blue and red and green], and the distance between the items in the group is not greater than 20 between blue and red, and not greater than 25 between red and green.
Is there a known name for such algorithm? And if so what is it?
And what is the best way to implement this algorithm in C#?
The algorithm needs to consider a few things:
Can be between 1 and a thousand colors
There is an order of colors, and each color must be close enough to the color in front of it according to the maximum distance specified
The distance to the preceding color can be positive or negative, unless it is explicitly stated that the distance must be positive
Each color has its own unique maximum distance that can be far from the color in front of it
The count of points in each color is between 1 and a million, And can be different in each color.
Each group must contain all the colors, unless explicitly stated about a particular color that is optional,
Or it was stated that it is enough to have 40 percent of the colors in the group or 60 percent, etc.
I tried to implement it like this:
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;
}
// ....
}
In the above test data the expected result is that 100 105 110 are a good group, and all other points fall out of the group and are disqualified.
An example of using this algorithm could be in a text search.
If the user wants to search for N different words, when between words there is no more than X distance. This is called W/N operator - within N words, See here.
Here is a project that deals with the subject, and has an algorithm, but it is only suitable for two colors.
Here is another example:
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 |
In this example I added 20 to the blues, it illustrates that each color can have a different number of items.
Another clarification, to create the horizontal line of all the colors together, just take all the numbers from all the colors and sort them, and just remember each number to which color it belongs. And only after all the numbers are sorted in ascending order, only then do you start looking for groups by distances and other criteria.
Another clarification 2, order within the group does not matter, the colors I mentioned red blue and green this is just an example can be any color in the world also white and any color.
Following Konstantin Borisov question I deleted part of the requirement 6. Now I guess it will be possible to bring an algorithm much faster and better.
Example of a negative distance:
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 |
In this example, blue is first and red is second, but the distance between them can be negative, so even though blue is at 105 and red at 100 they can join one group, then have green within 25 of red.
Also, in my first example, if we allow a negative distance between red and green then 80 100 105 would be a valid group.
652
Let me first restate the problem in a more mathematical formulation, while at the same time also slightly generalizing it in a natural way (in the following I use '_' to designate indices; unfortunately SO lacks good support for typing formulas):
Let C_1, ... , C_M be finite subsets of the integers. Let I_2, ... , I_M be integer intervals, i.e. I_j = [a_j, b_j] with a_j <= b_j (all integers). Furthermore, let a real number p in [0, 1] be given.
The task is to find an efficient algorithm to determine the set of groups {G = (c_k_1, ... , c_k_N) | k_1 < ... < k_N are positive integers, c_k_j is an element of C_k_j for all j, c_k_(j+1) - c_k_j is contained in I_(j+1) for all j = 1, ... , N - 1, N >= pM}.
From a mathematical perspective we may assume without loss of generality that p = 1 and hence M=N (as we can solve the problem in turn for all subsets of the color space with N elements and N >= pM).
The algorithm that I propose is very simple: Consider all possible combinations (c_k_1, ... , c_k_M) and test whether they fullfill the desired properties.
Is this algorithm efficient? Certainly there are more efficient algorithms. But the question in practice is not whether we have found the most efficient possible algorithm/implementation (which is hardly ever available), but rather whether it is efficient enough for the given task. Let me add a few further thoughts:
The problem has the unpleasant property that the complexity grows hyperexponentially with the size of the inputs. In the worst case, when the distances are large enough, all combinations are solutions. In the case of 1000 colors with 1 million points each this amounts to (10^6)^1000 = 10^6000 groups. No implementation will ever be able to cope with these numbers (the number of atoms in the universe is estimated to be 10^80). So, every algorithm has its limits with respect to practicable execution (and the limits are pretty small compared to the boundaries given in the question). Given an algorithm, is it worth the effort improving it by, say, a factor of 1000? If you are very lucky, yes, but the odds are against that the the problem you are looking at is exactly in the very small area between the limits of the weaker and the stronger algorithm.
So, my claim is that the naive algorithm proposed above is efficient enough. It definitively is efficient enough to solve the examples in the question in next to no time. My implementation solves the following slight extension of the examples almost instantly:
The colors:
Blue: 10, 20, 100, 200
Red: 50, 105, 150
Green: 80, 110, 250
Yellow: 42, 62, 82, 102, 122, 142, 162The distances:
From red: [0,20]
From green: [0,25]
From yellow: [0,25]2 colors may be skipped.
The groups:
B: 100, R: 105
B: 100, G: 110
B: 20, Y: 42
B: 100, Y: 102
B: 100, Y: 122
R: 105, G: 110
R: 50, Y: 62
R: 105, Y: 122
R: 150, Y: 162
G: 80, Y: 82
G: 80, Y: 102
G: 110, Y: 122
B: 100, R: 105, G: 110
B: 100, R: 105, Y: 122
B: 100, G: 110, Y: 122
R: 105, G: 110, Y: 122
B: 100, R: 105, G: 110, Y: 122
You can find the full implementation at Arlofin/SO_ColourGroups. In the following I sketch the essentials.
public class Interval
{
public int LowerBound { get; }
public int UpperBound { get; }
// Details elided
}
public class Color
{
private readonly int[] _points;
public IReadOnlyCollection<int> Points => _points;
public Interval Distance { get; }
public string Name { get; }
// Details elided
}
public struct ColorPoint
{
public int Value { get; }
public Color Color { get; }
// Details elided
}
public class ProblemSpecification
{
private readonly Color[] _colors;
public IReadOnlyCollection<Color> Colors => _colors;
public double Fraction { get; }
// Details elided
}
public class Group
{
private readonly ColorPoint[] _elements;
public IReadOnlyCollection<ColorPoint> Elements => _elements;
// Details elided
}
public static class SetOperations<T>
{
public static IEnumerable<T[]> CrossProduct(IEnumerable<IEnumerable<T>> sets)
{
// Details elided
}
public static IEnumerable<T[]> SubSets(IReadOnlyCollection<T> set, int cardinality)
{
// Details elided
}
}
public static class ProblemSolver
{
private static bool IsGroupValid(Group group)
{
return group.Elements.Zip(group.Elements.Skip(1), (pre, el) => el.Color.Distance.Contains(el.Value - pre.Value)).All(b => b);
}
private static IEnumerable<Group> NaiveSolverFull(IEnumerable<Color> colors)
{
var colourPointsPerColor = from color in colors
select color.Points.Select(colorValue => new ColorPoint(colorValue, color));
var groupCandidates = from colorPointCombination in SetOperations<ColorPoint>.CrossProduct(colourPointsPerColor)
select new Group(colorPointCombination);
return groupCandidates.Where(group => IsGroupValid(group));
}
public static IEnumerable<Group> NaiveSolver(ProblemSpecification spec)
{
int minimalNumberOfColors = (int)Math.Ceiling(spec.Fraction * spec.Colors.Count);
return Enumerable.Range(minimalNumberOfColors, spec.Colors.Count - minimalNumberOfColors + 1)
.SelectMany(n => SetOperations<Color>.SubSets(spec.Colors, n)
.SelectMany(NaiveSolverFull));
}
}
Since there is additional information about the negative distance processing the algorithm is completeley reworked for using recursion.
Some notes:
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!");
}
}
Provided 2 approaches. First approach is simply Brute Force using recursion. Second approach uses some graph theory and implements a Depth-First search algorithm.
Edit: Added a 'sliding window' to the brute force approach to skip some unnecessary iterations. Edit2: Created second Graphed approach using a Depth-First search algorithm.
using System;
using System.Collections.Generic;
using System.Linq;
namespace Color_Finder
{
class Program
{
static void Main(string[] args)
{
//int[] blues = new int[] { 10, 105, 200 };
//int[] reds = new int[] { 50, 100, 150 };
//int[] greens = new int[] { 80, 110, 250 };
//int[] yellows = new int[] { 0, 10, 101 };
bool IsNegativeDistance = true;
////FindGroup finder = new FindGroup_Windowed();
//FindGroup finder = new FindGroup_Linked();
//finder.AddColor("Blue ", 20, IsNegativeDistance, blues);
//finder.AddColor("Red ", 25, IsNegativeDistance, reds);
//finder.AddColor("Green ", 10, IsNegativeDistance, greens);
//finder.AddColor("Yellow", 0, IsNegativeDistance, yellows);
FindGroup finder1 = new FindGroup_Windowed();
FindGroup finder2 = new FindGroup_Linked();
Random r = new Random();
int numColors = 6;
int numPoints = 100;
for (int i = 0; i < numColors; i++)
{
List<int> list = new List<int>();
for (int j = 0; j < numPoints; j++)
{
list.Add(r.Next(0, numPoints * 10)); //for ints
}
int maxDist = r.Next(1, 300);
finder1.AddColor($"Color{i.ToString()}", maxDist, IsNegativeDistance, list.ToArray());
finder2.AddColor($"Color{i.ToString()}", maxDist, IsNegativeDistance, list.ToArray());
}
DateTime start = DateTime.Now;
finder1.GetColorGroups();
Console.WriteLine($"Window Time: {DateTime.Now - start}");
DateTime start2 = DateTime.Now;
finder2.GetColorGroups();
Console.WriteLine($"Links Time: {DateTime.Now - start2}");
finder1.Print();
finder2.Print();
Console.WriteLine("done");
Console.ReadKey();
}
public interface FindGroup
{
void AddColor(string Name, int MaxDistanceToNext, bool IsNegativeDistance, int[] Points);
List<List<int>> GetColorGroups();
void Print();
}
//Brute Force approach. Not very elegant, but it works
public class FindGroup_Windowed : FindGroup
{
public FindGroup_Windowed(bool IsVerbose = false)
{
Colors = new List<Color>();
this.IsVerbose = IsVerbose;
}
private List<Color> Colors { get; set; }
private List<List<int>> Groups { get; set; }
private int NumSteps { get; set; }
private bool IsVerbose { get; }
public void AddColor(string Name, int MaxDistanceToNext, bool IsNegativeDistance, int[] Points)
{
Colors.Add(new Color(Name, MaxDistanceToNext, IsNegativeDistance, Points));
}
public List<List<int>> GetColorGroups()
{
NumSteps = 0;
Groups = FindColorGroups(0);
return Groups;
}
public void Print()
{
if (IsVerbose)
{
Console.Write("Colors:\n");
for (int i = 0; i < Colors?.Count; i++)
{
Console.Write($"Name={Colors[i].Name}, MaxDist={Colors[i].MaxDistanceToNext}, Points=[{string.Join(", ", Colors[i].Points)}]\n");
}
Console.Write("\n");
Console.Write("Groups:\n");
for (int i = 0; i < Groups?.Count; i++)
{
for (int j = 0; j < Groups[i].Count; j++)
{
Console.Write(Groups[i][j].ToString());
if (j < Groups[i].Count - 1) Console.Write(", ");
else Console.Write("\n");
}
}
}
Console.Write($"Window: Num Steps taken: {NumSteps}\n");
Console.Write($"Window: Num Groups Found: {Groups.Count}\n");
}
private List<List<int>> FindColorGroups(int colorIndex)
{
if (Colors.Count <= colorIndex) return null;
Color current = Colors[colorIndex];
List<List<int>> ret = new List<List<int>>();
int lowerBoundIndex = 0;
for (int i = 0; i < current.Points.Length; i++)
{
int pointA = current.Points[i];
List<int> group = new List<int>();
group.Add(pointA);
List<List<int>> nextPoints = FindNextColor(colorIndex + 1, group, ref lowerBoundIndex);
if (nextPoints != null) ret.AddRange(nextPoints);
}
if (IsVerbose) Console.Write("\n");
return ret;
}
private List<List<int>> FindNextColor(int colorIndex, List<int> group, ref int lowerBoundIndex)
{
if (Colors.Count <= colorIndex) return null; // found end of complete group :)
List<List<int>> ret = new List<List<int>>();
Color prev = Colors[colorIndex - 1];
Color current = Colors[colorIndex];
int pointA = group.Last();
int nextLowerBoundIndex = 0;
for (int i = lowerBoundIndex; i < current.Points.Length; i++)
{
NumSteps++;
int pointB = current.Points[i];
int dist = pointB - pointA;
if (IsVerbose) Console.WriteLine($"{colorIndex - 1}: {pointA}, {pointB} = {dist}");
int minDist = prev.IsNegativeDistance ? -prev.MaxDistanceToNext : 0;
//points are in ascending order
if (dist < minDist)
{
lowerBoundIndex = i; //set lower end of window. this will slide forward as the prev Color iterates through its points.
}
else if (minDist <= dist && dist <= prev.MaxDistanceToNext)
{
List<int> newGroup = new List<int>(group);
newGroup.Add(pointB);
List<List<int>> nextPoints = FindNextColor(colorIndex + 1, newGroup, ref nextLowerBoundIndex);
if (nextPoints != null) ret.AddRange(nextPoints);
else ret.Add(newGroup); // found end of complete group :)
}
else //if (prev.MaxDistanceToNext < dist)
{
break; //all points past this are going to be to far away too.
}
}
return ret;
}
private class Color
{
public Color(Color color)
{
this.Name = color.Name;
this.MaxDistanceToNext = color.MaxDistanceToNext;
this.IsNegativeDistance = color.IsNegativeDistance;
this.Points = color.Points;
}
public Color(string Name, int MaxDistanceToNext, bool IsNegativeDistance, int[] Points)
{
Array.Sort(Points);
this.Name = Name;
this.MaxDistanceToNext = MaxDistanceToNext;
this.IsNegativeDistance = IsNegativeDistance;
this.Points = Points;
}
public string Name { get; }
public int MaxDistanceToNext { get; }
public bool IsNegativeDistance { get; }
public int[] Points { get; }
}
}
public class FindGroup_Linked : FindGroup
{
public FindGroup_Linked(bool IsVerbose = false)
{
this.Colors = new List<ColorLinked>();
this.IsVerbose = IsVerbose;
}
private List<ColorLinked> Colors { get; set; }
private List<List<int>> Groups { get; set; }
private int NumSteps { get; set; }
private bool IsVerbose { get; }
public void AddColor(string Name, int MaxDistanceToNext, bool IsNegativeDistance, int[] Points)
{
Colors.Add(new ColorLinked(Name, MaxDistanceToNext, IsNegativeDistance, Points));
}
public List<List<int>> GetColorGroups()
{
NumSteps = 0;
//Build links between colors
BuildLinks();
//iterate through links
Groups = FindColorGroups();
return Groups;
}
public void Print()
{
if (IsVerbose)
{
Console.WriteLine("Colors:");
for (int i = 0; i < Colors?.Count; i++)
{
Console.WriteLine($"Name={Colors[i].Name}, MaxDist={Colors[i].MaxDistanceToNext}, Points=[{string.Join(", ", Colors[i]._points)}]");
for (int j = 0; j < Colors[i].Points?.Count; j++)
{
Console.WriteLine($"Value={Colors[i].Points[j].Value}, Next=[{string.Join(", ", Colors[i].Points[j].Next.Select(x => x.Value))}]");
}
}
Console.WriteLine("");
Console.WriteLine("Groups:");
for (int i = 0; i < Groups?.Count; i++)
{
for (int j = 0; j < Groups[i].Count; j++)
{
Console.Write(Groups[i][j].ToString());
if (j < Groups[i].Count - 1) Console.Write(", ");
else Console.Write("\n");
}
}
}
Console.WriteLine($"Links: Num Steps taken: {NumSteps}");
Console.WriteLine($"Links: Num Groups Found: {Groups.Count}");
}
private void BuildLinks()
{
ColorLinked current;
ColorLinked next;
int lowerBoundIndex = 0;
for (int colorIndex = 0; colorIndex < Colors.Count - 1; colorIndex++) //minus 1 because last color has nowhere to go
{
current = Colors[colorIndex];
next = Colors[colorIndex + 1];
lowerBoundIndex = 0;
for (int i = 0; i < current.Points.Count; i++)
{
Point pointA = current.Points[i];
for (int j = lowerBoundIndex; j < next.Points.Count; j++)
{
NumSteps++;
Point pointB = next.Points[j];
int dist = pointB.Value - pointA.Value;
if (IsVerbose) Console.WriteLine($"{colorIndex}: {pointA.Value}, {pointB.Value} = {dist}");
int minDist = current.IsNegativeDistance ? -current.MaxDistanceToNext : 0;
//points are in ascending order
if (dist < minDist)
{
lowerBoundIndex = j; //set lower end of window. this will slide forward as the prev Color iterates through its points.
}
else if (minDist <= dist && dist <= current.MaxDistanceToNext)
{
pointA.Next.Add(pointB);
pointB.Prev.Add(pointA);
}
else //if (prev.MaxDistanceToNext < dist)
{
break; //all points past this are going to be too far away too.
}
}
}
}
if (IsVerbose) Console.WriteLine("");
}
private List<List<int>> FindColorGroups()
{
List<List<int>> ret = new List<List<int>>();
foreach (Point point in Colors[0].Points)
{
List<int> path = new List<int>();
path.Add(point.Value);
List<List<int>> groups = helper(point, path);
if (groups != null) ret.AddRange(groups);
}
return ret;
}
private List<List<int>> helper (Point point, List<int> path)
{
if (point.Next.Count == 0) return null; // found end of grouping
List<List<int>> ret = new List<List<int>>();
foreach (Point next in point.Next)
{
//NumSteps++;
List<int> nextPath = new List<int>(path);
nextPath.Add(next.Value);
List<List<int>> nextGroup = helper(next, nextPath);
if (nextGroup != null) ret.AddRange(nextGroup);
else if(nextPath.Count == Colors.Count) ret.Add(nextPath); // found end of complete group :)
}
return ret;
}
private class ColorLinked
{
public ColorLinked(string Name, int MaxDistanceToNext, bool IsNegativeDistance, int[] Points)
{
Array.Sort(Points);
this.Name = Name;
this.MaxDistanceToNext = MaxDistanceToNext;
this.IsNegativeDistance = IsNegativeDistance;
this._points = Points;
this.Points = new List<Point>();
foreach (var value in Points)
{
this.Points.Add(new Point(value));
}
}
public string Name { get; }
public int MaxDistanceToNext { get; }
public bool IsNegativeDistance { get; }
public int[] _points { get; }
public List<Point> Points { get; }
}
public class Point
{
public Point(int value)
{
this.Prev = new List<Point>();
this.Next = new List<Point>();
this.Value = value;
}
public List<Point> Prev { get; set; }
public List<Point> Next { get; set; }
public int Value { get; set; }
}
}
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
