# pkrumins/set-operations-in-unix-shell

Fetching contributors…
Cannot retrieve contributors at this time
executable file 214 lines (134 sloc) 6.11 KB
 .----------------------------------------------------------------------------. | | | Set Operations in the Unix Shell v1.01 | | | '----------------------------------------------------------------------------' | Peteris Krumins (peter@catonmat.net), 2008.12.02 | | http://www.catonmat.net - good coders code, great reuse | | | | Released under the GNU Free Document License | '----------------------------------------------------------------------------' Set operations covered in this document: ---------------------------------------- - Set Membership. - Set Equality. - Set Cardinality. - Subset Test. - Set Union. - Set Intersection. - Set Complement. - Set Symmetric Difference. - Power Set. - Set Cartesian Product. - Disjoint Set Test. - Empty Set Test. - Minimum. - Maximum. Full explanation of these operations at: http://www.catonmat.net/blog/set-operations-in-unix-shell/ Set Membership -------------- \$ grep -xc '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 -xq '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 Set Equality ------------ \$ diff -q <(sort set1) <(sort set2) # returns 0 if set1 is equal to set2 # returns 1 if set1 != set2 \$ diff -q <(sort set1 | uniq) <(sort set2 | uniq) # 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 | cut -d' ' -f1 # outputs number of elements in set \$ wc -l < set \$ awk 'END { print NR }' set Subset Test ----------- \$ comm -23 <(sort subset | uniq) <(sort set | uniq) | head -1 # outputs something if subset is not a subset of set # does not putput anything if subset is a subset of set \$ awk 'NR==FNR { a[\$0]; next } { if !(\$0 in a) exit 1 }' set 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 \$ cat set1 set2 | sort -u # same, but assumes they are not disjoint \$ sort set1 set2 | uniq \$ sort -u set1 set2 \$ awk '!a[\$0]++' # ditto Set Intersection ---------------- \$ comm -12 <(sort set1) <(sort set2) # outputs insersect of set1 and set2 \$ grep -xF -f set1 set2 \$ sort set1 set2 | uniq -d \$ join <(sort -n A) <(sort -n B) \$ awk 'NR==FNR { a[\$0]; next } \$0 in a' set1 set2 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 'NR==FNR { a[\$0]; next } !(\$0 in a)' set2 set1 Set Symmetric Difference ------------------------ \$ comm -3 <(sort set1) <(sort set2) | sed 's/\t//g' # outputs elements that are in set1 or in set2 but not both \$ comm -3 <(sort set1) <(sort set2) | tr -d '\t' \$ 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 'NR==FNR { a[\$0]; next } \$0 in a { delete a[\$0]; next } 1; END { for (b in a) print b }' set1 set2 Power Set --------- \$ p() { [ \$# -eq 0 ] && echo || (shift; p "\$@") | while read r ; do echo -e "\$1 \$r\n\$r"; done } \$ p `cat set` # no nice awk solution, you are welcome to email me one: peter@catonmat.net Set Cartesian Product --------------------- \$ while read a; do while read b; do echo "\$a, \$b"; done < set1; done < set2 \$ awk 'NR==FNR { a[\$0]; next } { for (i in a) print i, \$0 }' set1 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 | cut -d' ' -f1 # outputs 0 if the set is empty # outputs >0 if the set is not empty \$ wc -l < set \$ awk '{ exit 1 }' set # returns 0 if set is empty, 1 otherwise Minimum ------- \$ head -1 <(sort set) # outputs the minimum element in the set \$ awk 'NR == 1 { min = \$0 } \$0 < min { min = \$0 } END { print min }' Maximum ------- \$ tail -1 <(sort set) # outputs the maximum element in the set \$ awk 'NR == 1 { max = \$0 } \$0 > max { max = \$0 } END { print max }' .---------------------------------------------------------------------------. | Peteris Krumins (peter@catonmat.net), 2008.12.02 | | http://www.catonmat.net - good coders code, great reuse | | | | Released under the GNU Free Document License v1.01 | | | | Thanks to waldner and pgas from #awk on FreeNode | | Power set function by Andreas: http://lysium.de/blog | '---------------------------------------------------------------------------'