Check for permutation using awk

Question

My problem is to determine via shell script if certain strings are permutations of each other e.g.

1.Nf3 c5 2.e4 Nc6
1.e4 c5 2.Nf3 Nc6

As you can see the permutation is based on atomic substrings. So in other words, I want to know if both strings containing same substrings without consider the order.

AWK is a programming language designed for advanced text processing. So one idea that comes up is to split both strings into arrays:

{1., Nf3, c5, 2., e4, Nc6}
{1., e4, c5, 2., Nf3, Nc6}

and compare if both consists same elements. But I'm not sure if this fits awk way.

A second approach is to split the first string into patterns {1., Nf3, c5, 2., e4, Nc6} and search in the second string for all patterns and create a new string based on those matches. After all I could check if the new string is equal to the first string. Are there any other approaches in awk for this specific text processing?

Answer 1

I don't think awk is the right way. Just split the strings, sort the string elements, and compare the result.

Example with bash:

$ split_and_sort() { sed -r 's/\</\n/g' | sort; }

$ split_sort_and_compare() {
    if [ "$(split_and_sort <<< "$1")" = "$(split_and_sort <<< "$2")" ]
    then echo "Match"
    else echo "No match"
    fi
}

$ split_sort_and_compare "1.Nf3 c5 2.e4 Nc6" "1.e4 c5 2.Nf3 Nc6"
Match

$ split_sort_and_compare "1.Nf3 c5 2.e4 Nc6" "1.e4 c5 2.Nf3 Nc5"
No match

This is just a crude example to illustrate my idea, with my own interpretation of how the strings have to be split and compared. Make your own more elaborate functions according to your rules.

Answer 2

Just for the record this is an awk solution (not very tricky though) in case you need to integrate this solution to any of your existed awk projects.

a="1.Nf3 c5 2.e4 Nc6"
b="1.e4 c5 2.Nf3 Nc6"
awk 'BEGIN{FS=""}{last=NF;for (i=1;i<=NF;i++) {if (NR==FNR) {a[i]=$i} else {b[i]=$i}}} \
{asort(a);asort(b)}END{{for (k=1;k<=last;k++) if (a[k]!=b[k]) nomatch++}{print (nomatch==0)?"match":"no match"}}' <(echo "$a") <(echo "$b")

If you just want to compare those two strings, i would go using some bash way either like the answer of xhienne advises or even something like this:

[[ $(sort <(grep -o . <<<"$a") |base64) == $(sort <(grep -o . <<<"$b") |base64) ]] && echo "match" || echo "differ"

In both cases the logic is the same. Input string are split per char, then sorted one by one and those two sorted strings are compared.

In above bash way, i thought to encode the sorted strings to base64 and compare their base64 values.

Answer 3

An alternative way to check if both strings contain the same chars could be to calculate the sum of their ASCII values.

$ while read -rn1 char;do sumA+=$(printf '%d+' "'$char'");done <<<"1.Nf3 c5 2.e4 Nc6"
$ while read -rn1 char;do sumB+=$(printf '%d+' "'$char'");done <<<"1.e4 c5 2.Nf3 Nc6"

$ echo "$sumA"
49+46+78+102+51+39+99+53+39+50+46+101+52+39+78+99+54+39+
$ echo "$sumB"
49+46+101+52+39+99+53+39+50+46+78+102+51+39+78+99+54+39+

$ bc <<<"${sumB:0:-1}"
1114
$ bc <<<"${sumA:0:-1}"
1114

Same numeric sum = same strings.Thus by comparing those two bc values you can have a match/nomatch condition.

If one char is different between strings ascii values sum will be different:

$ while read -rn1 char;do sumC+=$(printf '%d+' "'$char'");done <<<"1.Nf3 q5 2.e4 Nc6" #q5 is different than string A
$ echo "$sumC"
49+46+78+102+51+39+113+53+39+50+46+101+52+39+78+99+54+39+
$ bc <<<"${sumC:0:-1}"
1128