Re: lists/unions/intersections:

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: New hp49g+ / hp48gII Advanced Users Reference Manual now available from HP
    ... creating the alternate "list of lists" output as on 48G, even with symbolic elements. ... but the output array may be symbolic" is entirely obsolete, as is the IFERR part of the program, but it might error on other input, and if it ever does, the program *assumes* flag -55 to be clear, which the program forgets to assure; ... 49G series MAP command does this entire job all by itself? ...
    (comp.sys.hp48)
  • Re: Process arbitrary #lists (continued)
    ... Subject: Process arbitrary #lists (continued) ... allocate ) ... so simple to manipulate the indexable data structure with averages, ... Probably not, but why bother, todays CPU comes with HUMONGUOUS memory ...
    (comp.lang.pl1)
  • Re: Cons cell archaic!?
    ... from s-expression or XML or other syntax you keep the bloated array ... For using vectors to emulate lists that ... Allocate 2, move 1 element: ... What do you think of that algorithm? ...
    (comp.lang.lisp)
  • Re: Linked list allocation
    ... and delete_item frees that memory. ... An alternative I thought of was that add_item should allocate a block, ... for inserting and deleting nodes from linked lists. ...
    (comp.lang.c)
  • Re: Global Variables
    ... >> Allocate your memory, call functions to manipulate it, ... DH-434 MOTORCRAFT ... from various text files which each list all of the cars, ... The file lists cars, and the parts which the vendor has, ...
    (comp.lang.c)