csrComb.h

   1 // Copyright (C) 2021 Harry Godden (hgn)
   2
   3 // API
   4 //=======================================================================================================================
   5
   6 // Algorithm 1: Generate non-repeating combinations of size M in set of N
   7 // Usage:
   8 //   int p[3];
   9 //   hgn_comb_init( 3, p );
  10 //
  11 //   do
  12 //   {
  13 //      something with p[0], p[1], p[2]
  14 //   }
  15 //   while( hgn_comb( 3, 5, p ) );
  16 //
  17 //   Output of p each iteration:
  18 //     0 1 2
  19 //     0 1 3
  20 //     0 1 4
  21 //     0 2 3
  22 //     0 2 4
  23 //     0 3 4
  24 //     1 2 3
  25 //     1 2 4
  26 //     1 3 4
  27 //     2 3 4
  28
  29 void csr_comb_init( int const M, int p[] );
  30 int csr_comb( int M, int N, int p[] );
  31
  32 // Implementation
  33 //=======================================================================================================================
  34
  35 #ifdef CSR_EXECUTABLE
  36
  37 void csr_comb_init( int const M, int p[] )
  38 {
  39         for( int i = 0; i < M; i ++ )
  40         {
  41                 p[ i ] = i;
  42         }
  43 }
  44
  45 int csr_comb( int M, int N, int p[] )
  46 {
  47         for( int j = M-1; j >= 0; --j )
  48         {
  49                 if( p[j] < N-(M-j) ) // Can J be incremented?
  50                 {
  51                         p[j] ++;
  52                         for( int k = j+1; k < M; k ++ ) // Adjust following indexes
  53                         {
  54                                 p[k] = p[j]+k-j;
  55                         }
  56                         return 1;
  57                 }
  58         }
  59         return 0;
  60 }
  61
  62 #endif