22
$\begingroup$

Lists of Rules or Associations are both a useful way of mapping between values. It also allows us to use handy functions like

Lookup[key]@ rules
(*value*)
(*Alternatively: Lookup[rules, key]*)

Lookup[key]@ assoc
(*value*)
(*Alternatively: Lookup[assoc, key]*)

Unfortunately, there is not a built-in reverse, i.e. given the value, what key(s) are associated to that value.

What is an efficient alternative to do so?

$\endgroup$
1
  • $\begingroup$ I recommend using an Association instead of aList if your keys in each List are unique. Then you could just use Position. $\endgroup$
    – Edmund
    Nov 1, 2016 at 8:29

9 Answers 9

23
$\begingroup$
 PositionIndex[assoc][<value>]

For example:

assoc = <|a -> 1, b -> 2, c -> 3, d -> 1, e -> 4, f -> 1|>;
PositionIndex[assoc][1]

{a, d, f}

And

PositionIndex[assoc]

<|1 -> {a, d, f}, 2 -> {b}, 3 -> {c}, 4 -> {e}|>

Alternatively:

PositionIndex[assoc] // Lookup[4]

{e}

$\endgroup$
2
  • 2
    $\begingroup$ I think this should be the accepted answer for this question. $\endgroup$
    – WReach
    Jun 27, 2017 at 17:15
  • $\begingroup$ @WReach I am surprised that no one thought to post this before (clearly I didn't) but it should be noted that it is slower than a one-off operation with Position, or Pick for that matter, and it isn't clear from the original question this operation would be repeated or not. $\endgroup$
    – Mr.Wizard
    Jun 28, 2017 at 12:05
19
$\begingroup$

One way would be to "invert" the association and then look up values in the result:

$a = <| "a" -> 1, "b" -> 2, "c" -> 1, "d" -> 2, "e" -> 3 |>;


$inv = $a // Normal // GroupBy[Last -> First]

(* <| 1 -> {a, c}, 2 -> {b, d}, 3 -> {e} |> *)


$inv[1]

(* {a, c} *)

If the original collection is a list of rules instead of an association, Normal can be left out.

If an association has a one-to-one mapping of keys to values then (in V11) there is a built-in, but undocumented, function that does the inversion:

$a2 = <| "a" -> 1, "b" -> 2, "c" -> 3 |>;

Needs["GeneralUtilities`"]
AssociationInvert[$a2]

(* <| 1 -> a, 2 -> b, 3 -> c |> *)
$\endgroup$
6
  • $\begingroup$ What version has GeneralUtilities`InvertAssociation? I can't seem to find it on my system. $\endgroup$
    – Greg Hurst
    Nov 1, 2016 at 14:50
  • $\begingroup$ @ChipHurst I'm using V11.0.1. I updated the response to indicate that it is a V11 function. Thanks. $\endgroup$
    – WReach
    Nov 1, 2016 at 14:53
  • 1
    $\begingroup$ (+1) If you don't care about collisions, i.e. the association is a one-to-one map, you can do invertAssociation[assoc_?AssociationQ] := Association[KeyValueMap[#2 -> #1 &, assoc]]. It seems to be twice as fast as the GroupBy approach. $\endgroup$
    – Greg Hurst
    Nov 1, 2016 at 14:59
  • $\begingroup$ Ah, it's AssociationInvert not InvertAssociation... No wonder I couldn't find it :) $\endgroup$
    – Greg Hurst
    Nov 1, 2016 at 15:02
  • 5
    $\begingroup$ It's implementation is simply AssociationInvert [assoc_] := AssociationThread[Values[assoc], Keys[assoc]]. Should have thought to do that! $\endgroup$
    – Greg Hurst
    Nov 1, 2016 at 15:04
10
$\begingroup$

You may use Position on an Association to return the Key (or keys) that holds a value.

With

assoc = <|a -> 1, b -> 2, c -> 3, d -> 1, e -> 4, f -> 1|>;

Then

Position[assoc, 4]
{{Key[e]}}
Position[assoc, 1]
{{Key[a]}, {Key[d]}, {Key[f]}}

These can be used with Extract,

Extract[Position[assoc, 1]]@assoc
{1, 1, 1}

Or with Query

Query[Position[assoc, 1]]@assoc
{<|a -> 1|>, <|d -> 1|>, <|f -> 1|>}

or

Query[Flatten@Position[assoc, 1]]@assoc
<|a -> 1, d -> 1, f -> 1|>

Hope this helps.

$\endgroup$
3
  • $\begingroup$ What you have above work, but doesn't quite give what I envisioned as the output. I mean, it works, but you why would you want to Extract the value from the position? You entered it as a parameter, i.e. you already know what it is? The idea is to get the Key from the Value $\endgroup$
    – SumNeuron
    Nov 1, 2016 at 8:50
  • 1
    $\begingroup$ @SumNeuron Position gives you the Key. Just showing ways to use the output of Position to go the other way as many first-time users don't know what to do with it. $\endgroup$
    – Edmund
    Nov 1, 2016 at 8:52
  • $\begingroup$ Good point. I must admit at first I was really bother with Position returning such nested output. $\endgroup$
    – SumNeuron
    Nov 1, 2016 at 8:54
10
$\begingroup$

Pick may be worthy of consideration:

kfv = Pick[Keys @ #, Values @ #, #2] &;

rules = {a -> 1, b -> 2, c -> 3, d -> 1, e -> 4, f -> 1};
assoc = <|a -> 1, b -> 2, c -> 3, d -> 1, e -> 4, f -> 1|>;

kfv[rules, 1]
kfv[assoc, 1]
{a, d, f}

{a, d, f}
$\endgroup$
7
$\begingroup$

There's a certain elegance to:

GroupBy[assoc, Identity, Keys]         (* gives all keys for a given value *)

GroupBy[assoc, Identity, First@*Keys]  (* gives first key for a given value *)
GroupBy[assoc, Identity, Last@*Keys]   (* gives last key for a given value *)

But it's no more efficient than @WReach's GroupBy solution for all keys, and much less efficient than the "GeneralUtilities`" solution for the (partial) inverse function he also gives:

AssociationInvert[assoc] :=            (* gives last key for a given value *)
 AssociationThread[Values@assoc, Keys@assoc]

(The code for AssociationInvert[] was first noted by Chip Hurst in a comment. I thought it deserved a mention in an answer, since it's simple and built out of documented functions.)

$\endgroup$
4
$\begingroup$

you can use Select as well:

assoc = <|a -> 1, b -> 2, c -> 3, d -> 1, e -> 4, f -> 1|>;
Keys[Select[assoc, # == 1 &]]

{a , d , f}

$\endgroup$
3
$\begingroup$

Regarding the answer of WReach

AssociationMap[Reverse] delivers the same result as AssociationInvert:

asc = <|a -> 1, b -> 2, c -> 3, d -> 1, e -> 4, f -> 1|>;

AssociationMap[Reverse] @ asc

(* <|1 -> f, 2 -> b, 3 -> c, 4 -> e|> *)

Needs["GeneralUtilities`"]
AssociationInvert[asc]

(* <|1 -> f, 2 -> b, 3 -> c, 4 -> e|> *)

$\endgroup$
2
$\begingroup$

Assuming a simple List of Rules, e.g.

rules = {
a -> 1,
b -> 2,
c -> 3,
d -> 1,
e -> 4,
f -> 1
};

The following function allows one to get various amounts of key(s) associated with the specified value, using familiar list operators First, Most, Rest, and Last. One can also specify All (typically an option) to get All keys associated with value. In addition, one can specify which key they want. The code is at the bottom of this post.

Examples

Using the rules defined above:

Default: return first instance of a key associated with the value

KeyFromValue[rules, 1]
(*a*)

Playing around with the option "Which":

KeyFromValue[rules, 1, "Which" -> Last]
(*f*)
KeyFromValue[rules, 1, "Which" -> All]
(*{a, d, f}*)
KeyFromValue[rules, 1, "Which" -> Most]
(*{a, d}*)
KeyFromValue[rules, 1, "Which" -> 2]
(*d*)

There is some limited error handling:

KeyFromValue[rules, 1, "Which" -> 5]
Asked for 5th instance of 1.
Only 3  instances found.
Out: {}

KeyFromValue[rules, 10]
Nothing found
Out: {}

Update

Added alternative definition to handle association:

assoc = <|a -> 1, b -> 2, c -> 3, d -> 1, e -> 4, f -> 1|>;

KeyFromValue[rules, 1]
KeyFromValue[assoc, 1]
KeyFromValue[rules, 1, "Which" -> Most]
KeyFromValue[assoc, 1, "Which" -> Most]

a
a
{a, d}
{a, d}

Code

I'm not claiming this is the most efficient means of doing so, but it does serve its purpose. Kudos to anyone who wants to abstract this for any list of rules.

Options[KeyFromValue] = {"Which" -> 1, "Verbose" -> False};
KeyFromValue[association_List, value_, OptionsPattern[]] :=
 Module[
  {found = First /@ Position[association, value]},

  (*If that value is not found*)
  If[found == {},

   (*Return empty List*)

   If[OptionValue[KeyFromValue, "Verbose"], Print["Nothing found"];]

    Return[{}],

   (*Else rename the position wanted as pos*)

   With[{pos = OptionValue[KeyFromValue, "Which"]},


    (*If pos is a function that returns an unwrapped singular value*)

        If[MemberQ[{First, Last}, pos],
     (*Apply the function. Return it.*)

     Return[First@association[[#]] &@(pos@found)],

     (*If pos is a function that returns a List*)

     If[MemberQ[{Most, Rest}, pos],
      (*Apply the function. Return it.*)

      Return[First /@ (association[[#]] & /@ (pos@found))],

      (*If pos is All (technically not a function)*)

      If[MemberQ[{All}, pos],

       (*Given them everything found*)

       Return[First /@ (association[[#]] & /@ (found))],

       (*Else, check to see if position valid.*)

       If[pos <= Length@found,
        (*If it is, return desired value.*)

        Return[First@association[[found[[pos]]]]],
        (*Else notify user and return {}.*)

        If[OptionValue[KeyFromValue, "Verbose"], 
         Print["Asked for " <> ToString@pos <> "th instance of " <> 
            ToString@value <> ".\nOnly " <> 
            ToString[Length@found]  " instances found."]];
        Return[{}];
        ]
       ]
      ]
     ]

    ]
   ]
  ]


Options[KeyFromValue] = {"Which" -> 1, "Verbose" -> False};
KeyFromValue[association_Association, value_, OptionsPattern[]] :=

 Module[
  {found = First /@ First /@ Position[association, value]},

  (*If that value is not found*)
  If[found == {},
   (*Return Missing List*)

   If[OptionValue[KeyFromValue, "Verbose"], Print["Nothing found"];];
   Return[Missing];
   ];

  (*Else rename the position wanted as pos*)

  With[{pos = OptionValue[KeyFromValue, "Which"]},

   (*If pos is a function that returns an unwrapped singular value*)

     If[MemberQ[{First, Last, Most, Rest}, pos],
    (*Apply the function. Return it.*)
    Return[(pos@found)],

    (*If pos is All (technically not a function)*)

    If[MemberQ[{All}, pos],

     (*Given them everything found*)
     Return[(found)],

     (*Else, check to see if position valid.*)

     If[pos <= Length@found,

      (*If it is, return desired value.*)
      Return[found[[pos]]],
      (*Else notify user and return {}.*)

      If[OptionValue[KeyFromValue, "Verbose"], 
       Print["Asked for " <> ToString@pos <> "th instance of " <> 
          ToString@value <> ".\nOnly " <> 
          ToString[Length@found]  " instances found."]];
      Return[{}];
      ]
     ]

    ]

   ]
  ]
$\endgroup$
0
2
$\begingroup$

Another option is to use pattern matching to find the key you're looking for:

key = assoc /. <|___, n_ -> value, ___|> -> n

The downside is that it will only return the first match it finds so this is only good for 1 to 1 associations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.