PSPP-BUG: [bug #25466] Compile problem on wilcoxon.c

[Ben Pfaff]

Follow-up Comment #7, bug #25466 (project pspp):

Actually, here's a solution that is even better.  A test program using it
calculates (correctly) and prints *all* the values for 1 <= N <= 30, 1 <= W <=
N*(N+1)/2, in under .2 seconds *total*.

The runtime of this algorithm is O(N*W) and it uses O(W) space.


int ranksum6(int N, int W)
{
  int *array;
  int max;
  int total;

  assert (N >= 0);
  if (N == 0)
    return 0;
  else if (W <= 0)
    return 1 << N;
  else if (W > N * (N + 1) / 2)
    return 0;
  else if (N == 1)
    return 1;

  array = calloc (sizeof *array, W + 1);
  array[W] = 1;

  max = W;
  total = 0;
  for (; N > 1; N--)
    {
      int max_sum = N * (N + 1) / 2;
      int i;

      if (max_sum < max)
        max = max_sum;

      for (i = 1; i <= max; i++)
        if (array[i] != 0)
          {
            int new_W = i - N;
            if (new_W <= 0)
              total += array[i] * (1 << (N - 1));
            else
              array[new_W] += array[i];
          }
    }
  total += array[1];
  free (array);
  return total;
}


    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?25466>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/