# Rearrange the list in a specific way

Suppose I have a list like {"e", "c", "a", "d", "b"} and list of rules {1 -> 5, 2 -> 3, 3 -> 1, 4 -> 4, 5 -> 2}. The second list says that for example element on position 1 shoud be on position 5 and so on. So the desired result is {"a", "b", "c", "d", "e"}. How it can be done in the fastest and elegant way?

• No, the First /@rules is the same as Range[Length[firstList]]. Commented Jun 8, 2017 at 9:48
• Your suggestion is working thanks a lot. But what do you mean by the direct use? Commented Jun 8, 2017 at 10:00

A bit simpler:

Permute[lst, SparseArray[order]]


Example:

lst = {"e", "c", "a", "d", "b"};
order = {1 -> 5, 2 -> 3, 3 -> 1, 4 -> 4, 5 -> 2};
Permute[lst, SparseArray[order]]


{"a", "b", "c", "d", "e"}

• Beautiful! +1 :-) Commented Jun 8, 2017 at 11:40
• Darn it! Forgot about the matrix form for Permute. :-( (+1) Commented Jun 8, 2017 at 12:00

By using assignment to parts. Update: now cleaner.

fn[list_, r_] :=
Module[{n = list},
n[[Values @ r]] = n[[Keys @ r]];
n
]


Test:

x = {"e", "c", "a", "d", "b"} ;
r = {1 -> 5, 2 -> 3, 3 -> 1, 4 -> 4, 5 -> 2};

fn[x, r]

{"a", "b", "c", "d", "e"}


## Performance

This outperforms even Shadowray's elegant code:

x = RandomReal[1, 50000];
r = #2[Thread[# -> #2[#]]] &[Range@50000, RandomSample];

a = Permute[x, SparseArray[r]];   // RepeatedTiming
b = fn[x, r];                     // RepeatedTiming

a === b

{0.016, Null}

{0.0048, Null}

True


### Optimization for a specific format

If all positions are specified and in order as in the example, we can simplify:

f2[list_, r_] := Module[{n = list}, n[[Values @ r]] = n; n]


This can be very fast:

r = Sort[r];

c = f2[x, r]; // RepeatedTiming

a === c

{0.0010, Null}

True


If the position of every element is specified, as in the example, we can use:

x = {"e", "c", "a", "d", "b"} ;
r = {1 -> 5, 2 -> 3, 3 -> 1, 4 -> 4, 5 -> 2};

x[[ Ordering @ Values @ Sort @ r ]]

{"a", "b", "c", "d", "e"}


Sort is redundant if the rules are already sorted but I included it for robustness.

Assuming:

lst = {"e", "c", "a", "d", "b"};
order = {1 -> 5, 2 -> 3, 3 -> 1, 4 -> 4, 5 -> 2};

1. lst[[#]] & /@ First /@ SortBy[order, Last]
2. lst[[#]] & /@ Keys[SortBy[order, Last]]
3. lst[[Keys[SortBy[order, Last]]]]

You may use Permute and FindCycles.

With

vals = {"e", "c", "a", "d", "b"};
pos = {1 -> 5, 2 -> 3, 3 -> 1, 4 -> 4, 5 -> 2};


Then

Permute[vals, Cycles@Map[Last, FindCycle[pos, {1, ∞}, All], {2}]]

{"a", "b", "c", "d", "e"}


FindCycle will find more than one cycle if they exists in the rules of pos and Permute will apply all of them.

Hope this helps.

Also vals[[Ordering[Values@r]]] but I need to think if this will work with multiple cycles but have to go right now.

Thread[SparseArray[rules] -> lst] // SparseArray // Normal


or:

rules // SparseArray // Normal // SparseArray[# -> lst] & // Normal


Previous versions:

SparseArray[Thread[ rules[[;; , 2]] -> lst[[rules[[;; , 1]]]]]] // Normal

{lst, rules} // Apply[Thread[Values[#2] -> #[[Keys@#2]]] &] //SparseArray // Normal


{a, b, c, d, e}

A bit less elegant:

values = {"e", "c", "a", "d", "b"};
pos = {1 -> 5, 2 -> 3, 3 -> 1, 4 -> 4, 5 -> 2};
list = Table[{}, {i, 1, Length[values]}];
Table[list[[pos[[i, 2]]]] = values[[pos[[i, 1]]]], {i,1,Length[values]}];

list


gives {"a", "b", "c", "d", "e"}

• +1 because after a half hour of independent development I realize that ended up with a cleaner version of your assignment. You might take a look at my answer to see how this might be done in a more concise and efficient way. Commented Jun 8, 2017 at 12:31
• I should definitely consider using the mapping functionality... Commented Jun 8, 2017 at 16:25
list = {"e", "c", "a", "d", "b"};

p = {1 -> 5, 2 -> 3, 3 -> 1, 4 -> 4, 5 -> 2};


Using Query

Query[Keys @ SortBy[p, Last]] @ list


{"a", "b", "c", "d", "e"}