9

I need to compare two Lists of Rules of form var -> integer on the fact of mismatch.
To determine, if there are any rules the same by lhs and different by rhs.

For example:

{a->3, b->1, c->4} ~ ??? ~ {a->3, b->1, c->4} = true
{a->3, b->1, c->4} ~ ??? ~ {a->3, b->2, c->4} = false
{a->3, b->1, c->4} ~ ??? ~ {a->1, b->3, c->4} = false
{a->3, b->1, c->4} ~ ??? ~ {c->4, d->8, e->9} = true
{a->3, b->1, c->4} ~ ??? ~ {d->8, e->9, f->7} = true

In my case they are already sorted by lhs and all lhs are unique if it could help to make as simple function as possible.

UPD: forgot one thing! Lists can be of different length. But seems like all three current answers are still valid.

Nakilon
  • 34,866
  • 14
  • 107
  • 142

4 Answers4

7

You could do something like

check[{a__Rule}, {b__Rule}] := 
 Module[{common = Intersection[{a}[[All, 1]], {b}[[All, 1]]]},
  SameQ[common /. {a}, common /. {b}]]

Then 

check[{a -> 3, b -> 1, c -> 4}, {a -> 3, b -> 1, c -> 4}]
check[{a -> 3, b -> 1, c -> 4}, {a -> 3, b -> 2, c -> 4}]
check[{a -> 3, b -> 1, c -> 4}, {a -> 1, b -> 3, c -> 4}]

yields

True
False
False
Heike
  • 24,102
  • 2
  • 31
  • 45
  • +1 That's exactly the approach I came up with (but a half hour after you!). – DavidC Oct 11 '11 at 13:12
  • +1 This solution may be easily generalized for empty sets of rules by replacing `BlankSequence` (`__`) with `BlankNullSequence` (`___`): `check[{a___Rule}, {b___Rule}] := ...`. – Alexey Popkov Oct 11 '11 at 13:23
  • What a difference between `check[{a__Rule}, {b__Rule}] :=` and `check[a, b] :=`? – Nakilon Oct 11 '11 at 13:28
  • 1
    @Nakilon Please read corresponding Documentation pages: "[Making Definitions for Functions](http://reference.wolfram.com/mathematica/tutorial/MakingDefinitionsForFunctions.html)", "[`Blank` (`_`)](http://reference.wolfram.com/mathematica/ref/Blank.html)", "[`BlankSequence` (`__`)](http://reference.wolfram.com/mathematica/ref/BlankSequence.html)". – Alexey Popkov Oct 11 '11 at 13:45
7

Perhaps simpler

check[a : {__Rule}, b : {__Rule}] :=  SameQ @@ Transpose[a /. b /. a /. Rule -> List]

EDIT

Here is an even more esoteric version, which has the advantage of being completely high-level, in the sense that we don't need to know anything about the internal structure of the rules, only how they act:

checkAlt[a : {__Rule}, b : {__Rule}] := # === (# /. #) &[a /. b /. a]

EDIT 2

Well, let me throw in another one, just for fun:

check1[{a__Rule}, {b__Rule}] := SameQ @@ ({a, b} /. {{a, b}, {b, a}})
Leonid Shifrin
  • 22,449
  • 4
  • 68
  • 100
  • +1. Very smart! But this solution will work correctly only of there are no intersections between the *l.h.s.* and *r.h.s.* of both sets of rules. In this sense Heike's solution is straightforward (and much easier for understanding). – Alexey Popkov Oct 11 '11 at 14:00
  • I don't yet understand how, but it works with the same speed and success as Heike's straightforward solution. – Nakilon Oct 11 '11 at 14:02
  • Clever, it took me a moment to figure out what you're doing, and the construct `a /. b /. a /. Rule -> List` was confusing. But, it deals with the case where the lhs of the rules differs between the two lists. – rcollyer Oct 11 '11 at 14:07
  • 1
    @Nakilon The idea is that we act with rules from `b` on l.h.s of `a`. This assumes that no vars are on the r.h.s of `a`. E.g., if `a` is `{c->1,d->2,e->3}`, and `b` is `{c->1,d->3,f->4}`, you get for `a/.b` this: `{1->1,2->3,e->4}`. We act now with `a`, so that those vars not in `b` l.h.s. will be replaced as well. You get then `{1->1,2->3,4->4}`. For rule sets to be the same, the l.h.s. and r.h.s of rules must be the same. This is checked by the rest of the code, where rules are converted to sub-lists first. – Leonid Shifrin Oct 11 '11 at 14:38
  • 1
    @Alexey Indeed, my version is not very general. I was using the OP's spec: rules are restricted to be of the form `var->int`, but it will work also in all cases when there are no variables on the r.h.s. – Leonid Shifrin Oct 11 '11 at 14:57
  • @Leonid Please explain a bit how your "esoteric" solution works (especially why `# === (# /. #) &` should always give the expected result). It is not for simple minds. – Alexey Popkov Oct 11 '11 at 16:35
  • 1
    @Alexey If we get a list of idle rules like `{1->1,2->2}`, then it is unchanged when we act on it with itself. If we have a list where some rules are not idle, like say `{1->1,2->3,3->3}`, then the list will *necessarily* change when we act on it with itself (`#/.#`), which also seems rather easy to see, because those same l.h.sides which are different will be replaced with their r.h. sides, giving a *different* list of rules. – Leonid Shifrin Oct 11 '11 at 16:47
  • @Leonid I caught, thank you. I stumbled over cases like `{1->2,2->1}/.{1->2,2->1}` giving equivalent sets of rules but with different order. – Alexey Popkov Oct 11 '11 at 19:05
  • @Alexey Yes, I thought about this case too, but, as you mentioned, the order is different. – Leonid Shifrin Oct 11 '11 at 19:15
  • @Leonid In really, there was much more important reason for concern: the case `{1->2,2->1,1->2,2->1}/.{1->2,2->1,1->2,2->1}`. This replacement does not give the original expression `{1->2,2->1,1->2,2->1}` (as double replacement does in this case) due to undocumented feature of `ReplaceAll`: it does not look at the parts of the original expression which were already replaced (I used this feature [here](http://stackoverflow.com/questions/6451802/pattern-to-match-only-children-of-certain-elements/6453681#6453681)). So your solution also relies on this undocumented behavior. – Alexey Popkov Oct 11 '11 at 20:00
  • @Alexey Yes, it does, and I also use this feature at times, e.g. here: http://stackoverflow.com/questions/6968806/how-do-i-replace-each-value-in-run-with-the-integer-preceding-the-run/6969008#6969008, and also discussed this behavior here: http://stackoverflow.com/questions/4823838/how-does-mathematica-determine-which-rule-to-use-first-in-substitution/4824119#4824119. I thought that it *is* documented, although have no time right now to look for it in the docs. As to the case at hand, the OP explicitly stated that l.h.s. entries are unique for both sets, so this can not happen here anyway. – Leonid Shifrin Oct 11 '11 at 20:18
  • 1
    @Leonid Oops! This behavior is [documented](http://reference.wolfram.com/mathematica/ref/ReplaceAll.html) in the "More information" field. Sorry for confusion. – Alexey Popkov Oct 11 '11 at 20:18
  • @Leonid Yes, I really like it! But it seems that this behavior of `ReplaceAll` is truly undocumented. I learned this feature originally from [you](http://stackoverflow.com/questions/4998144/reduce-system-of-equations-which-is-under-determined-in-mathematica/4998275#4998275). – Alexey Popkov Oct 11 '11 at 22:29
  • 1
    @Alexey Oh, but it is, although in a tutorial rather than a function page: http://reference.wolfram.com/mathematica/tutorial/ApplyingTransformationRules.html – Leonid Shifrin Oct 11 '11 at 22:32
  • 1
    @Alexey Actually, there is one example of this also on the doc page for `ReplaceAll`, the last of "basic examples", however this form is not stated in the function's syntax. So, it is kind of "semi-documented" :) – Leonid Shifrin Oct 11 '11 at 22:38
  • 1
    @Alexey In fact, this behavior is fully documented for `Replace`, under "More information" section. Since `ReplaceAll` is by far the more often used command, there would be no harm in replicating that info also in the syntax section on the page for `ReplaceAll`. – Leonid Shifrin Oct 11 '11 at 23:18
  • btw, how about `check[a : {__Rule}, b : {__Rule}] := And @@ SameQ @@@ (a /. b /. a)` ? – Mr.Wizard Oct 12 '11 at 08:51
  • @Mr.Wizard Yes, this came to my mind, and also Alexey briefly posted something very similar, but then removed. I did not use this one because, for long lists of rules, it will be slower than `SameQ@@Transpose[...]`, although for longer lists of rules, rule application itself might be a major bottleneck. – Leonid Shifrin Oct 12 '11 at 09:09
  • @Mr.Wizard Thanks. I can say the same about yours. – Leonid Shifrin Oct 12 '11 at 09:43
  • Thanks, Leonid. :-) considering, `SameQ @@ Thread[a /. b /. a, Rule]` appears to be shorter, and a slight bit faster too. Any problems with it? – Mr.Wizard Oct 12 '11 at 09:56
  • @Mr.Wizard It's fine, as an alternative to my first one. It is just that my last 2 solutions were to completely abstract away the internal rule structure, so that it is enough to know that rules replace l.h.s. with r.h.s for *any* expression, *including themselves*, for them to work. This is why I consider them more elegant than the first one - they are more high-level. And this is the main reason I included them - it was interesting to see that there exist such high-level solutions. I actually like my second one the most. – Leonid Shifrin Oct 12 '11 at 10:20
  • Leonid, I was just interested in comparing what I might do with yours. I think that `Thread[#, Rule]` is a little cleaner than `Transpose[# /. List -> Rule]` if it comes without caveat, but I also prefer your second method. – Mr.Wizard Oct 12 '11 at 10:36
  • @Mr.Wizard Yes, I agree, I actually like your version more than my first one. In a sense, `Thread` is acting like generalized `Transpose` here. – Leonid Shifrin Oct 12 '11 at 10:39
7

Here's another solution:

In[12]:= check[a:{__Rule}, b:{__Rule}] := FilterRules[a, b] === FilterRules[b, a]

In[18]:= {{a -> 3, b -> 1, c -> 4}~check ~ {a -> 3, b -> 1, c -> 4} ,
 {a -> 3, b -> 1, c -> 4}~check ~ {a -> 3, b -> 2, c -> 4},
 {a -> 3, b -> 1, c -> 4}~check ~ {a -> 1, b -> 3, c -> 4},
 {a -> 3, b -> 1, c -> 4}~check ~ {c -> 4, d -> 8, e -> 9},
 {a -> 3, b -> 1, c -> 4}~check ~ {d -> 8, e -> 9, f -> 7}}

Out[18]= {True, False, False, True, True}

(This relies on the fact that the lists of options are already sorted.)

Brett Champion
  • 8,497
  • 1
  • 27
  • 44
  • In addition to size, this solution is 3 times faster on my data, than other two. – Nakilon Oct 11 '11 at 14:58
  • @Nakilon If speed is an issue, wrap rules on the r.h.s. of `/.` in `Dispatch` - this should speed the code up, both for my version(s) and @Heike's. – Leonid Shifrin Oct 11 '11 at 15:10
2

Here's a slightly generalized approach:

In[24]:= check[lists__] := 
 And @@ (SameQ @@@ GatherBy[Join[lists], First])

In[25]:= {
  {a -> 3, b -> 1, c -> 4}~check~{a -> 3, b -> 1, c -> 4}, 
  {a -> 3, b -> 1, c -> 4}~check~{a -> 3, b -> 2, c -> 4}, 
  {a -> 3, b -> 1, c -> 4}~check~{a -> 1, b -> 3, c -> 4}, 
  {a -> 3, b -> 1, c -> 4}~check~{c -> 4, d -> 8, e -> 9}, 
  {a -> 3, b -> 1, c -> 4}~check~{d -> 8, e -> 9, f -> 7}
  }

Out[25]= {True, False, False, True, True}

This one doesn't require the elements to be rules, they could be lists, or pretty much any other head. It should also work on any number of inputs.

Brett Champion
  • 8,497
  • 1
  • 27
  • 44