Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Selectively iterate through an array

by jaiieq (Novice)
on Mar 14, 2013 at 15:29 UTC ( #1023490=perlquestion: print w/replies, xml ) Need Help??
jaiieq has asked for the wisdom of the Perl Monks concerning the following question:

Title probably doesn't accurately describe the issue I am having, but I am having a brain freeze moment on something I think should be fairly simple.

I have an array that contains 'starting' and 'ending' positions of a string, like this in the format if 'start position:end position'. There is also some data attached to all this, but its irrelevant to the end goal.

$VAR1 = 0:6 $VAR2 = 0:12 $VAR3 = 0:18 $VAR4 = 0:24 $VAR5 = 6:12 $VAR6 = 6:18 $VAR7 = 6:24 $VAR8 = 12:18 $VAR9 = 12:24 $VAR10 = 18:24

What I need to get out of this is all the possible 'start' to 'end' positions. Which would look like the following:

0:6 6:12 12:18 18:24 0:6 6:18 18:24 0:6 6:24 0:12 12:18 18:24 0:12 12:24 0:18 18:24 0:24 6:12 12:18 18:24 6:18 18:24 6:24 12:18 18:24 12:24 18:24
I hope this all makes sense and thanks in advance for any help or insight!

Replies are listed 'Best First'.
Re: Selectively iterate through an array
by tobyink (Abbot) on Mar 14, 2013 at 16:36 UTC

    This seems to be a question about finding all possible paths through a graph that end in "24". This does the job:

    use strict; use warnings; use Graph::Directed; my $g = "Graph::Directed"->new; $g->add_edge(split ":") for qw( 0:6 0:12 0:18 0:24 6:12 6:18 6:24 12:18 12:24 18:24 ); # This doesn't protect against cyclic graphs sub paths_from_vertex { my $g = shift; my $v = shift; return unless $g->has_vertex($v); my @s = $g->successors($v); return [$v] unless @s; my @p = map { paths_from_vertex($g, $_) } @s; unshift @$_, $v for @p; return @p; } sub print_path { my @path = @{+shift}; for my $i ( 0 .. $#path-1 ) { print "$path[$i]:$path[$i+1] "; } print "\n"; } for my $i (0..24) { print_path($_) for paths_from_vertex($g, $i); }
    package Cow { use Moo; has name => (is => 'lazy', default => sub { 'Mooington' }) } say Cow->new->name
      This appears to do exactly what I needed. Thank you for your reply.
Re: Selectively iterate through an array
by BrowserUk (Pope) on Mar 14, 2013 at 15:53 UTC
    Title probably doesn't accurately describe the issue

    I think what you are looking for is known combinatorially as 'non-overlapping subsets'.

    Should be fun to generate.


    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
Re: Selectively iterate through an array
by kennethk (Abbot) on Mar 14, 2013 at 15:57 UTC
    As with nearly everything in Perl, the answer is a hash. Specifically, a hash of arrays constructed from your colon-separated data set.
    my @input = qw(0:6 0:12 0:18 0:24 6:12 6:18 6:24 12:18 12:24 18:24); my %link; for (@input) { my ($key, $value) = split /:/; push @{$link{$key}}, $value; }
    which gives
    $VAR1 = { '6' => [ '12', '18', '24' ], '18' => [ '24' ], '0' => [ '6', '12', '18', '24' ], '12' => [ '18', '24' ] };

    You then just need to connect the dots, which I'd probably implement with a recursive subroutine.

    Note that the confusion about the start and end definition of your chains likely comes from the fact that, in your example, you seem to use all possible values for starts, but only 24 as an end.


    #11929 First ask yourself `How would I do this without a computer?' Then have the computer do it the same way.

Re: Selectively iterate through an array
by blue_cowdawg (Monsignor) on Mar 14, 2013 at 15:39 UTC
        I hope this all makes sense and thanks in advance for any help or insight!

    not really.. at least to me...

    Which values are considered "starting" and which are considered "ending?"


    Peter L. Berghold -- Unix Professional
    Peter -at- Berghold -dot- Net; AOL IM redcowdawg Yahoo IM: blue_cowdawg
      Each item in the array is a starting and ending value (colon delimited), so in the above example $VAR1 = 0:6, 0 is the starting value and 6 is the ending value, and so on for each array item.
Re: Selectively iterate through an array
by kcott (Chancellor) on Mar 14, 2013 at 19:54 UTC

    G'day jaiieq,

    I appear to have identified more paths than you show (e.g. 0:6 6:12 12:24 is not in your list). Here's the code:

    #!/usr/bin/env perl -l use strict; use warnings; my %route_from; my %routes_starting_at; my @paths = qw{0:6 0:12 0:18 0:24 6:12 6:18 6:24 12:18 12:24 18:24}; map { push @{$route_from{$_->[0]}}, $_->[1] } map { [ split /:/ ] } @p +aths; for my $s (sort { $b <=> $a } keys %route_from) { for my $e (sort { $a <=> $b } @{$route_from{$s}}) { my $path = "$s:$e"; if (exists $routes_starting_at{$e}) { for my $r (@{$routes_starting_at{$e}}) { my $ext_path = join ' ' => $path, $r; push @{$routes_starting_at{$s}}, $ext_path; } } else { push @{$routes_starting_at{$s}}, $path; } } } for my $k (sort { $a <=> $b } keys %routes_starting_at) { print for @{$routes_starting_at{$k}}; }

    Output:

    $ pm_start_end_graph.pl 0:6 6:12 12:18 18:24 0:6 6:12 12:24 0:6 6:18 18:24 0:6 6:24 0:12 12:18 18:24 0:12 12:24 0:18 18:24 0:24 6:12 12:18 18:24 6:12 12:24 6:18 18:24 6:24 12:18 18:24 12:24 18:24

    -- Ken

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1023490]
Approved by blue_cowdawg
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (8)
As of 2017-11-20 20:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    In order to be able to say "I know Perl", you must have:













    Results (293 votes). Check out past polls.

    Notices?