Hi,
some ideas from the top of my head...one obvious way of doing this is
using a Dictionary to keep track of occurrences of each number (i.e.
scan the input list twice, first constructing the dictionary and next
constructing the output list). Another (memory-friendly) is sorting the
input list and doing a simple scan ((n*log n) + n). There are
bucket-sort-inspired variations on this one that greatly reduce the
complexity (that might even outperform the dictionary approach).
HTH,
Filip
I have a list of n numbers than I want to partition into two
subsets--the first set contains numbers that only appear in the list one
time, the second set contains numbers that appear twice.
For example, a list such as {1, 2, 3, 4, 2, 3} would be partitioned into
{1, 4} and {2,3}.
I could recurse through the list, picking off the first element each
time, and adding it to one list the first time it was encountered, and
then removing it from the first list and adding it to the second if it
is encountered a second time.
My question is this:
Is there a more efficient way to partition this list in OZ--
such as using the List partition function, or or one of the "drop..."
functions?
George Rudolph
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
