Re: lists/unions/intersections:

Chris,
I use perl to implement this algoritm, so hashmap is available. Memory
efficiency is irrelevent ( a few gigs in the workstation) I only care
about final list. If I understand your idea correctly, it will not
work because of requirement number 5.

In other words, from my example, when user selects list _7, new
list(list_4+list_6+list_7) is accessed which has all elements that
user is trying to access from list_7. Removal of duplicat elements is
the only difference between old lists and new combinational lists

With your algorithm old lists will not be subset of any of the new
lists


Chris wrote:
oleg wrote:
Hello,


Could you please help me to solve the following problem.
Rules:
1) There "N" number of lists. Each list has W(N) number of elements
2) Each list can be fully independent of other lists or it can have
intersection with one or more other lists or it can be identical to one
or more other lists.
3) I need to combine these lists into the new "M" number of lists
of size that is less then K. The goal is to produce the smallest
possible number of lists
4) Size K is greater then any one size of original lists
5) New lists must always include all elements found in original lists
minus the duplicates.

Here is an example:

Combine seven lists below into new lists. New lists must contain less
then 10 elements
list_1: { a, b, c, d ,e }
list_2: { c, d, a, g }
list_3: { a, g, s, h, y }
list_4: { t, r, n, l, o }
list_5: { c, f, g, s, w, y }
list_6: { n, y, r, s }
list_7: { k, b, s }

list_1+list_2: { a, b, c, d, e, g }
list_3 + list_5; { a, g, s, h, y, c, f, w, y }
list_4 + list_6 + list_7: { t, r, n, l, o, y, s, k, b }

Thank you!
Oleg


Can you use an external data structure, like a hashmap?

Allocate an output array of size K

For each element in each list, attempt to insert it into a hashmap. If
it's not already in the map, add it to your output array. If it is,
then ignore it.

When you run out of room in the output array, allocate
another one and continue.

This is not particularly memory efficient, but it is fast and simple.

.

Relevant Pages

  • Re: Hashmap and multiple threads
    ... updated by multiple threads in a completely unprotected ... Although not protecting the Hashmap operations is clearly wrong, ... using the hash code to select a bucket, then scanning the linked list. ... It might prevent the lists from becoming permanently ...
    (comp.lang.java.programmer)
  • Re: Hashmap and multiple threads
    ... Although not protecting the Hashmap operations is clearly wrong, ... using the hash code to select a bucket, ... linked lists could have become a loop, so that any thread scanning it ... find are from containsKey, it could just be luck of the draw. ...
    (comp.lang.java.programmer)
  • Re: hash collision and the HashMap
    ... a Hashmap rather maps the hashcode of the key to a list of key- Value ... it then uses the equals method in that list to find what object you are ... so hashmap is kind of an array of lists.. ...
    (comp.lang.java.programmer)
  • Re: grow list by tail, pointer example recipe -- please comment
    ... manufacturing a pointer with that address. ... the next cons cell. ... believe these lists are in consecutive memory locations. ...
    (comp.lang.lisp)
  • Re: Fast linked list
    ... > amounts of memory rather than huge chunks of it. ... random insertions into a vector/dynamic array are not as slow ... to cause a cache miss. ... some hard numbers on speed differences between lists and arrays. ...
    (microsoft.public.vc.mfc)