mjhjmtu

I have a file df like:

1 4
1 6
1 7
1 10
2 3
2 9
2 10
3 4
4 7
9 10

I need to identify the smallest set of values such that every row in df contains at least one of these values.

From the above df the desired out is:

1
2
4
9

I have a process that works but is terribly slow. Is there a way I can execute this more quickly or parallelize the process?

x=1 
while [ $x -gt 0 ] 
do 
i=$(paste df | tr 't' 'n' | sort | uniq -c | sort -r -k1,1 -k2,2n | awk 'NR==1print $2') 
echo $i >> out 
grep -vw $i df > tmpdf 
cat tmpdf > df 
x=$(paste df | wc -l) 
done

Here's some "line-noisy" perl:

perl -lane '
 for $f (@F) push @$x$f, $. # 1.
 END {
 use List::Util qw/any first/;
 sub sort_by_count_desc 
 map $_->[0] 
 sort $a->[0] <=> $b->[0] 
 map [$_, scalar(@$x$_)] 
 @_ 
 
 @ordered = sort_by_count_desc(keys %x); # 2.
 %result = ();
 for ($i=1; $i<=$.; $i++) # 3.
 $node = first any $_ == $i @$x$_ @ordered; # 4.
 $result$node = 1;
 
 print join "n", sort_by_count_desc(keys %result);
' df

Where

1. loops over the lines of the file and maps each value to the list of lines it appears on


2. creates an ordered line of the values sorted by the size of the list of appearances, descending


3. loops over the range of line numbers, and foreach line number


4. finds the first value for which the line number appears

This outputs

1
2
4
10