Attempting to learn dynamic programming, it seems like the algorithm works. I'm looking to make sure the algorithm is correct (and actually uses dynamic programming correctly) and for pointers on ways to clean up the code.
The algorithm creates a meta data table that has the element's value, the length of its longest sub-sequence, and a pointer to the index of its predecessor with the longest sub-sequence of its own.
Then we use the meta data to collect value with the longest length, then follow its predecessor pointer index to the next value, and add them to our longest sub-sequence in reverse order to reconstruct it until we hit an element with no predecessor.
And now for the code:
class SequenceValueWithMetaData
{
public int Value { get; private set; }
public int Length { get; set; }
public int? predecessorIndexMaybe { get; set; }
public SequenceValueWithMetaData(int value)
{
Value = value;
Length = 0;
predecessorIndexMaybe = null;
}
}
public class Program
{
static void Main(string[] args)
{
List<int> sequence = new List<int> { 2, 4, 3, 5, 1, 7, 6, 9, 8 };
List<int> longestSubsequence = GetLongestSubSequence(sequence);
PrintList(sequence);
PrintList(longestSubsequence);
PromptForClose();
}
private static void PrintList<T>(IEnumerable<T> list)
{
foreach (T t in list)
{
Console.Write(t + " ");
}
Console.WriteLine();
}
private static void PromptForClose()
{
Console.WriteLine("Press RETURN to close.");
Console.ReadLine();
}
public static List<int> GetLongestSubSequence(List<int> sequence)
{
if (sequence == null)
{
return null;
}
if (sequence.Count <= 0)
{
return new List<int>();
}
// generate the value table
List<SequenceValueWithMetaData> valueTable = GenerateValueTableFromSequence(sequence);
if (valueTable == null)
{
// Internal Error
throw new InvalidOperationException("valueTable is null");
}
// find largest length in the valueTable and record it to index
int indexOfLongestLength = 0;
for (int i = 0; i < valueTable.Count; i++)
{
if (valueTable[i].Length > valueTable[indexOfLongestLength].Length)
{
indexOfLongestLength = i;
}
}
// create the longest subsequence by finding the longest length,
// adding the value to the back of the list, then moving to its predecessor's index
int currentIndex = indexOfLongestLength;
int insertionPoint = valueTable[indexOfLongestLength].Length - 1;
int[] longestSubsequence = new int[valueTable[indexOfLongestLength].Length];
do
{
// add the value at index to the end of longestSubsequence
longestSubsequence[insertionPoint] = valueTable[currentIndex].Value;
insertionPoint = insertionPoint - 1;
// check if there is a predecessor
int? predecessorIndexMaybe = valueTable[currentIndex].predecessorIndexMaybe;
// if there is a predecessor, then assign set currentIndex to to the predecessorIndex
if (predecessorIndexMaybe.HasValue)
{
currentIndex = predecessorIndexMaybe.Value;
}
else
{
// no predecessor, so we're done
break;
}
} while (true); // breaks when there is no predecessor
return longestSubsequence.ToList();
}
private static List<SequenceValueWithMetaData> GenerateValueTableFromSequence(List<int> sequence)
{
if (sequence == null)
{
// Internal Error
throw new InvalidOperationException("valueTable is null");
}
List<SequenceValueWithMetaData> valueTable = new List<SequenceValueWithMetaData>();
// for each number in sequence
foreach (int number in sequence)
{
// Create a ValueMetaData for this number and add it to the valueTable
SequenceValueWithMetaData currentValue = new SequenceValueWithMetaData(number);
valueTable.Add(currentValue);
// traverse valueTable looking for the index of the longest length; where the value is < the current number
int indexOfCurrentLongestLength = 0;
bool hasPredecessor = false;
for (int i = 0; i < valueTable.Count; i++)
{
// if the value is less than our current value
if (valueTable[i].Value < currentValue.Value)
{
// at least one value is lower, so there will be a valid predecessor
hasPredecessor = true;
// if this value has a longer length than the currentLongestLength, then assign its index to the currentLongestLength
if (valueTable[i].Length > valueTable[indexOfCurrentLongestLength].Length)
{
indexOfCurrentLongestLength = i;
}
}
}
// record the found's length + 1 into this number's ValueMetaData
currentValue.Length = valueTable[indexOfCurrentLongestLength].Length + 1;
// if our currentValue has no predecessor, then set it to null
if (hasPredecessor == false)
{
currentValue.predecessorIndexMaybe = null;
}
// else, set currentValue's predecessor to the predecessor with the longest length
else
{
currentValue.predecessorIndexMaybe = indexOfCurrentLongestLength;
}
}
return valueTable;
}
}
Thanks!
1 Answer 1
I don't know whether it's a real dynamic programming or not because the definition is a little bit confusing but I'll try to review it anyway.
First of all your problem can be solved with a single method like this one. It groups elements in ascending order and picks the longest sequence. It works with any T that implements IComparable.
public static IEnumerable<T> LongestSequence<T>(this IEnumerable<T> values) where T : IComparable
{
return values.Aggregate(new List<List<T>>(), (groups, next) =>
{
if (groups.Any())
{
var group = groups.FirstOrDefault(x => x.Any() && x.Last().CompareTo(next) < 0);
if (group != null)
{
group.Add(next);
return groups;
}
}
groups.Add(new List<T> { next });
return groups;
})
.OrderByDescending(x => x.Count)
.FirstOrDefault();
}
Now let's review your code...
GenerateValueTableFromSequence and the null check
In .net we don't usually return null for collections. We do this so that we can avoid the null-check. We return empty collections which are safe to work with.
So this
List<SequenceValueWithMetaData> valueTable = GenerateValueTableFromSequence(sequence); if (valueTable == null) { // Internal Error throw new InvalidOperationException("valueTable is null"); }
would become:
List<SequenceValueWithMetaData> valueTable = GenerateValueTableFromSequence(sequence);
if (!valueTable.Any())
{
// Internal Error
return new List<int>(); // or Enumerable.Empty<int>().ToList();
}
There's no need for exeptions. (I'm ignoring the fact that it won't be null anyway looking at the implementation).
private static List<SequenceValueWithMetaData> GenerateValueTableFromSequence(List<int> sequence) { if (sequence == null) { // Internal Error throw new InvalidOperationException("valueTable is null"); }
If we check arguments we throw the Argument(Null)Exception rather then anything else.
You would throw the InvalidOperationException when
[...] a method call is invalid for the object's current state.
For example if some property of the object is in invalid state etc.