Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Recently I had to solve a problem similar to this:

Let's say I have a list of list of rules

Clear[a, b, c, d]
l = {{a -> 2, b -> 1, c -> 3, d -> 2}, {d -> 2, b -> 1, a -> 1, c -> 2}, 
     {c -> 3, a -> 1, b -> 2}};

What is the best way to sort the values of {a, b, c} in each sublist without touching the rest of the sublist. So the first sublist should be:

{a -> 1, b -> 2, c -> 3, d -> 2}

and the whole result should be

{{a -> 1, b -> 2, c -> 3, d -> 2}, {d -> 2, b -> 1, a -> 1, c -> 2}, 
 {c -> 3, a -> 1, b -> 2}}

There are no duplicates in the subsists (so a -> _ appears only once). The order of rules in the sublist does not matter.

In an effort to expand my pattern matching skills I would like to know: What's the best way to achieve this? Here "best" means elegant code, but still efficient enough to work ~10^5 subsists.

testdata = 
  Table[MapThread[
    Rule, {RandomSample[{a, b, c, d, e, f, g, h, i, j, k}, 10], 
     RandomReal[{-1, 1}, 10]}], {ii, 10^5}];

I'm posting my answer below, so that I won't get accused of not showing any effort:)

share|improve this question

4 Answers 4

up vote 4 down vote accepted

I cannot think of a better approach than your own method therefore I shall recast it in a generalized fashion.

With[{T = Thread},
 normRls[l_, pat_] := l /. T[T[pat -> _] -> T[pat -> Sort[pat /. l]]]
]

normRls[#, {a, b, c}] & /@ testdata // Timing // First
1.31

This is however a bit slower than your hard-coded method:

normalize /@ testdata // Timing // First
1.045

Okay, let's try a little meta-programming:

genRule[x_, {y_}] := (x -> _) :> (x -> Slot[y])

genNorm[pat_List] :=
  With[{body = MapIndexed[genRule, pat]},
    # /. (body &) @@ Sort[pat /. #] &
  ]

genNorm[{a, b, c}] /@ testdata // Timing // First
0.889

Ah, that's more like it!


Explanation

A request for explanation of the code was made. The first method is fairly straightforward after understanding the behavior of Thread:

Thread[{a, b, c} -> {1, 2, 3}]
{a -> 1, b -> 2, c -> 3}
Thread[{a, b, c} -> nonlist]
{a -> nonlist, b -> nonlist, c -> nonlist}

This is used three separate times, to generate e.g.: {a -> _, b -> _, c -> _}
then {a -> 1, b -> 2, c -> 3}, and then to combine them into:
{(a -> _) -> a -> 1, (b -> _) -> b -> 2, (c -> _) -> c -> 3}.

The "meta-programming" method is a bit more involved.

First let's look at the result, then how we get there:

genNorm[{q, r, s}]
#1 /. ({(q -> _) :> q -> #1,
        (r -> _) :> r -> #2,
        (s -> _) :> s -> #3} &) @@ Sort[{q, r, s} /. #1] &

We see that the output is a Function (&). This function takes a single argument, the (sub)list of rules to be modified. Upon it a replacement will eventually be done (#1 /. ...). The rules for that replacement are constructed by an internal Function:

({(q -> _) :> q -> #1,
  (r -> _) :> r -> #2,
  (s -> _) :> s -> #3} &)

the parameters (#1, #2, #3) of which are filled by applying (@@) to Sort[{q, r, s} /. #1] wherein #1 is the original (sub)list of rules. Sort[{q, r, s} /. #1] itself is hopefully self-explanatory. This internal function pulls the needed parts from the sorted list. For example, with the input:

{q -> 21, r -> 11, s -> 31, t -> 21}

The output is:

{(q -> _) :> q -> 11,
 (r -> _) :> r -> 21,
 (s -> _) :> s -> 31}

Which when applied yields:

{q -> 11, r -> 21, s -> 31, t -> 21}

Okay, so how is that function constructed?

The auxiliary function genRule is MapIndexed over the pattern list:

MapIndexed[genRule, {a, b, c}]
{(a -> _) :> a -> #1,
 (b -> _) :> b -> #2,
 (c -> _) :> c -> #3}

This expression is then named body (using With) and injected into: # /. (body &) @ Sort[pat /. #] & which you should recognize as the (nested) function detailed above.

share|improve this answer
    
Thank you for the answer (+1). Some wonderful ideas. But, I think this answer would be much better if you could ad a line or two explaining what the code does (for those who don't have MMA at hand or are not so proficient -- actually I'm still deciphering the meta-programming trick:). –  Ajasja Feb 14 '13 at 21:43
    
@Ajasja Done. Please tell me if my explanation is satisfactory. I never know what to include and what to leave out I'm afraid. –  Mr.Wizard Feb 14 '13 at 22:07
    
Thanks, that was very extensive! –  Ajasja Feb 15 '13 at 9:41
    
@Ajasja I realize that this can be made faster by using genNorm[pat_List] := With[{body = MapIndexed[genRule, pat]}, Replace[#, body & @@ Sort[pat /. #], {1}] &] -- that is replace at level one. –  Mr.Wizard Feb 20 '13 at 21:12

Here is an alternative:

Clear@sortKeys
sortKeys[list_, keys_] := Module[{keysInList, values, rules},
    {keysInList, values} = (rules = FilterRules[#, keys]) /. Rule -> List // Transpose;       
    # /. MapThread[RuleDelayed, {Sort@rules, Thread[Sort@keysInList -> Sort@values]}]
] & /@ list

This first filters the rules in a sublist corresponding to the input keys ({a, b, c}) we wish to sort by and then keeps a separate list of keys that actually appear in the sublist (keysInList) and their values (this is to handle missing keys). Then it sorts the values and replaces a -> original value with a -> sorted value (the MapThread is used to construct a rule list).

Usage:

sortKeys[l, {a, b, c}]
(* {{a -> 1, b -> 2, c -> 3, d -> 2}, {d -> 2, b -> 1, a -> 1, c -> 2}, 
    {c -> 3, a -> 1, b -> 2}} *)

This can be simplified if it can be guaranteed that all the sublists will have all the keys.

share|improve this answer
    
Thanks for the answer. I think a short sentence explaining what the code does would make this a much better answer. –  Ajasja Feb 14 '13 at 10:19
    
@Ajasja Explanation added :) –  rm -rf Feb 14 '13 at 14:54
    
Thanks +1. Why is RuleDelayed needed? (Instead of a normal Rule) –  Ajasja Feb 14 '13 at 15:06
1  
Probably not needed in this case, but I do it out of habit, when the RHS is a named pattern (or more generally, when it's not something of the form HeadA -> HeadB or SymbolA -> SymbolB) –  rm -rf Feb 14 '13 at 16:11

edit: this is actually not doing what you want, i sorted the order of the rules without changing the rules.

rulelist = {a -> 1, b -> 2, cc -> 4, c -> -1};
sortpos = Position[ rulelist ,  r_Rule /; MemberQ[{a, b, c}, r[[1]]]];
sorted = Sort[ 
   Take[rulelist, #][[1]] & /@ (sortpos) , #1[[2]] < #2[[2]] &];
(rulelist[[sortpos[[#]]]] = sorted[[#]]) & /@ Range[Length[sortpos]];
rulelist

{c -> -1, a -> 1, cc -> 4, b -> 2}

Take 2, I think this is what you want, changine the rules so that a-> min value, etc and reordering the rules.. I think it does basically what you did, except I didnt "hard code" the a,b,c into the algotithm. If performace suffers a tad that might be a fair trade.

rulelist = {a -> 1, b -> 2, cc -> 4, c -> -1};
desiredorder = {a, b, c};
values = Sort[ desiredorder /. rulelist];
rulelist = rulelist /. (x_ -> y_) /; 
     MemberQ[desiredorder, x] :> (x ->values[[First[Position[desiredorder, x]][[1]]]]);
sortpos = 
  Position[ rulelist ,  r_Rule /; MemberQ[desiredorder, r[[1]]]];
(rulelist[[sortpos[[#]]]] = desiredorder[[#]] -> values[[#]]) & /@ 
      Range[Length[desiredorder]];


rulelist -> {a -> -1, b -> 1, cc -> 4, c -> 2}

(If you dont care about the order of the rules, drop the last two lines)

share|improve this answer
    
Thanks for the answer. I think a short sentence explaining what the code does would make this a much better answer. –  Ajasja Feb 14 '13 at 10:20

Here is my solution: I first retrieve the values, sort them and then use rule replacement to apply the changes.

Clear@normalize
normalize[l_] := Block[{av, bv, cv},
  (*Get sorted values*)
  {av, bv, cv} = Sort[{a, b, c} /. l];
  (*Modify the original lis*)
  l /. {Rule[a, _] -> Rule[a, av],
    Rule[b, _] -> Rule[b, bv],
    Rule[c, _] -> Rule[c, cv]}
  ]

normalize /@ l
(* out =>
{{a -> 1, b -> 2, c -> 3, d -> 2}, {d -> 2, b -> 1, a -> 1, 
  c -> 2}, {c -> 3, a -> 1, b -> 2}}
*)

This takes about 2 seconds on my computer

AbsoluteTiming[result = normalize /@ testdata;]
(*=> {2.319133, Null}*)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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