Linux tools to treat files as sets and perform set operations on them
Assuming elements are strings of characters other than NUL and newline (beware that newline is valid in file names though), you can represent a set as a text file with one element per line and use some of the standard Unix utilities.
Set Membership
$ grep -Fxc 'element' set # outputs 1 if element is in set
# outputs >1 if set is a multi-set
# outputs 0 if element is not in set
$ grep -Fxq 'element' set # returns 0 (true) if element is in set
# returns 1 (false) if element is not in set
$ awk '$0 == "element" { s=1; exit }; END { exit !s }' set
# returns 0 if element is in set, 1 otherwise.
$ awk -v e='element' '$0 == e { s=1; exit } END { exit !s }'
Set Intersection
$ comm -12 <(sort set1) <(sort set2) # outputs intersect of set1 and set2
$ grep -xF -f set1 set2
$ sort set1 set2 | uniq -d
$ join -t <(sort A) <(sort B)
$ awk '!done { a[$0]; next }; $0 in a' set1 done=1 set2
Set Equality
$ cmp -s <(sort set1) <(sort set2) # returns 0 if set1 is equal to set2
# returns 1 if set1 != set2
$ cmp -s <(sort -u set1) <(sort -u set2)
# collapses multi-sets into sets and does the same as previous
$ awk '{ if (!($0 in a)) c++; a[$0] }; END{ exit !(c==NR/2) }' set1 set2
# returns 0 if set1 == set2
# returns 1 if set1 != set2
$ awk '{ a[$0] }; END{ exit !(length(a)==NR/2) }' set1 set2
# same as previous, requires >= gnu awk 3.1.5
Set Cardinality
$ wc -l < set # outputs number of elements in set
$ awk 'END { print NR }' set
$ sed '$=' set
Subset Test
$ comm -23 <(sort -u subset) <(sort -u set) | grep -q '^'
# returns true iff subset is not a subset of set (has elements not in set)
$ awk '!done { a[$0]; next }; { if !($0 in a) exit 1 }' set done=1 subset
# returns 0 if subset is a subset of set
# returns 1 if subset is not a subset of set
Set Union
$ cat set1 set2 # outputs union of set1 and set2
# assumes they are disjoint
$ awk 1 set1 set2 # ditto
$ cat set1 set2 ... setn # union over n sets
$ sort -u set1 set2 # same, but doesn't assume they are disjoint
$ sort set1 set2 | uniq
$ awk '!a[$0]++' set1 set2 # ditto without sorting
Set Complement
$ comm -23 <(sort set1) <(sort set2)
# outputs elements in set1 that are not in set2
$ grep -vxF -f set2 set1 # ditto
$ sort set2 set2 set1 | uniq -u # ditto
$ awk '!done { a[$0]; next }; !($0 in a)' set2 done=1 set1
Set Symmetric Difference
$ comm -3 <(sort set1) <(sort set2) | tr -d '\t' # assumes not tab in sets
# outputs elements that are in set1 or in set2 but not both
$ sort set1 set2 | uniq -u
$ cat <(grep -vxF -f set1 set2) <(grep -vxF -f set2 set1)
$ grep -vxF -f set1 set2; grep -vxF -f set2 set1
$ awk '!done { a[$0]; next }; $0 in a { delete a[$0]; next }; 1;
END { for (b in a) print b }' set1 done=1 set2
Power Set
All possible subsets of a set displayed space separated, one per line:
$ p() { [ "$#" -eq 0 ] && echo || (shift; p "$@") |
while read r; do printf '%s %s\n%s\n' "$1" "$r" "$r"; done; }
$ p $(cat set)
(assumes elements don't contain SPC, TAB (assuming the default value of $IFS), backslash, wildcard characters).
Set Cartesian Product
$ while IFS= read -r a; do while IFS= read -r b; do echo "$a, $b"; done < set1; done < set2
$ awk '!done { a[$0]; next }; { for (i in a) print i, $0 }' set1 done=1 set2
Disjoint Set Test
$ comm -12 <(sort set1) <(sort set2) # does not output anything if disjoint
$ awk '++seen[$0] == 2 { exit 1 }' set1 set2 # returns 0 if disjoint
# returns 1 if not
Empty Set Test
$ wc -l < set # outputs 0 if the set is empty
# outputs >0 if the set is not empty
$ grep -q '^' set # returns true (0 exit status) unless set is empty
$ awk '{ exit 1 }' set # returns true (0 exit status) if set is empty
Minimum
$ sort set | head -n 1 # outputs the minimum (lexically) element in the set
$ awk 'NR == 1 { min = $0 }; $0 < min { min = $0 }; END { print min }'
# ditto, but does numeric comparison when elements are numerical
Maximum
$ sort test | tail -n 1 # outputs the maximum element in the set
$ sort -r test | head -n 1
$ awk '$0 > max { max = $0 }; END { print max }'
# ditto, but does numeric comparison when elements are numerical
All available at http://www.catonmat.net/blog/set-operations-in-unix-shell-simplified/
Sort of. You need to deal with sorting yourself, but comm can be used to do that, treating each line as a set member: -12 for intersection, -13 for difference. (And -23 gives you flipped difference, that is, set2 - set1 instead of set1 - set2.) Union is sort -u in this setup.
The tiny console tool “setop” is now availible in Debian Stretch and in Ubuntu since 16.10. You can get it via
sudo apt install setop
Here are some examples. The sets to be operated on are given as different input files:
setop input # is equal to "sort input --unique"
setop file1 file2 --union # option --union is default and can be omitted
setop file1 file2 file3 --intersection # more than two inputs are allowed
setop file1 - --symmetric-difference # ndash stands for standard input
setop file1 -d file2 # all elements contained in 1 but not 2
Boolean queries return only EXIT_SUCCESS in case of true, and EXIT_FAILURE as well as a message otherwise. This way, setop can be used in the shell.
setop inputfile --contains "value" # is element value contained in input?
setop A.txt B.txt --equal C.txt # union of A and B equal to C?
setop bigfile --subset smallfile # analogous --superset
setop -i file1 file2 --is-empty # intersection of 1 and 2 empty (disjoint)?
It is also possible to precisly describe how the input streams shall be parsed, actually by regular expressions:
setop input.txt --input-separator "[[:space:]-]"means that a whitespace (i. e.\v\t\n\r\for space) or a minus sign is interpreted as a separator between elements (default is new line, i. e. every line of the input file is one element)setop input.txt --input-element "[A-Za-z]+"means that elements are only words consisting of latin characters, all other characters are considered to be separators between elements
Furthermore, you can
--countall elements of the output set,--trimall input elements (i. e. erase all unwanted preceding and succeeding characters like space, comma etc.),- consider empty elements as valid via
--include-empty, --ignore-case,- set the
--output-separatorbetween elements of the output stream (default is\n), - and so on.
See man setop or github.com/phisigma/setop for more information.