in reply to Re: better union of sets algorithm?
in thread better union of sets algorithm?

Only if they are non-negative integers....

(Well, theoretically, for any set for which you have a fast, 1-to-1 mapping to the set of non-negative integers, this method will work. For instance, if all your members are negative integers, multiplying all members with -1 gives you positive integers to put inside the bit string)

Replies are listed 'Best First'.
Re^3: better union of sets algorithm?
by QM (Parson) on Mar 11, 2005 at 15:41 UTC
    Only if they are non-negative integers...
    The positive integers can be mapped 1-to-1 on the entire set of integers (both sets have the same cardinality). You can construct a mapping so that the bit index is unique for any integer. For example: 
    my $index = ( $integer >= 0 )
            ? 2 * $index
            : -2 * $index - 1;

    [download]
    Then $index is non-negative even for positive integers, and non-negative odd for negative integers.

    BTW, there is an interesting idea for Bottle Golf at Aleph-0 on Mathworld.

    -QM
    --
    Quantum Mechanics: The dreams stuff is made of

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom