Perl +lists/unions/intersection:

Discussion in 'Perl Misc' started by oleg, Jul 12, 2006.

  1. oleg

    oleg Guest

    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
    oleg, Jul 12, 2006
    #1
    1. Advertising

  2. oleg

    oleg Guest

    A. Sinan Unur wrote:
    > "oleg" <> wrote in
    > news::
    >
    > > Could you please help me to solve the following problem.
    > > Rules:

    >
    > This sounds like homework to me.
    >
    > > 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

    >
    > That would be a single list, wouldn't it?
    >
    > > 4) Size K is greater then any one size of original lists

    >
    > This requirement does not preclude producing a single list.
    >
    > > 5) New lists must always include all elements found in original
    > > lists minus the duplicates.

    >
    > Ditto.
    >
    > > Here is an example:
    > >
    > > Combine seven lists below into new lists. New lists must contain less
    > > then 10 elements

    >
    > Why? Where did that requirement come from?
    >
    > > 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 }

    >
    > How did you come up with these magic lists?
    >
    > Please read and follow the posting guidelines for this group. Post a
    > more complete statement of the problem, along with your best attempt to
    > solve it (following the guidelines).
    >
    > Do browse the FAQ list before you post. In particular,
    >
    > perldoc -q intersection
    > perldoc -q duplicate
    >
    > Sinan
    > --
    > A. Sinan Unur <>
    > (remove .invalid and reverse each component for email address)
    >
    > comp.lang.perl.misc guidelines on the WWW:
    > http://augustmail.com/~tadmc/clpmisc/clpmisc_guidelines.html


    I guess I made it look like school homework, but it is not.

    In real world, I have "bunches" of signals coming from hardware
    substate machines ( very large state machine split up into many smaller
    ones) . I want to write a script to equalize these signals into the
    least number of 21bit chunks to minimize the muxing.

    I did it by hand once, but state machine keeps changing and so I would
    rather automate procedure. I already wrote a perl script that extracts
    the signals and build the lists. Now, I just need the right algorithm
    for the lists
    oleg, Jul 12, 2006
    #2
    1. Advertising

  3. oleg

    l v Guest

    oleg wrote:
    > Hello,
    >
    >
    > Could you please help me to solve the following problem.


    [snip]
    >
    > 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
    >


    List::Compare may be what you are looking for to get the union of two lists.

    --

    Len
    l v, Jul 12, 2006
    #3
  4. oleg

    oleg Guest

    Glenn,
    Thank you for looking into this!

    >
    > Are you dropping duplicated elements or not? Your "list_3 + list_5"
    > contains 2 "y". Is there any reason to associate the new lists with
    > particular old lists?


    I am only dropping the duplicate elements within the lists that are
    selected to be combined. The key here is to find among original lists
    those with the largest intersection. YES, there must be association
    between the old and new lists. All elements of any given old list must
    be accessible in one of the new lists.


    Thanks!
    Oleg
    oleg, Jul 12, 2006
    #4
  5. oleg

    Guest

    "oleg" <> wrote:
    > [Sinan wrote:]
    > > [Oleg wrote:]
    > > >
    > > > 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 }

    > >
    > >
    > > perldoc -q intersection
    > > perldoc -q duplicate
    > >


    > In real world, I have "bunches" of signals coming from hardware
    > substate machines ( very large state machine split up into many smaller
    > ones) . I want to write a script to equalize these signals into the
    > least number of 21bit chunks to minimize the muxing.


    I don't get it. If you have real hardware, surely you aren't writing the
    kernel/microcode in Perl! And if you are merely simulating hardware, I'm
    not sure why you would want to write a simulation in such a way that, if
    the simulation turns out to be successful, it cannot be translated into
    reality.

    In any event, I believe this is a type of bin-packing problem for which
    there is no efficient way to find the optimal packing without exhaustive
    checking every possiblity (or doing something on the same order as that.)
    It isn't obvious whether you need the optimal solution, or merely a
    sufficiently good one.

    > I did it by hand once, but state machine keeps changing and so I would
    > rather automate procedure. I already wrote a perl script that extracts
    > the signals and build the lists. Now, I just need the right algorithm
    > for the lists


    If you only need a sufficiently good solution, then check the size of the
    union of randomly chosen pairwise combinations of lists (how to do this is
    covered in the docs you have been referred to). If it is small enough to
    meet your criteria, fuse them. Stop when you can't find any more pairwise
    combinations that meet the criteria, or when you get sick of searching, or
    when some other criteria of your choosing is met.

    Xho

    --
    -------------------- http://NewsReader.Com/ --------------------
    Usenet Newsgroup Service $9.95/Month 30GB
    , Jul 12, 2006
    #5
  6. oleg

    oleg Guest

    > I don't get it. If you have real hardware, surely you aren't writing the
    > kernel/microcode in Perl! And if you are merely simulating hardware, I'm
    > not sure why you would want to write a simulation in such a way that, if
    > the simulation turns out to be successful, it cannot be translated into
    > reality.


    I am designing hardware in RTL. I merely need a tool to speed up a
    tidius task of manually building up the signal lists of this huge state
    machine .


    >
    > In any event, I believe this is a type of bin-packing problem for which
    > there is no efficient way to find the optimal packing without exhaustive
    > checking every possiblity (or doing something on the same order as that.)
    > It isn't obvious whether you need the optimal solution, or merely a
    > sufficiently good one.
    >
    > > I did it by hand once, but state machine keeps changing and so I would
    > > rather automate procedure. I already wrote a perl script that extracts
    > > the signals and build the lists. Now, I just need the right algorithm
    > > for the lists

    >
    > If you only need a sufficiently good solution, then check the size of the
    > union of randomly chosen pairwise combinations of lists (how to do this is
    > covered in the docs you have been referred to). If it is small enough to
    > meet your criteria, fuse them. Stop when you can't find any more pairwise
    > combinations that meet the criteria, or when you get sick of searching, or
    > when some other criteria of your choosing is met.


    Yes, I only need a "good enough" solution.


    >
    > Xho
    >
    > --
    > -------------------- http://NewsReader.Com/ --------------------
    > Usenet Newsgroup Service $9.95/Month 30GB
    oleg, Jul 12, 2006
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?ISO-8859-1?Q?Mickel_Gr=F6nroos?=

    Standard ways to get union, intersection, difference of lists?

    =?ISO-8859-1?Q?Mickel_Gr=F6nroos?=, Jun 26, 2003, in forum: Python
    Replies:
    2
    Views:
    1,839
    Erik Max Francis
    Jun 26, 2003
  2. Gerrit Holl
    Replies:
    0
    Views:
    863
    Gerrit Holl
    Jun 26, 2003
  3. =?ISO-8859-1?Q?Mickel_Gr=F6nroos?=

    Re: Standard ways to get union, intersection, difference of lists?

    =?ISO-8859-1?Q?Mickel_Gr=F6nroos?=, Jun 26, 2003, in forum: Python
    Replies:
    3
    Views:
    1,435
    Mike C. Fletcher
    Jun 26, 2003
  4. Gordon Williams

    efficient intersection of lists with rounding

    Gordon Williams, Dec 2, 2004, in forum: Python
    Replies:
    9
    Views:
    355
    Gordon Williams
    Dec 6, 2004
  5. James Stroud
    Replies:
    2
    Views:
    380
    George Sakkis
    Oct 19, 2005
Loading...

Share This Page