Perl +lists/unions/intersection:

O

oleg

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
 
O

oleg

A. Sinan Unur said:
This sounds like homework to me.


That would be a single list, wouldn't it?


This requirement does not preclude producing a single list.


Why? Where did that requirement come from?


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 <[email protected]>
(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
 
L

l v

oleg said:
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.
 
O

oleg

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
 
X

xhoster

oleg said:
[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
 
O

oleg

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.


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.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top