You don't need to enumerate all possible combinations to solve this.

What you're looking for is longest common subsequence algorithm, aka diff. You need to compare your data with its own sorted copy.

Now any ordered subsequence of initial input is also a subsequence of the sorted input (well, this requires proof, but I'm too sleepy to come up with one). Therefore, it is guaranteed that the longest such subset will be selected by LCS.

Not sure which of these modules would fit your need, probably LCS::Tiny or LCS::XS.

Here's a working code sample:

#!/usr/bin/env perl

use strict;
use warnings;
use LCS::XS;

my @data = map { /(\d+)/g } <>;
my @odata = sort { $a <=> $b } @data;

my $alg = LCS::XS->new;
my @diff = $alg->LCS( \@data, \@odata ); # returns pairs or indices

# select elements with matching indices from data
my @subseq = map { $data[ $_->[0] ] } @diff;
print "@subseq\n";

# select same elements but from ordered data - result is identical
@subseq    = map { $odata[ $_->[1] ] } @diff;
print "@subseq\n";
[download]

UPDATE As BrowserUK points out, there's an even more efficient Longest increasing subsequence algorithm which is O(n ln n), while my proposed solution is only O(n*n).