Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > Perl +lists/unions/intersection:

Reply
Thread Tools

Perl +lists/unions/intersection:

 
 
oleg
Guest
Posts: n/a
 
      07-12-2006
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

 
Reply With Quote
 
 
 
 
oleg
Guest
Posts: n/a
 
      07-12-2006

A. Sinan Unur wrote:
> "oleg" <(E-Mail Removed)> wrote in
> news:(E-Mail Removed) oups.com:
>
> > 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 <(E-Mail Removed)>
> (remove .invalid and reverse each component for email address)
>
> comp.lang.perl.misc guidelines on the WWW:
> http://augustmail.com/~tadmc/clpmisc...uidelines.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

 
Reply With Quote
 
 
 
 
l v
Guest
Posts: n/a
 
      07-12-2006
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
 
Reply With Quote
 
oleg
Guest
Posts: n/a
 
      07-12-2006
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

 
Reply With Quote
 
xhoster@gmail.com
Guest
Posts: n/a
 
      07-12-2006
"oleg" <(E-Mail Removed)> 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
 
Reply With Quote
 
oleg
Guest
Posts: n/a
 
      07-12-2006
> 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


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
FAQ 2.17 What is perl.com? Perl Mongers? pm.org? perl.org? cpan.org? PerlFAQ Server Perl Misc 0 04-04-2011 10:00 PM
FAQ 1.4 What are Perl 4, Perl 5, or Perl 6? PerlFAQ Server Perl Misc 0 02-27-2011 11:00 PM
FAQ 2.17 What is perl.com? Perl Mongers? pm.org? perl.org? cpan.org? PerlFAQ Server Perl Misc 0 02-03-2011 11:00 AM
FAQ 1.4 What are Perl 4, Perl 5, or Perl 6? PerlFAQ Server Perl Misc 0 01-23-2011 05:00 AM
Perl Help - Windows Perl script accessing a Unix perl Script dpackwood Perl 3 09-30-2003 02:56 AM



Advertisments