How do I pass the resulting files from one grep pass to another so that I only grep through the subset with the second pass?

Question

Hello All,

I want to be able to take the files I found with my first grep statement, something like this for example: grep -r Makefile * And then pass the files found in that pass of grep to a second grep with something like this for example: grep {files} '-lfoo'

How do I do this? I know there must be a way.

Thank you.

Answer 1

Like the subset sum problem, this problem is weakly NP-complete, so it has a solution that runs in time polynomial(M), where M is the sum of all numbers appearing in the problem instance. You can achieve that with dynamic programming. For each set you can generate all possible sums by filling a 2-dimensional binary table, where "true" at (k,m) means that a subset sum m can be achieved by picking some elements from the first k elements of the set.

You fill it iteratively - you set (k,m) to "true" if (k-1,m) is set to "true" (obviously, if you can get m from k-1 elements, you can get it from k elements by not picking the k-th) or if (k-1,m-d) is set to "true" where d is the value of k-th element in the set (the case where you pick the k-th element).

Filling the table gets you all the possible sums in the last column (the one representing the whole set). Do this for both sets and find common sums. You can backtrack the actual subsets representing the solutions by reversing the process which you used to fill the tables.