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.
EDIT
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.