Modo efficiente per filtrare i gruppi che non contengono tutti i tipi di elementi
Ho 3 array come questo:
var blues = new int[] {10, 100, 200};
var reds = new int[] {50, 105, 150};
var greens = new int[] {80, 110, 250};
Ogni numero indica un punto su una linea orizzontale.
E se metto tutto in un array sarà simile a questo:
{ 10, 50, 80, 100, 105, 110, 150, 200, 250}
b r g b r g r b g
| group 1 |
Ho bisogno di trovare gruppi, in cui ogni gruppo ha tre colori [sia blu che rosso e verde], e la distanza tra gli elementi nel gruppo non è maggiore di 20 tra bluee red, e non maggiore di 25 tra rede green.
Esiste un nome noto per tale algoritmo? E se si cos'è?
E qual è il modo migliore per implementare questo algoritmo in C#?
L'algoritmo deve considerare alcune cose:
Può essere compreso tra 1 e mille colori
Esiste un ordine di colori e ciascun colore deve essere abbastanza vicino al colore che lo precede in base alla distanza massima specificata
La distanza dal colore precedente può essere positiva o negativa, a meno che non sia esplicitamente indicato che la distanza deve essere positiva
Ogni colore ha la sua distanza massima univoca che può essere lontana dal colore di fronte ad esso
Il conteggio dei punti in ciascun colore è compreso tra 1 e un milione e può essere diverso in ciascun colore.
Ogni gruppo deve contenere tutti i colori
, a meno che non sia esplicitamente indicato un colore particolare che è facoltativo, oppure è stato affermato che è sufficiente avere il 40 percento dei colori nel gruppo o il 60 percento, ecc.
Ho provato ad implementarlo in questo modo:
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;
}
// ....
}
Nei dati del test di cui sopra il risultato atteso è che 100 105 110 sono un buon gruppo e tutti gli altri punti escono dal gruppo e vengono squalificati.
Un esempio di utilizzo di questo algoritmo potrebbe essere in una ricerca di testo. Se l'utente vuole cercare N parole diverse, quando tra le parole non c'è più di X distanza. Questo è chiamato W/N operator- all'interno di N parole, Vedi qui .
Ecco un progetto che tratta l'argomento e ha un algoritmo, ma è adatto solo per due colori.
Ecco un altro esempio:
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 questo esempio ho aggiunto 20 al blu, illustra che ogni colore può avere un diverso numero di elementi.
Un'altra precisazione, per creare la linea orizzontale di tutti i colori insieme, basta prendere tutti i numeri da tutti i colori e ordinarli, e ricordare ogni numero a quale colore appartiene. E solo dopo che tutti i numeri sono stati ordinati in ordine crescente, solo allora inizi a cercare gruppi in base a distanze e altri criteri.
Un'altra precisazione 2, l'ordine all'interno del gruppo non ha importanza, i colori che ho citato rosso blu e verde questo è solo un esempio possono essere qualsiasi colore del mondo anche bianco e qualsiasi colore.
MODIFICARE
Seguendo la domanda di Konstantin Borisov ho eliminato parte del requisito 6. Ora immagino che sarà possibile portare un algoritmo molto più veloce e migliore.
Esempio di distanza negativa:
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 questo esempio, blueè il primo ed redè il secondo, ma la distanza tra loro può essere negativa, quindi anche se blueè a 105 ea red100 possono unirsi a un gruppo, quindi avere greenentro 25 di red.
Inoltre, nel mio primo esempio, se permettiamo una distanza negativa tra rede greenallora 80 100 105sarebbe un gruppo valido.
Risposte
Permettetemi prima di riformulare il problema in una formulazione più matematica, mentre allo stesso tempo lo generalizzo leggermente in modo naturale (nel seguito uso '_' per designare gli indici; sfortunatamente SO manca di un buon supporto per le formule di battitura):
Siano C_1, ... , C_M sottoinsiemi finiti degli interi. Siano I_2, ... , I_M intervalli interi, cioè I_j = [a_j, b_j] con a_j <= b_j (tutti interi). Inoltre, sia dato un numero reale p in [0, 1].
Il compito è trovare un algoritmo efficiente per determinare l'insieme dei gruppi {G = (c_k_1, ... , c_k_N) | k_1 < ... < k_N sono interi positivi, c_k_j è un elemento di C_k_j per ogni j, c_k_(j+1) - c_k_j è contenuto in I_(j+1) per ogni j = 1, ... , N - 1, N >= pM}.
Da un punto di vista matematico possiamo assumere senza perdita di generalità che p = 1 e quindi M=N (poiché possiamo risolvere il problema a turno per tutti i sottoinsiemi dello spazio colore con N elementi e N >= pM).
L'algoritmo che propongo è molto semplice: considera tutte le possibili combinazioni (c_k_1, ... , c_k_M) e verifica se soddisfano le proprietà desiderate.
Questo algoritmo è efficiente? Certamente ci sono algoritmi più efficienti. Ma la domanda in pratica non è se abbiamo trovato l'algoritmo/implementazione più efficiente possibile (che non è quasi mai disponibile), ma piuttosto se è abbastanza efficiente per il compito dato. Aggiungo qualche ulteriore considerazione:
Il problema ha la spiacevole proprietà che la complessità cresce in modo iperesponenziale con la dimensione degli input. Nel peggiore dei casi, quando le distanze sono abbastanza grandi, tutte le combinazioni sono soluzioni. Nel caso di 1000 colori con 1 milione di punti ciascuno ciò equivale a (10^6)^1000 = 10^6000 gruppi. Nessuna implementazione sarà mai in grado di far fronte a questi numeri (il numero di atomi nell'universo è stimato in 10^80). Quindi, ogni algoritmo ha i suoi limiti rispetto all'esecuzione praticabile (e i limiti sono piuttosto piccoli rispetto ai limiti indicati nella domanda). Dato un algoritmo, vale la pena migliorarlo, diciamo, di un fattore 1000? Se sei molto fortunato, sì, ma le probabilità sono contro il fatto che il problema che stai osservando si trovi esattamente nell'area molto piccola tra i limiti dell'algoritmo più debole e più forte.
Quindi, la mia affermazione è che l'ingenuo algoritmo proposto sopra è abbastanza efficiente. È definitivamente abbastanza efficiente da risolvere gli esempi nella domanda in pochissimo tempo. La mia implementazione risolve quasi istantaneamente la seguente leggera estensione degli esempi:
I colori:
Blu: 10, 20, 100, 200
Rosso: 50, 105, 150
Verde: 80, 110, 250
Giallo: 42, 62, 82, 102, 122, 142, 162Le distanze:
Dal rosso: [0,20]
Dal verde: [0,25]
Dal giallo: [0,25]2 colori possono essere saltati.
I gruppi:
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, G: 105, G: 110
B: 100, R: 105, Y: 122
SI: 100, G: 110, Y: 122
R: 105, G: 110, Y: 122
SI: 100, R: 105, G: 110, Y: 122
È possibile trovare l'implementazione completa in Arlofin/SO_ColourGroups . Di seguito abbozzerò l'essenziale.
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));
}
}
Poiché ci sono informazioni aggiuntive sull'elaborazione della distanza negativa, l'algoritmo è stato completamente rielaborato per l'utilizzo della ricorsione.
Alcune note:
- È piuttosto veloce in termini di crescita con il numero di punti. La complessità temporale è limitata dall'ordinamento (che è abbastanza veloce, O(ln*log n));
- La distanza può influire in modo significativo sulle prestazioni. Se hai una distanza che copre l'intero array, dovrai controllare tutte le combinazioni di punti. E questo non può essere evitato. Spero che non sia così e che i gruppi siano un po' compatti.;
- Ho aggiunto 1 milione di colori RGB casuali e ha funzionato per 30 secondi sul mio desktop;
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!");
}
}
Fornito 2 approcci. Il primo approccio è semplicemente Brute Force usando la ricorsione. Il secondo approccio utilizza una teoria dei grafi e implementa un algoritmo di ricerca Depth-First.
Modifica: aggiunta una "finestra scorrevole" all'approccio della forza bruta per saltare alcune iterazioni non necessarie. Edit2: creato il secondo approccio grafico utilizzando un algoritmo di ricerca Depth-First.
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; }
}
}
}
}
Ecco una soluzione che utilizza i limiti inferiori precalcolati della ricerca binaria . Ho basato il codice sulla forza bruta di Vargo .
Inoltre, come fase di precalcolo attraverso il backtracking, rimuovo tutti i punti che non possono far parte di un gruppo completo. Questo è necessario per evitare vicoli ciechi. Pertanto, quando ci sono solo pochi gruppi possibili, l'algoritmo non esplora in modo esponenziale molti gruppi possibili.
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 };
bool AbsoluteDistance = true;
FindGroup finder = new FindGroup_BruteForce();
finder.AddColor(new Color("Blue ", 20, AbsoluteDistance, blues));
finder.AddColor(new Color("Red ", 25, AbsoluteDistance, reds));
finder.AddColor(new Color("Green ", 10, AbsoluteDistance, greens));
List<List<int>> groups = finder.GetColorGroups();
finder.Print();
Console.WriteLine("done");
Console.ReadKey();
}
public interface FindGroup
{
void AddColor(Color newColor);
List<List<int>> GetColorGroups();
void Print();
}
public class FindGroup_BruteForce : FindGroup
{
public FindGroup_BruteForce()
{
Colors = new List<Color>();
}
private List<Color> Colors { get; set; }
private List<List<int>> Groups { get; set; }
private int[][] LowerBounds;
public void AddColor(Color newColor)
{
Colors.Add(newColor);
}
public List<List<int>> GetColorGroups()
{
Groups = FindColorGroups();
return Groups;
}
public void Print()
{
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");
}
}
}
private bool InRange(bool AbsoluteDistance, int MaxDist, int p1, int p2)
{
return (AbsoluteDistance && p1 - p2 <= MaxDist && p2 - p1 <= MaxDist)
|| (p1 <= p2 && p2 - p1 <= MaxDist);
}
private bool ExistsInRange(int[] Points, bool AbsoluteDistance, int MaxDist, int p)
{
int lower = AbsoluteDistance ? p - MaxDist : p;
int upper = p + MaxDist;
int lowerIdx = Array.BinarySearch(Points, lower);
if (lowerIdx < 0) lowerIdx = ~lowerIdx;
return lowerIdx < Points.Length && Points[lowerIdx] <= upper;
}
private List<List<int>> FindColorGroups()
{
// Eliminate points that do not connect to any point in the next color
for (int i = Colors.Count - 2; i >= 0; i--)
{
Color c = Colors[i];
Color d = Colors[i + 1];
c.Points = Array.FindAll(c.Points, p1 =>
ExistsInRange(d.Points, c.AbsoluteDistance, c.MaxDistanceToNext, p1));
}
LowerBounds = new int[Colors.Count - 1][];
for (int i = 0; i < Colors.Count - 1; i++)
{
Color c = Colors[i];
Color d = Colors[i + 1];
LowerBounds[i] = new int[c.Points.Length];
int k = 0;
for (int j = 0; j < c.Points.Length && k < d.Points.Length; j++)
{
while (k < d.Points.Length && !InRange(c.AbsoluteDistance,
c.MaxDistanceToNext,
c.Points[j],
d.Points[k]))
k++;
LowerBounds[i][j] = k;
}
}
Color current = Colors[0];
List<List<int>> ret = new List<List<int>>();
List<int> group = new List<int>(Colors.Count);
for (int i = 0; i < Colors.Count; i++)
group.Add(0);
for (int i = 0; i < current.Points.Length; i++)
{
int pointA = current.Points[i];
group[0] = pointA;
FindNextColor(1, i, group, ret);
}
Console.Write("\n");
return ret;
}
private void FindNextColor(int colorIndex, int pointIndex, List<int> group, List<List<int>> ret)
{
if (Colors.Count <= colorIndex) // found end of complete group :)
{
ret.Add(new List<int>(group));
return;
}
Color prev = Colors[colorIndex - 1];
Color current = Colors[colorIndex];
int pointA = group[colorIndex - 1];
// int lower = prev.AbsoluteDistance ? pointA - prev.MaxDistanceToNext : pointA;
// int upper = pointA + prev.MaxDistanceToNext;
// int lowerIdx = Array.BinarySearch(current.Points, lower);
// if (lowerIdx < 0) lowerIdx = ~lowerIdx;
// int upperIdx = Array.BinarySearch(current.Points, upper);
// if (upperIdx < 0) upperIdx = ~upperIdx - 1;
int lowerIdx = LowerBounds[colorIndex - 1][pointIndex];
for (int i = lowerIdx; i < current.Points.Length; i++)
{
int pointB = current.Points[i];
if (!InRange(prev.AbsoluteDistance, prev.MaxDistanceToNext, pointA, pointB))
break;
int dist = pointB - pointA;
Console.WriteLine($"{colorIndex - 1}: {pointA}, {pointB} = {dist}");
group[colorIndex] = pointB;
FindNextColor(colorIndex + 1, i, group, ret);
}
}
}
public class Color
{
public Color(string Name, int MaxDistanceToNext, bool AbsoluteDistance, int[] Points)
{
Array.Sort(Points);
this.Name = Name;
this.MaxDistanceToNext = MaxDistanceToNext;
this.AbsoluteDistance = AbsoluteDistance;
this.Points = Points;
}
public string Name { get; }
public int MaxDistanceToNext { get; }
public bool AbsoluteDistance { get; }
public int[] Points { get; set; }
}
}
}
Il codice sopra ha una complessità nel caso peggiore di O(NM + NG) = O(N * (M + G)), dove Nè il numero di colori, Mè il numero massimo di punti di un dato colore ed Gè il numero di gruppi che possono essere trovati dati i vincoli. È O(NM)per il precalcolo e O(NG)per l'algoritmo effettivo. Credo che questo sia ottimale.