14
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ No, the First /@rules is the same as Range[Length[firstList]]. $\endgroup$ – David Baghdasaryan Jun 8 '17 at 9:48
  • $\begingroup$ Your suggestion is working thanks a lot. But what do you mean by the direct use? $\endgroup$ – David Baghdasaryan Jun 8 '17 at 10:00
20
$\begingroup$

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"}

|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ Beautiful! +1 :-) $\endgroup$ – Mr.Wizard Jun 8 '17 at 11:40
  • $\begingroup$ Darn it! Forgot about the matrix form for Permute. :-( (+1) $\endgroup$ – Edmund Jun 8 '17 at 12:00
14
$\begingroup$

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

Old answer

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.

|improve this answer|||||
$\endgroup$
9
$\begingroup$

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]]]]
|improve this answer|||||
$\endgroup$
7
$\begingroup$

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.

|improve this answer|||||
$\endgroup$
5
$\begingroup$

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"}

|improve this answer|||||
$\endgroup$
  • 2
    $\begingroup$ +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. $\endgroup$ – Mr.Wizard Jun 8 '17 at 12:31
  • $\begingroup$ I should definitely consider using the mapping functionality... $\endgroup$ – Valacar Jun 8 '17 at 16:25
5
$\begingroup$
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}

|improve this answer|||||
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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