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

CodePudding user response：

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));
     
    }
}

CodePudding user response：

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();