# Reverse Lookup: getting keys from values

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?

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

 PositionIndex[assoc][<value>]


For example:

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


{a, d, f}

And

PositionIndex[assoc]


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

Alternatively:

PositionIndex[assoc] // Lookup


{e}

• I think this should be the accepted answer for this question. – WReach Jun 27 '17 at 17:15
• @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. – Mr.Wizard Jun 28 '17 at 12:05

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

(* {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 |> *)

• What version has GeneralUtilitiesInvertAssociation? I can't seem to find it on my system. – Chip Hurst Nov 1 '16 at 14:50
• @ChipHurst I'm using V11.0.1. I updated the response to indicate that it is a V11 function. Thanks. – WReach Nov 1 '16 at 14:53
• (+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. – Chip Hurst Nov 1 '16 at 14:59
• Ah, it's AssociationInvert not InvertAssociation... No wonder I couldn't find it :) – Chip Hurst Nov 1 '16 at 15:02
• It's implementation is simply AssociationInvert [assoc_] := AssociationThread[Values[assoc], Keys[assoc]]. Should have thought to do that! – Chip Hurst Nov 1 '16 at 15:04

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.

• 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 – SumNeuron Nov 1 '16 at 8:50
• @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. – Edmund Nov 1 '16 at 8:52
• Good point. I must admit at first I was really bother with Position returning such nested output. – SumNeuron Nov 1 '16 at 8:54

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}


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 *)


(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.)

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}

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[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[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[{}];
]
]

]

]
]


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.