Babar/CM2 A-to-Z at Manchester

James Werner

Recursive algorithm for Event Reconstruction.

      1   #include <stdlib.h>
      2   #include <stdio.h>
      3
      4   #define numterm 5
      5   FILE *arq;
      6
      7   int main()
      8   {
      9   int mat[numterm],lista[numterm],i,j,k;
     10
     11   for(i=0;i<numterm;i++)
     12     mat[i]=i;
     13
     14   printf("\nCombination (%d 1)\n\n",numterm);
     15
     16   for(i=0;i<numterm;i++) {
     17     printf(" %d \n",mat[i]);
     18   }
     19
     20   printf("\nCombination (%d 2)\n\n",numterm);
     21
     22   for(i=0;i<numterm;i++) {
     23     for(j=i+1;j<numterm;j++) {
     24       printf(" %d %d \n",mat[i],mat[j]);
     25     }
     26   }
     27
     28   printf("\nCombination (%d 3)\n\n",numterm);
     29
     30   for(i=0;i<numterm;i++) {
     31     for(j=i+1;j<numterm;j++) {
     32       for(k=j+1;k<numterm;k++) {
     33         printf(" %d %d %d \n",mat[i],mat[j],mat[k]);
     34       }
     35     }
     36   }
     37   return 0;
     38   }

The program initialises array mat (lines 11 & 12) with sequential numbering from zero. If you are combining only one element, you just have to print the whole list list (lines 14 to 18).
The case where you are combining 2 elements (20 to 26), two pointers are required that select different elements, without repeating the list in any order. This is done by initialising the second pointer in the next element pointed by the first pointer.
The case where you are combining 3 elements (28 to 36), requires three pointers that select different elements, without repeating the list in any order. This is by done initialising the third pointer in the next element pointed to the second pointer.

... and so on...

bash-2.05b$ vi lista.c
bash-2.05b$ gcc lista.c -o lista
bash-2.05b$ ./lista

Combination (5 1)

 0
 1
 2
 3
 4

Combination (5 2)

 0 1
 0 2
 0 3
 0 4
 1 2
 1 3
 1 4
 2 3
 2 4
 3 4

Combination (5 3)

 0 1 2
 0 1 3
 0 1 4
 0 2 3
 0 2 4
 0 3 4
 1 2 3
 1 2 4
 1 3 4
 2 3 4

Now lets introduce recursive code.

      1   #include <stdlib.h>
      2   #include <stdio.h>
      3
      4   #define maxnum 5
      5
      6   void comb(int init, int numtermos, int itera, int tam, int *lista)
      7   {
      8   int i,j,xlista[maxnum];
      9
     10   if((numtermos-itera)==1) {
     11     for(i=lista[numtermos-2]+1;i<tam;i++) {
     12       for(j=0;j<numtermos-1;j++) {
     13         printf(" %d ",lista[j]);
     14       }
     15       printf(" %d \n",i);
     16     }
     17   } else {
     18     for(i=init;i<tam;i++) {
     19       for(j=0;j<itera;j++)
     20         xlista[j]=lista[j];
     21       xlista[itera]=i;
     22       comb(i+1,numtermos,itera+1,tam,xlista);
     23     }
     24   }
     25   }
     26
     27   int main ()
     28   {
     29   int i,lista[maxnum];
     30
     31   lista[0]=0;
     32
     33   for(i=2;i<=maxnum;i++)
     34     comb(0,i,0,maxnum,lista);
     35   return 0;
     36   }

Lines 33 and 34 call the comb function, to combine 2 to maxnum elements without repetition in any sequence. Comb function is divided in 2 parts: lines 10 to 16 prints final list of elements, and 17 to 27 call comb again for the next pointer. When the last pointer is set, it is time to print the list. The important point is that the list can be a pointer for one element in the structure, e.g. one stable particle. The reconstruction will be to evaluate mass, momentum and energy for each element of the combination sequence.

bash-2.05b$ vi comb.c
bash-2.05b$ gcc comb.c -o comb
bash-2.05b$ ./comb

 0  1
 0  2
 0  3
 0  4
 1  2
 1  3
 1  4
 2  3
 2  4
 3  4
 0  1  2
 0  1  3
 0  1  4
 0  2  3
 0  2  4
 0  3  4
 1  2  3
 1  2  4
 1  3  4
 2  3  4
 0  1  2  3
 0  1  2  4
 0  1  3  4
 0  2  3  4
 1  2  3  4
 0  1  2  3  4