Inverting an associative array

Question

Let's say I have an associative array in bash,

declare -A hash
hash=(
    ["foo"]=aa
    ["bar"]=bb
    ["baz"]=aa
    ["quux"]=bb
    ["wibble"]=cc
    ["wobble"]=aa
)

where both keys and values are unknown to me (the actual data is read from external sources).

How may I create an array of the keys corresponding to the same value, so that I may, in a loop over all unique values, do

printf 'Value "%s" is present with the following keys: %s\n' "$value" "${keys[*]}"

and get the output (not necessarily in this order)

Value "aa" is present with the following keys: foo baz wobble
Value "bb" is present with the following keys: bar quux
Value "cc" is present with the following keys: wibble

The important bit is that the keys are stored as separate elements in the keys array and that they therefore do not need to be parsed out of a text string.

I could do something like

declare -A seen
seen=()
for value in "${hash[@]}"; do
    if [ -n "${seen[$value]}" ]; then
        continue
    fi

    keys=()
    for key in "${!hash[@]}"; do
        if [ "${hash[$key]}" = "$value" ]; then
            keys+=( "$key" )
        fi
    done

    printf 'Value "%s" is present with the following keys: %s\n' \
        "$value" "${keys[*]}"

    seen[$value]=1
done

But it seems a bit inefficient with that double loop.

Is there a piece of array syntax that I've missed for bash?

Would doing this in e.g. zsh give me access to more powerful array manipulation tools?

In Perl, I would do

my %hash = (
    'foo'    => 'aa',
    'bar'    => 'bb',
    'baz'    => 'aa',
    'quux'   => 'bb',
    'wibble' => 'cc',
    'wobble' => 'aa'
);

my %keys;
while ( my ( $key, $value ) = each(%hash) ) {
    push( @{ $keys{$value} }, $key );
}

foreach my $value ( keys(%keys) ) {
    printf( "Value \"%s\" is present with the following keys: %s\n",
        $value, join( " ", @{ $keys{$value} } ) );
}

But bash associative arrays can't hold arrays...

I'd also be interested in any old school solution possibly using some form of indirect indexing (building a set of index array(s) when reading the values that I said I had in hash above?). It feels like there ought to be a way to do this in linear time.

Answer 1

zsh

to reverse keys <=> values

In zsh, where the primary syntax for defining a hash is hash=(k1 v1 k2 v2...) like in perl (newer versions also support the awkward ksh93/bash syntax for compatibility though with variations when it comes to quoting the keys)

keys=("${(@k)hash}")
values=("${(@v)hash}")

typeset -A reversed
reversed=("${(@)values:^keys}") # array zipping operator

or using a loop:

for k v ("${(@kv}hash}") reversed[$v]=$k

The @ and double quotes is to preserve empty keys and values (note that bash associative arrays don't support empty keys). As the expansion of elements in associative arrays is in no particular order, if several elements of $hash have the same value (which will end up being a key in $reversed), you can't tell which key will be used as the value in $reversed.

for your loop

You'd use the R hash subscript flag to get elements based on value instead of key, combined with e for exact (as opposed to wildcard) match, and then get the keys for those elements with the k parameter expansion flag:

for value ("${(@u)hash}")
  print -r "elements with '$value' as value: ${(@k)hash[(Re)$value]}"

your perl approach

zsh (contrary to ksh93) doesn't support arrays of arrays, but its variables can contain the NUL byte, so you could use that to separate elements if the elements don't otherwise contain NUL bytes, or use the ${(q)var} / ${(Q)${(z)var}} to encode/decode a list using quoting.

typeset -A seen
for k v ("${(@kv)hash}")
  seen[$v]+=" ${(q)k}"

for k v ("${(@kv)seen}")
  print -r "elements with '$k' as value: ${(Q@)${(z)v}}"

ksh93

ksh93 was the first shell to introduce associative arrays in 1993. The syntax for assigning values as a whole means it's very difficult to do it programmatically contrary to zsh, but at least it's somewhat justified in ksh93 in that ksh93 supports complex nested data structures.

In particular, here ksh93 supports arrays as values for hash elements, so you can do:

typeset -A seen
for k in "${!hash[@]}"; do
  seen[${hash[$k]}]+=("$k")
done

for k in "${!seen[@]}"; do
  print -r "elements with '$k' as value ${x[$k][@]}"
done

bash

bash added support for associative arrays decades later, copied the ksh93 syntax, but not the other advanced data structures, and doesn't have any of the advanced parameter expansion operators of zsh.

In bash, you could use the quoted list approach mentioned in the zsh using printf %q or with newer versions ${var@Q}.

typeset -A seen
for k in "${!hash[@]}"; do
  printf -v quoted_k %q "$k"
  seen[${hash[$k]}]+=" $quoted_k"
done

for k in "${!seen[@]}"; do
  eval "elements=(${seen[$k]})"
  echo -E "elements with '$k' as value: ${elements[@]}"
done

As noted earlier however, bash associative arrays don't support the empty value as a key, so it won't work if some of $hash's values are empty. You could choose to replace the empty string with some place holder like <EMPTY> or prefix the key with some character that you'd later strip for display.

Answer 2

The stumbling block, as I'm sure you know, is to get the whole value of an indexed array when having its name as value of a (another) variable. I couldn't do it with less than having an intermediate whose value becomes of format ${v[@]} and then use eval on that. So, here's that approach:

declare -A keys
N=0 # counter for the index variables IX1, IX2, IX3, ...
for key in "${!hash[@]}"; do
    value="${hash[$key]}"
    if [ -z "${keys[$value]}" ] ; then N=$((N+1)) ; keys[$value]=IX$N ; fi
    index="${keys[$value]}" # 'index' is now name of index variable
    X="\${$index[@]}"
    eval "$index=( $X $key )" # adding next key to it
done

for value in "${!keys[@]}" ; do
    index=${keys[$value]}
    X="\${$index[@]}"
    printf "Value %s is present with the following keys: %s\n" \
       "$value" "$(eval echo "$X")"
done

This is for Linux bash. It creates indexed arrays IX1, IX2, etc., for the various values it encounters, and holds those names in the keys associative array for the values. Thus, ${keys[$value]} is the name of the indexed array that holds the keys for that value. Then X is set up to be the variable "access phrase" for the collection of values, allowing eval echo "$X" to translate into those values with space separation. For example, if a value has indexed array IX2, then X will be the string ${IX2[@]}.

I believe zsh is similar in not supporting arrays of arrays, so it'd probably require a similar solution. IMHO though, the access phrases in zsh are slightly clearer.

Answer 3

Here is an alternative approach - have data in two indexed arrays. One of them has unique values and the second can contain repeated/duplicate values. One can constuct the associative array which has duplicating elements from the second array as keys and corresponding entries from the first array as values separated by space.

The code below avoids using eval and uses only a for loop

code

source=("foo" "bar" "baz" "quux" "wibble" "wobble")
destination=("aa" "bb" "aa" "bb" "cc" "aa")

declare -A inverted_array

# Printout formatted arrays with headers
printf '%-10s %-20s %-30s\n' "Index" "Destination" "Source"

for ((i = ((${#source[@]} - 1)); i >= 0; i--)); do

    source_i="${source["$i"]}"
    destination_i="${destination["$i"]}"

    printf '%-10s %-20s %-30s\n' "$i" "$destination_i" "$source_i"

    tempstring="${inverted_array["$destination_i"]}"
    inverted_array["$destination_i"]="$source_i"" ""$tempstring"

done
echo
printf '%-10s %-20s\n' "Key" "Value"

# Remove the last space from the every element of the resulted array and print it formatted
for index in "${!inverted_array[@]}"; do

    removespace="${inverted_array[$index]}"
    removespace=${removespace%" "}
    inverted_array["$index"]="$removespace"
    printf '%-10s %-20s\n' "$index" "${inverted_array["$index"]}"
done
echo

Output:

Index      Destination          Source
5          aa                   wobble
4          cc                   wibble
3          bb                   quux
2          aa                   baz
1          bb                   bar
0          aa                   foo

Key        Value
bb         bar quux
aa         foo baz wobble
cc         wibble

P.S. To expand/demonatrate the above example even more - here is a following code which genenrates two arrays. One of them - source containing 5 char long random characters and the second - destination contains just as a values only random one char 0-9a-f.

Code to generate two index arrays each with 100 elements:

    for ((i = 0; i < 100; i++)); do
        source+=("$(tr -dc 'a-zA-Z' </dev/urandom | head -c 5)")
        destination+=("$(tr -dc '0-9a-f' </dev/urandom | head -c 1)")
    done

Using the above code to create an associative array, the result is following:

Key        Value
9          soxRg PmUZv eOmkR cFuie wmlsO EdNdM XuloF SSfjE oHfnc FcIKE
8          hLRpa eXODM wRGkh MwZUW lfWaE WQiwU IHGjj nNEcg
7          Pdxmd ywPZQ lPQIx TKawd VTyqR
6          lIwla Docxu Dimnz ovywP HwzQv
5          ObezH tyFNS BqnWp CFlMk dDkYC
4          rNzLM GVLXH AgZSL ionEp tngzQ
3          yRfqn IdTne
2          sMSxm WKmGm ELjOL pqxqw stWnL
1          yxycd EAGRg WxBle ItLNz WUdVu shUaC qDNIO xIwdM
0          OXdHh VQcsT AFvFq sgrYK AQrjZ
f          uXJor IkwDr AOGSK hYMGE PQQfu tUjbh NwrVi iqZKO hHLYU
e          XhMpB TCCFr ATbxa
d          ReqMh lbxFx bGivd YCGtv lAtZj
c          Kvthr itbaF wIbaf LwUiB VTInv xvWbC gpyRZ
b          riimt EkLbv QYpZq kgvTi tOJRH jZykW pRuMD FJVXZ xipDx wkCMN
a          REJnb Xtunv raimk SemnZ xMwno EXwKi sekmg WUKhx