|
|
|
|
|
|
| Author |
Message |
oleg
*nix forums beginner
Joined: 05 Jan 2006
Posts: 7
|
 Posted: Wed Jul 12, 2006 2:13 am Post subject:
Perl +lists/unions/intersection:
|
|
|
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 |
|
| Back to top |
|
 |
A. Sinan Unur
*nix forums Guru
Joined: 03 Mar 2005
Posts: 1840
|
| Posted: Wed Jul 12, 2006 2:21 am Post subject:
Re: Perl +lists/unions/intersection:
|
|
|
"oleg" <orodionov@gmail.com> wrote in
news:1152670386.786062.215730@i42g2000cwa.googlegroups.com:
| Quote: | Could you please help me to solve the following problem.
Rules:
|
This sounds like homework to me.
| Quote: | 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?
| Quote: | 4) Size K is greater then any one size of original lists
|
This requirement does not preclude producing a single list.
| Quote: | 5) New lists must always include all elements found in original
lists minus the duplicates.
|
Ditto.
| Quote: | 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?
| Quote: | 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 <1usa@llenroc.ude.invalid>
(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 |
|
| Back to top |
|
|
oleg
*nix forums beginner
Joined: 05 Jan 2006
Posts: 7
|
| Posted: Wed Jul 12, 2006 3:00 am Post subject:
Re: Perl +lists/unions/intersection:
|
|
|
A. Sinan Unur wrote:
| Quote: | "oleg" <orodionov@gmail.com> wrote in
news:1152670386.786062.215730@i42g2000cwa.googlegroups.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 <1usa@llenroc.ude.invalid
(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 |
|
| Back to top |
|
|
A. Sinan Unur
*nix forums Guru
Joined: 03 Mar 2005
Posts: 1840
|
| Posted: Wed Jul 12, 2006 3:07 am Post subject:
Re: Perl +lists/unions/intersection:
|
|
|
"oleg" <orodionov@gmail.com> wrote in news:1152673202.092297.64310@
75g2000cwc.googlegroups.com:
| Quote: | A. Sinan Unur wrote:
"oleg" <orodionov@gmail.com> wrote in
news:1152670386.786062.215730@i42g2000cwa.googlegroups.com:
....
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).
|
<SNIP>
Don't quote signatures.
| Quote: | 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.
|
Please do read and follow the posting guidelines. Do not full-quote.
Trim quoted material appropriately in your response.
| Quote: | 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
|
Well, as I said, explain what you want to do clearly, and consistently,
and show your best attempt to solve the problem.
Sinan
--
A. Sinan Unur <1usa@llenroc.ude.invalid>
(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 |
|
| Back to top |
|
|
veatchla@yahoo.com
*nix forums addict
Joined: 17 Nov 2005
Posts: 53
|
| Posted: Wed Jul 12, 2006 4:17 am Post subject:
Re: Perl +lists/unions/intersection:
|
|
|
oleg wrote:
| Quote: | Hello,
Could you please help me to solve the following problem.
|
[snip]
| Quote: |
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 |
|
| Back to top |
|
|
Glenn Jackman
*nix forums addict
Joined: 19 Apr 2005
Posts: 97
|
| Posted: Wed Jul 12, 2006 3:26 pm Post subject:
Re: Perl +lists/unions/intersection:
|
|
|
At 2006-07-11 10:13PM, oleg <orodionov@gmail.com> wrote:
| Quote: | 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 }
|
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?
use strict;
use warnings;
sub printLoL {
my $count = 0;
print(++$count, "\t", join(", ", @$_), "\n") foreach @_;
}
my @orig = (
[qw(a b c d e)],
[qw(c d a g)],
[qw(a g s h y)],
[qw(t r n l o)],
[qw(c f g s w y)],
[qw(n y r s)],
[qw(k b s)],
);
print "original lists:\n";
printLoL(@orig);
# combine elements into one big list
my %hash;
foreach my $list (@orig) {
$hash{$_}++ foreach @$list;
}
my @biglist = sort keys %hash;
# then, split the big list into constrained smaller lists
my @newlists;
my $K = 10;
while (@biglist) {
push @newlists, [splice @biglist, 0, $K];
}
print "new lists:\n";
printLoL(@newlists);
output:
original lists:
1 a, b, c, d, e
2 c, d, a, g
3 a, g, s, h, y
4 t, r, n, l, o
5 c, f, g, s, w, y
6 n, y, r, s
7 k, b, s
new lists:
1 a, b, c, d, e, f, g, h, k, l
2 n, o, r, s, t, w, y
--
Glenn Jackman
Ulterior Designer |
|
| Back to top |
|
|
oleg
*nix forums beginner
Joined: 05 Jan 2006
Posts: 7
|
| Posted: Wed Jul 12, 2006 3:52 pm Post subject:
Re: Perl +lists/unions/intersection:
|
|
|
Glenn,
Thank you for looking into this!
| Quote: |
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 |
|
| Back to top |
|
|
xhoster@gmail.com
*nix forums Guru
Joined: 19 Jul 2005
Posts: 842
|
| Posted: Wed Jul 12, 2006 4:30 pm Post subject:
Re: Perl +lists/unions/intersection:
|
|
|
"oleg" <orodionov@gmail.com> wrote:
| Quote: | [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.
| Quote: | 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 |
|
| Back to top |
|
|
oleg
*nix forums beginner
Joined: 05 Jan 2006
Posts: 7
|
| Posted: Wed Jul 12, 2006 5:20 pm Post subject:
Re: Perl +lists/unions/intersection:
|
|
|
| Quote: | 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 .
| Quote: |
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.
| Quote: |
Xho
--
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service $9.95/Month 30GB |
|
|
| Back to top |
|
|
A. Sinan Unur
*nix forums Guru
Joined: 03 Mar 2005
Posts: 1840
|
| Posted: Wed Jul 12, 2006 5:24 pm Post subject:
Re: Perl +lists/unions/intersection:
|
|
|
"oleg" <orodionov@gmail.com> wrote in
news:1152724850.600675.238860@m79g2000cwm.googlegroups.com:
[ attribution missing. please do not snip attributions. ]
| Quote: | 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.
|
Well, Xho has told you how to do it. Now, it is your turn to give it a
shot. You have all the information you need to write this thing.
Sinan
--
A. Sinan Unur <1usa@llenroc.ude.invalid>
(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 |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Sun Nov 23, 2008 11:16 am | All times are GMT
|
|
Download Korean movies | Credit Card | Loans | Loans | Mobile Phones
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
|
|
Other DeniX Solutions sites:
Unix/Linux blog |
electronics forum |
medicine forum |
science forum |
|
|
Privacy Policy
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Programming
»
Perl
