# Confused behavior using Dispatch to sort one list relative to another

I have a need to sort the entries of one list into the same sequence as the entries in a reference list. Because I have rather large lists involving strings, I'm trying to use Dispatch to accomplish this quickly.

Here is code that works correctly to provide an example of what I am doing:

list1={"q", "r", "p"}; (*reference list*)
list2={"r", "q", "p"}; (* needs sorted into same order as list1*)

listdispatch=Dispatch[list1rules]

updatedpositions=list2 /. listdispatch
list2[[updatedpositions]]

Out[2]= {"q" -> 1, "r" -> 2, "p" -> 3}

Out[3]= {"q" -> 1, "r" -> 2, "p" -> 3}

Out[4]= {2, 1, 3}

Out[5]= {"q", "r", "p"}


This code works as expected and allows me to extract the elements of list2 in the same order as list 1.

My problem comes in when the strings are more complicated ... the behavior of the above seems to change.

Here is an example of toy code that does not work as expected.

reflist={"AFFX-BioB-5_at", "AFFX-BioB-M_at",
"AFFX-BioB-3_at", "AFFX-BioC-5_at", "AFFX-BioC-3_at",
"AFFX-BioDn-5_at", "AFFX-BioDn-3_at", "AFFX-CreX-5_at",
"AFFX-CreX-3_at", "AFFX-DapX-5_at", "AFFX-DapX-M_at",
"AFFX-DapX-3_at", "AFFX-LysX-5_at", "AFFX-LysX-M_at",
"AFFX-LysX-3_at", "AFFX-PheX-5_at", "AFFX-PheX-M_at",
"AFFX-PheX-3_at", "AFFX-ThrX-5_at",
"AFFX-ThrX-M_at"}; (* reference list to be sorted against *)

seclist=RotateLeft[reflist, 4] (* list that should be sorted according to reflist *)

dispatchthis=Dispatch[rules];
newpositions=seclist /. dispatchthis

seclist[[newpositions]]

Out[7]= {"AFFX-BioC-3_at", "AFFX-BioDn-5_at", "AFFX-BioDn-3_at", \
"AFFX-CreX-5_at", "AFFX-CreX-3_at", "AFFX-DapX-5_at", \
"AFFX-DapX-M_at", "AFFX-DapX-3_at", "AFFX-LysX-5_at", \
"AFFX-LysX-M_at", "AFFX-LysX-3_at", "AFFX-PheX-5_at", \
"AFFX-PheX-M_at", "AFFX-PheX-3_at", "AFFX-ThrX-5_at", \
"AFFX-ThrX-M_at", "AFFX-BioB-5_at", "AFFX-BioB-M_at", \
"AFFX-BioB-3_at", "AFFX-BioC-5_at"}

Out[8]= {"AFFX-BioB-5_at" -> 1, "AFFX-BioB-M_at" -> 2,
"AFFX-BioB-3_at" -> 3, "AFFX-BioC-5_at" -> 4, "AFFX-BioC-3_at" -> 5,
"AFFX-BioDn-5_at" -> 6, "AFFX-BioDn-3_at" -> 7,
"AFFX-CreX-5_at" -> 8, "AFFX-CreX-3_at" -> 9, "AFFX-DapX-5_at" -> 10,
"AFFX-DapX-M_at" -> 11, "AFFX-DapX-3_at" -> 12,
"AFFX-LysX-5_at" -> 13, "AFFX-LysX-M_at" -> 14,
"AFFX-LysX-3_at" -> 15, "AFFX-PheX-5_at" -> 16,
"AFFX-PheX-M_at" -> 17, "AFFX-PheX-3_at" -> 18,
"AFFX-ThrX-5_at" -> 19, "AFFX-ThrX-M_at" -> 20}

Out[10]= {5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, \
1, 2, 3, 4}

Out[11]= {"AFFX-CreX-3_at", "AFFX-DapX-5_at", "AFFX-DapX-M_at", \
"AFFX-DapX-3_at", "AFFX-LysX-5_at", "AFFX-LysX-M_at", \
"AFFX-LysX-3_at", "AFFX-PheX-5_at", "AFFX-PheX-M_at", \
"AFFX-PheX-3_at", "AFFX-ThrX-5_at", "AFFX-ThrX-M_at", \
"AFFX-BioB-5_at", "AFFX-BioB-M_at", "AFFX-BioB-3_at", \
"AFFX-BioC-5_at", "AFFX-BioC-3_at", "AFFX-BioDn-5_at", \
"AFFX-BioDn-3_at", "AFFX-CreX-5_at"}


You'll notice that the newpositions list does not contain the proper coordinates to rearrange seclist into the same sequence as the first.

I am at a loss to understand this behavior, when the first code example works. Any thoughts? Thank you.

• Todd is your seclist always identical in content to reflist, i.e. differing only in its sorting? – Mike Honeychurch Jan 12 '13 at 22:09
• @MikeHoneychurch: yes, reflist and seclist have identical elements, just in different order. – Todd Allen Jan 12 '13 at 22:13

The problem is not in the second example, but in the first, and in the algorithm not being right. You fell victim to the simplicity of your test example, since 3 elements is not enough for testing permutations. Here is a more representative example:

list1 = DeleteDuplicates@RandomInteger[15, 10]

(*  {1, 3, 8, 7, 14, 11, 13} *)

list2 = RandomSample[list1]

{8, 3, 11, 13, 1, 14, 7}


Creating the rules:

list1rules = Thread[list1 -> Range[Length[list1]]]
listdispatch = Dispatch[list1rules]


Now the key point: you need not just to apply the rules, which simply give you the positions of elements of list2 in list1, but you need the Ordering of those positions:

list2[[Ordering[list2 /. listdispatch]]]

(*  {1, 3, 8, 7, 14, 11, 13} *)


since at some point, some real sorting should take place. Have a look also here and here, where I gave detailed discussions of very similar ideas. I also once wrote a package called UnsortedOperations, which has a collection of functions for doing similar kind of manipulations. The package lives here, and comes with a notebook containing examples of use for all functions in it.

• Thank you! Ironically I am at page 130 of your text and hadn't gotten to your reference points yet. You are an excellent teacher, Leonid. I hope one day you will be motivated to write a second, advanced tutorial to your current offering. I would definitely pay good money for that. Kind regards. – Todd Allen Jan 12 '13 at 23:11
• Thanks, @Todd. I have had these plans for the second book exactly along the lines you described, for quite a while. Alas, don't have enough time to move this project along with the speed it deserves. – Leonid Shifrin Jan 12 '13 at 23:19