(If you can think of a better title, please let me know.)
I’m working on a route optimization program. I'm starting with a list of points which the route needs to include. My first step is to create a list of all possible routes (permutations). I then remove any route I can (for example, if one stop must precede another). Once that's done I calculate the distance and time between each point, in each possible route. Each point is an object (TPoint) and all the distance and time values are stored in a separate class called TData, which is stored in each instance of TPoint. My problem is this: when I try to update the TData in, say, the first stop, in the first possible route it will update the TData for that same TPoint in each possible route. This is because the class is a reference type and is stored on the heap. I’m looking for a solution that allows me to store the TData on each TPoint.
Here's some example code (the following code demonstrates how when I modify one object (TPoint), I'm only actually using the reference to modify the object on the heap):
Main
// Let's create a list of points we need to hit.
List<TPoint> lstInitial = new List<TPoint>();
lstInitial.Add(new TPoint("A", new TData(-1, -1)));
lstInitial.Add(new TPoint("B", new TData(-1, -1)));
lstInitial.Add(new TPoint("C", new TData(-1, -1)));
// Now let's get all possible routes
IList<IList<TPoint>> lstPermutations = Permutations(lstInitial);
// Let's write these values to the first point, in the first possible route.
lstPermutations[0][0].oTData.distance = 10;
lstPermutations[0][0].oTData.minutes = 20;
foreach (IList<TPoint> perm in lstPermutations)
{
foreach (TPoint p in perm)
{
Response.Write(p.id + "|" + p.oTData.distance + "|" + p.oTData.minutes);
Response.Write(" ");
}
Response.Write("<br />");
}
Permutation Function
// Get permutations
private static IList<IList<T>> Permutations<T>(IList<T> list)
{
List<IList<T>> perms = new List<IList<T>>();
// If the list is empty, return an empty list.
if (list.Count == 0)
{
return perms;
}
// This is a loop method to get the factorial of an integer
int factorial = 1;
for (int i = 2; i <= list.Count; i++)
{
// shortcut for: factorial = factorial * i;
factorial *= i;
}
for (int v = 0; v < factorial; v++)
{
//List<T> s = new List<T>(list);
List<T> s = new List<T>(list);
int k = v;
for (int j = 2; j <= list.Count; j++)
{
int other = (k % j);
T temp = s[j - 1];
s[j - 1] = s[other];
s[other] = temp;
k = k / j;
}
perms.Add(s);
}
return perms;
}
Classes
public class TPoint
{
public TPoint(string _id, TData _oTData)
{
id = _id;
oTData = _oTData;
}
public string id { get; set; }
public int someInt { get; set; }
public TData oTData { get; set; }
}
public class TData
{
public TData(int _distance, int _minutes)
{
distance = _distance;
minutes = _minutes;
}
public int distance { get; set; }
public int minutes { get; set; }
}
It kind of seems as if I've managed to paint myself into a corner. I can think of a few solutions, but they seem messy so I figured I'd ask the experts on this one.
Edit
Can anyone think of why this wouldn't be a good idea?
Instead of this, which modifies the object on the heap (and affects every point in each possible route):
lstPermutations[0][0].oTData.distance = 10;
lstPermutations[0][0].oTData.minutes = 20;
Use this, which just creates a new instance of the class:
TPoint oTPoint = new TPoint(lstPermutations[0][0].id, new TData(10, 20));
lstPermutations[0][0] = oTPoint;