Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

array splitting

by CColin (Scribe)
on Jun 05, 2007 at 11:06 UTC ( #619343=perlquestion: print w/ replies, xml ) Need Help??
CColin has asked for the wisdom of the Perl Monks concerning the following question:

Hi, I am grappling with what looks like a simple problem but I'm not finding a simple answer. I have an array, let's say
@times = (5, 10, 20, 25, 30, 40, 45, 50, 55, 65, 75, 80, 90)
I want to remove any element from the array (to place in another array) which is less than 10 from it's neighbour (that bit I managed), but the other array must also not contain any neighbours who are less than 10 apart (so far not managed, instead I ended up removing too much of the original list) - all members of the array mut be accounted for and the distance between neighbours is never less than 5, so this should be possible.
So, for the above example, I want to end up with:
@times1 = (5, 20, 30, 40, 50, 65, 75, 90)
@times2 = (10, 25, 45, 55, 80)
I think.
How to acheive this programmatically?
Colin

Comment on array splitting
Re: array splitting
by kyle (Abbot) on Jun 05, 2007 at 11:14 UTC

    Can you show us what you have so far? It might be easier to fix the code you've written than to write you a solution from scratch.

Re: array splitting
by ww (Bishop) on Jun 05, 2007 at 11:16 UTC
    1. Customarily, posting some code will get better help than a simple question
    2. Your definition of "neighbor" appears (from the sample) to mean "the next-adjacent number -- after each test/remove/keep action." But this is NOT unambiguous, from your sample data.
      Consider: (5,6,7,8,9,10, 15, 20...)
      A tighter definition may actually reveal the answer you seek, as at least my reading of your sample makes me believe their can be cases where your final requirement cannot be satisfied for certain data.

    HTH

      >(5,6,7,8,9,10, 15, 20...)
      That can't happen - See the condition above in that no neighbour (ie. next adjacent number) is ever less than 5, and also all sequences are always ascending. Hence there should be a solution for this type of final data. Here is some code that sorts the first list so that all distances between numbers in the first list 10 or more, but fails for the second list when 2 or more consecutive numbers are less than 10.
      $count = 0; $time = 0; $last_time = 0; $time_diff = 100; #to ensure the first value appears in list 1 foreach $time (@times) { unless ($count == 0) {$time_diff = $last_time - $time}; if ($time_diff >= 10) {push (@times1, $time} else {push (@times2, $time)}; $last_time = $time; $count ++; } #end foreach
      Unless more alternative arrays can be added, which may not be the case.
Re: array splitting
by GrandFather (Cardinal) on Jun 05, 2007 at 11:39 UTC

    Deal with the problem a little at a time. First bit is loop over the elements (with strictures, declarations and initialisation thrown in):

    use warnings; use strict; my @times = (5, 10, 20, 25, 30, 40, 45, 50, 55, 65, 75, 80, 90); my @times1; my @times2; for my $elmt (@times) {

    Then deal with the first case (and the special case for the first element):

    if (! @times1 || $elmt - $times1[-1] >= 10) { push @times1, $elmt; next; }

    Then deal with the second case (and again the special case for the first special element):

    if (! @times2 || $elmt - $times2[-1] >= 10) { push @times2, $elmt; next; }

    Then deal with the exception (and close the loop body):

    push @times1, $elmt; }

    Finally print the result:

    print "Times1: @times1\n"; print "Times2: @times2\n";

    Prints:

    Times1: 5 20 30 40 50 65 75 90 Times2: 10 25 45 55 80

    DWIM is Perl's answer to Gödel
      I note the code I posted actually didn't even work for the first list. I note this code does work and there's a few things in this that I don't know well, so good for learning, thank you.
      if (! @times) presumably means if there is nothing in the array? This is a general confusion I have with perl, about what tests for a value being present in a variable and what "undef" means. I assume the exclamation mark I can always use to determine if values are (not) present in a variable from now on? Colin
        if (! @times) presumably means if there is nothing in the array?

        Yes. Alternatively you could use

        unless (@times) { # ...

        which may be clearer to understand naively, based on the rationale that a full thingy is true and an empty one is false.

        This is a general confusion I have with perl, about what tests for a value being present in a variable and what "undef" means.

        undef is a builtin function which can take a variable and give it a special value which is also its own return value. The latter is thus in turn also called undef: in fact the function is often used with no argument in which case it simply returns it. undef is a particular false value, precisely the one that also have variables which have not been initialized at all.

        I assume the exclamation mark I can always use to determine if values are (not) present in a variable from now on?

        The exclamation mark is simply a logical "not" that turns a true value into a false one and vice versa.

Re: array splitting
by perlfan (Curate) on Jun 05, 2007 at 14:55 UTC
    This is similar to the "longest increasing subsequence" problem. A very likely "solution" would be to:
    1. create a directed, acyclic graph, connecting numbers that are a distance of 10 or more - this is O(n2)
    2. iteratively, find the longest path start at the lowest number still contained in the graph
    3. each time a path is found, eliminate those numbers and edges from the graph
    You could probably use one of the Graph modules.
Re: array splitting
by Roy Johnson (Monsignor) on Jun 05, 2007 at 16:31 UTC
    Task: Go through the original array and determine which of the new arrays it should go in. The decision is based on looking at what's at the end of @t1.
    use strict; use warnings; my @times = (5, 10, 20, 25, 30, 40, 45, 50, 55, 65, 75, 80, 90); my (@t1, @t2); for (@times) { push @{(defined $t1[-1] and $_ - 10 < $t1[-1]) ? \@t2 : \@t1}, $_; } print "@t1\n@t2\n";

    Caution: Contents may have been coded under pressure.
Re: array splitting
by graff (Chancellor) on Jun 05, 2007 at 17:47 UTC
    Is it the case, for any given input list, that there can only be one correct division of elements into two lists? Or are multiple alternatives acceptable?

    And is it really the case that the input list will always consist of integer multiples of 5?

    If the latter answer is "yes", and you're not too picky about the nature of the partitioning, this ought to do fine:

    @input = (5, 10, 20, 25, 30, 40, 45, 50, 55, 65, 75, 80, 90); @out1 = grep /5$/, @input; @out2 = grep /0$/, @input;
    If that's not suitable, you'll need to be clearer about what the other constraints are for the partition.
Re: array splitting
by l.frankline (Hermit) on Jun 06, 2007 at 07:54 UTC
    @times = (5, 10, 20, 25, 30, 40, 45, 50, 55, 65, 75, 80, 90);
    @times1 = ();
    @times2 = ();
    $sw = 1;
    map {if ($sw == 1) {push (@times1,$_);$sw = 0;} else {$sw = 1;}} @times;
    $sw = 1;
    map {if ($sw == 0) {push (@times2,$_);$sw = 1;} else {$sw = 0;}} @times;

    Don't put off till tomorrow, what you can do today.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://619343]
Approved by ww
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (9)
As of 2014-11-26 01:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My preferred Perl binaries come from:














    Results (160 votes), past polls