RE: finding differences in a list of amounts

[CWilt@xxxxxxxxxxxx]

Dan,

Yep, considerable bit-twiddling!

Though about it at lunch, decided you'd end up doing both bit-shifting and
pattern shifting.

Realized that we're talking about an algorithm for "n choose k"

Googled for said algorithm and here you go:
-pseudo code-
http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module11/module11.html

here's the code to another one I found:


HTH,
Charles


/***********************************************************
    gencomb.c -- witten by Haruhiko Okumura:
((<URL:ftp://ftp.matsusaka-u.ac.jp/pub/algorithms/src/gencomb.c>)). 
***********************************************************/
#include <stdio.h>
#include <stdlib.h>
#define N 8
#define K 4
typedef unsigned int set;
#define first(n) ((set) ((1U << (n)) - 1U))

set nextset(set x)
{
    set smallest, ripple, new_smallest, ones;

    smallest = x & -x;
    ripple = x + smallest;
    new_smallest = ripple & -ripple;
    ones = ((new_smallest / smallest) >> 1) - 1;
    return ripple | ones;
}

void printset(set s)
{
    int i;

    for (i = 1; i <= N; i++) {
        if (s & 1) printf(" %d", i);
        s >>= 1;
    }
    printf("\n");
}

int main()
{
    int i;
    set x;

    i = 1;  x = first(K);
    while (! (x & ~first(N))) {
        printf("%4d:", i);  printset(x);
        x = nextset(x);  i++;
    }
    return EXIT_SUCCESS;
}


> -----Original Message-----
> From: Dan Bale [mailto:dbale@xxxxxxxxxxxxx]
> Sent: Monday, September 20, 2004 11:39 AM
> To: RPG programming on the AS400 / iSeries
> Subject: RE: finding differences in a list of amounts
> 
> 
> 
> Yeah, see, this is what I'm thinking as well.  Finding differences in
> reconciliation, in my experience, usually involves a small 
> set of numbers.
> Since this seems to be getting into serious bit-twiddling 
> territory, I had
> posted this part of the problem to the MI400 list.  A couple 
> of responses
> there gave me an idea, and I replied:
> 
> I am starting to think that this problem requires another 
> array that I can't
> quite put in words (there's a horrendous machine buzzing in 
> my background
> all morning - need to get some noise-cancelling headphones).  
> Essentially,
> it would be an array of integers that would have as many 
> elements as there
> would be the number amount of combinations as I want to test 
> for.  In my
> first iteration, only elements 1 & 2 would be used.  Element1 
> is set to 1
> and element2 is set to 2.  Increment element2 until get to 
> the high limit,
> then add 1 to element1 and set element2 to (element1 + 1).
> 
> Once I get to the end of 2-bit combos, set e1 to 1, e2 to 2, 
> and e3 to 3,
> and repeat the process as described for the 2-bit combos.
> 
> Does that make any sense?
> 
> tia,
> db
>