CODEWITHSUNDEEP
crecursion
guskenny83
guskenny83

Reputation: 1373

counting derangements using recursion? (c code)

we've been studying cryptography in computing theory and the idea of derangements came up in class which interested me so i wanted to do some investigation into the topic.

to that end i have been trying to work out a c program that can count the derangements for an arbitrary set size, but have been having some trouble.

i have been able to write something that counts the derangements for a specific set size, eg. 4:

#include <stdio.h>
#include <stdlib.h>

#define SET_SIZE 4


int main(void)
{   
   int i, j, k, l, counter = 0;

   for (i = 0; i < SET_SIZE; i++)
   {
      for (j = 0; j < SET_SIZE; j++)
      {
         for (k = 0; k < SET_SIZE; k++)
         {
            for (l = 0; l < SET_SIZE; l++)
            {
               if (i != j && i != k && i != l && j != k && j != l && k != l)
               {
                  if (i != 0 && j != 1 && k != 2 && l != 3)
                     counter++;
               }
            }
         }
      }
   }

   printf("number of derangements for size %d: %d\n", SET_SIZE, counter);
}

but i would like to be able to just input a value for set size as an argument for the program and calculate the number of derangements for that set size.

i think using recursion could be a way to solve the problem, but i cant really think about how i would go about doing it

any one have any ideas?

Upvotes: 0

Views: 798

Answers (2)

millinon
millinon

Reputation: 1576

I like your approach. You're probably starting to see that you want to keep running a for loop for every subset of the set, which suggests a stack-like structure. Recursion works by repeatedly pushing onto the call stack, so this is like an abstraction of your counting method. I suggest reading this to see how the following is derived.

unsigned int D(int n){
    if(n <= 1) return 0;
    else if(n == 2) return 1;
    else return (n-1)*(D(n-1) + D(n-2));
}

Sample run here.

Upvotes: 1

LearningC
LearningC

Reputation: 3162

for counting the number of dearrangements for any n objects you can use the formula given here or link. you can implement it with factorial implentation.

Upvotes: 2

Related Questions