Dynamic programming in C#

Question

I'm writing a simple dynamic programming in C#.

public class CountDerangementRec
{
    public long Derangements(int setsize)
    {
        var subSolutions = new List<long>(capacity:setsize + 1);

        for (int n = 1; n <= setsize; n++)
        {
            if (n == 1)
                subSolutions[n] = 0;
            else if (n == 2)
                subSolutions[n] = 1;
            else
                subSolutions[n] = (n - 1) * (subSolutions[n - 1] + subSolutions[n - 2]);

            return subSolutions[n];
        }
        return subSolutions[setsize];
    }
}

My main class looks like this: public class Program {

    public static void Main()
    {
        var count = new CountDerangementRec();

        Console.WriteLine(count.Derangements(3));           
            
    }
}

Every time I run the program , I get the following error:

Unhandled exception. System.ArgumentOutOfRangeException: Index was out of range. Must be non-negative and less than the size of the collection. (Parameter 'index')
   at System.Collections.Generic.List`1.set_Item(Int32 index, T value)
   at Dynamic_programing.CountDerangementRec.Derangements(Int32 setsize) in C:\Users\pasob\source\repos\Dynamic programing\CountDerangementRec.cs:line 18
   at Dynamic_programing.Program.Main() in C:\Users\pasob\source\repos\Dynamic programing\Program.cs:line 10

I don't know what I'm doing wrong

Have you tried stepping through with the debugger? Specifically checking the value of `n` in relation to how many items are in `subSolutions` at any given time? — maccettura, Aug 29 '22 at 17:03
Why do you (unconditionally) return inside the loop? - Also You do realize that arrays etc are zero-based in C#? — TaW, Aug 29 '22 at 17:05
Hint: setting the underlying *capacity* for a list doesn't change its *size*. With an empty list, *no* indexer access will work... you'd need to use `Add` to add a new element first. Perhaps you want an array in this case? — Jon Skeet, Aug 29 '22 at 17:05
Does this answer your question? [What is an IndexOutOfRangeException / ArgumentOutOfRangeException and how do I fix it?](https://stackoverflow.com/questions/20940979/what-is-an-indexoutofrangeexception-argumentoutofrangeexception-and-how-do-i-f) — Progman, Aug 29 '22 at 17:06

Dmitry Bychenko · Answer 1 · 2022-08-29T17:54:52.363

I suggest getting rid of List<long> and just generate items:

// Generate derangements one after one
public static IEnumerable<long> Derangements() {
  yield return 0;
  yield return 1;

  long prior = 1;
  long current = 0;

  for (int n = 2; ; ++n) {
    (prior, current) = (current, (n - 1) * (current + prior));

    yield return current;
  }
}

Then you can query Derangements() with a help of Linq:

using System.Linq;

...
// Quite literally: generate derangments,
// take first 3 of them 
// materialize as a list
List<long> all = Derangements().Take(3).ToList();

long last = Derangements().Skip(2).First();

score 0 · Accepted Answer · answered Aug 29 '22 at 17:53

subSolutions[n] goes out of bounds. Check this snippet for derangements permutation using DP:

using System;
 
class GFG
{
     
    // Function to count
    // derangements
    static int countDer(int n)
    {
        // Create an array to store
        // counts for subproblems
        int []der = new int[n + 1];
     
        // Base cases
        der[1] = 0;
        der[2] = 1;
     
        // Fill der[0..n] in bottom up
        // manner using above recursive
        // formula
        for (int i = 3; i <= n; ++i)
            der[i] = (i - 1) * (der[i - 1] +
                                der[i - 2]);
     
        // Return result for n
        return der[n];
    }
     
    // Driver code
    public static void Main ()
    {
        int n = 4;
        Console.Write("Count of Derangements is " +
                       countDer(n));
     
    }
}

Dynamic programming in C#

2 Answers2