A recursive search does the trick so long as run time on typical data is not an issue:

use strict;
use warnings;

my @parts;

while (<DATA>) {
    my ($start, $end) = /(\d+)\D(\d+)/;

    next if !defined $end;
    push @parts, [$start, $end];
}

@parts = sort {$a->[0] <=> $b->[0] || $a->[1] <=> $b->[1]} @parts;
print join ('-', @$_), "\n" for trailsBetween(0, 2000, @parts);


sub trailsBetween {
    my ($prevEnd, $to, @parts) = @_;
    my @tails;

    return [$prevEnd] if $prevEnd == $to;

    while (@parts) {
        my ($start, $end) = @{shift @parts};

        last if $start > $prevEnd;
        next if $end < $prevEnd;
        push @tails, trailsBetween($end, $to, @parts);
    }

    unshift @$_, $prevEnd for @tails;
    return @tails;
}


__DATA__
0-200
0-1800
200-400
400-600
600-800
800-1000
1000-2000
[download]

Prints:

0-200-1800-2000
0-200-400-600-800-1000-2000
0-1800-2000
[download]

Best algorithm depends on many factors you didn't explained.

• motivation
• data size (speed matters?)
• data source (unique starts?)

And last but not least: what did you try so far? (we are not to keen doing other peoples homework)

Hi Rolf. I tried putting a hash as you suggested. However for some of the paths the starts are the same while the end is different. Also I am new to graphs. Can you maybe direct me to a backtracking algorithm or graph module that will do this trick. I have tried answering your question below. motivation: This is not a homework. I am trying to stitch together alignments from strings. I know the start and end of the positions of the strings that i can recover from my data. And from this I have to generate the full string in the quickest way possible. data size: the data size can vary greatly depending on the size of my input string. data source: The starts are not unique. Even in my example, there are two chunks starting with 0 (0-200) and 90-1800). hope this answers your question

Sorry I don't seem to understand your question.

For instance there is no 1800-2000 link, such that your last two "solutions" don't make much sense to me.

I'm only realizing it now because you didn't use any recommended formatting.

And since you are posting anonymously, you can't correct it. :(

Cheers Rolf

(addicted to the Perl Programming Language)

List::PowerSet can do this for you.

Here is a small program using the data you provided, (followed by the results of the run).

#!/usr/bin/perl
use strict;
use warnings;
use List::PowerSet qw(powerset);

my $nums = '0-200 200-400 400-600 600-800 800-1000 1000-2000 0,1800';
my %hash;
@hash{ split /\D+/, $nums } = ();

my @sorted = sort {$a<=> $b} keys %hash;
my $start = shift @sorted;
my $end = pop @sorted;

my $ps = powerset(@sorted);

for my $set (@$ps) {
    print join("-", $start, @$set, $end), "\n";    
}

__END__
0-200-400-600-800-1000-1800-2000
0-400-600-800-1000-1800-2000
0-200-600-800-1000-1800-2000
0-600-800-1000-1800-2000
0-200-400-800-1000-1800-2000
0-400-800-1000-1800-2000
0-200-800-1000-1800-2000
0-800-1000-1800-2000
0-200-400-600-1000-1800-2000
0-400-600-1000-1800-2000
0-200-600-1000-1800-2000
0-600-1000-1800-2000
0-200-400-1000-1800-2000
0-400-1000-1800-2000
0-200-1000-1800-2000
0-1000-1800-2000
0-200-400-600-800-1800-2000
0-400-600-800-1800-2000
0-200-600-800-1800-2000
0-600-800-1800-2000
0-200-400-800-1800-2000
0-400-800-1800-2000
0-200-800-1800-2000
0-800-1800-2000
0-200-400-600-1800-2000
0-400-600-1800-2000
0-200-600-1800-2000
0-600-1800-2000
0-200-400-1800-2000
0-400-1800-2000
0-200-1800-2000
0-1800-2000
0-200-400-600-800-1000-2000
0-400-600-800-1000-2000
0-200-600-800-1000-2000
0-600-800-1000-2000
0-200-400-800-1000-2000
0-400-800-1000-2000
0-200-800-1000-2000
0-800-1000-2000
0-200-400-600-1000-2000
0-400-600-1000-2000
0-200-600-1000-2000
0-600-1000-2000
0-200-400-1000-2000
0-400-1000-2000
0-200-1000-2000
0-1000-2000
0-200-400-600-800-2000
0-400-600-800-2000
0-200-600-800-2000
0-600-800-2000
0-200-400-800-2000
0-400-800-2000
0-200-800-2000
0-800-2000
0-200-400-600-2000
0-400-600-2000
0-200-600-2000
0-600-2000
0-200-400-2000
0-400-2000
0-200-2000
0-2000
[download]

Hi Cristoforo. I don't want all combinations. I only want paths. For example, from node 0 only two paths are possible - 0-200 and 0-1800. So to go from 0-2000 there are only, (0-200,200-400,400-600,600-800,800-1000,1000-2000),
(0-1800,1000-2000)
and (0-200,0-1800,1000-2000)
which is what i want my program to output.