I put this on pspp-dev, since now we're talking about a new algorithm.
Very creative, Ben. It's definitely worth a paper if it isn't already
published.
I've read through the code of ranksum6 below, and it passed the few
tests I ran. Walking through the algorithm, it always seems to give
the correct value.
But I would have to think more about the algorithm to convince myself
it will always be correct. Or see a written explanation. ('sorry Ben,
I know how you feel about being able figure out what code is supposed
to do just by reading it.)
-Jason
----- Forwarded message from Ben Pfaff <[email protected]> -----
To: Ben Pfaff <[email protected]>, John Darrington <[email protected]>,
Michel Boaventura <[email protected]>,
[email protected]
From: Ben Pfaff <[email protected]>
...
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/
_______________________________________________
Bug-gnu-pspp mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/bug-gnu-pspp
----- End forwarded message -----
_______________________________________________
pspp-dev mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/pspp-dev
