13
$\begingroup$

I have a list of distinct expressions. We can represent a partitioning of list in two ways:

  1. As a list of sublists partitions = {{a, b, ...}, {x, y, ...}, ...}.

  2. As a vector of integer partition indices, corresponding to each element of list.

Example:

list = {a, b, c, d, e}
partitions = {{a,e}, {}, {c,d,b}}
vector = {1, 3, 3, 3, 1}

Here {a,e} has index 1, {} has index 2 and {c,d,b} has index 3.

What is the fastest way to convert from the partitions representation to the vector representation?

list may contain any expression, including lists. The conversion must be as fast as possible, with special attention given to the situation where list contains only integers.

A possible implementation is

partitionToVector[list_, partitions_] := 
    list /. Dispatch[Join @@ Thread /@ Thread[partitions -> Range@Length[partitions]]]
Improve this question
$\endgroup$
4
  • $\begingroup$ @SjoerdC.deVries Take the partitions in consecutive order and number them starting with 1. Thus {a,e} receives the index 1. Then both a and e will be replaced with 1 in list. Another way to put it: There's a direct correspondence between elements of list and vector (that are in the same position). The number in vector indicates which partition the corresponding element of list belongs to. $\endgroup$
    – Szabolcs
    Sep 24, 2015 at 21:35
  • $\begingroup$ @Sjoerd I mean that list is given. Then vector and partitions are two different but equivalent representations for a partitioning of list. I want to state the problem better, but I don't really understand why you find it misleading. BTW this is for use with community detection algorithms and igraph. igraph likes the vector representation and Mathematica likes the partitions representation. $\endgroup$
    – Szabolcs
    Sep 24, 2015 at 21:55
  • $\begingroup$ Do you guarantee that list contains no duplicates? Do you guarantee that every element of list appears exactly once in partitions? $\endgroup$
    – Eric Towers
    Sep 25, 2015 at 3:57
  • 1
    $\begingroup$ @EricTowers Yes, that's why I said "I have a list of distinct expressions." $\endgroup$
    – Szabolcs
    Sep 25, 2015 at 6:25

2 Answers 2

Reset to default
13
$\begingroup$

This seems to be about twice faster on large generic lists, and I made it somewhat faster still on integer lists (about 4-5x faster, per my tests):

ClearAll[partitionToVectorLS];
partitionToVectorLS[list : {__Integer}, partitions_, sparsenessThreshold_: 10] :=
  Module[{max = Max[list], min = Min[list], copy = partitions, 
      sparseness, inds, nonsparseQ, dim
    },
    dim = max - min + 1;
    sparseness = dim/Length[list];
    nonsparseQ = sparseness < sparsenessThreshold;
    inds = If[TrueQ @ nonsparseQ, Range[dim], SparseArray[{}, dim]];
    copy[[All, All]] = Range[Length[partitions]];
    inds[[Join @@ partitions - min + 1]] = Join @@ copy;
    If[nonsparseQ, Identity, Normal]@inds[[list - min + 1]]
  ];


partitionToVectorLS[list_, partitions_] :=
  Module[{copy = partitions},
    copy[[All, All]] = Range[Length[partitions]];
    Lookup[AssociationThread[Flatten[partitions,1], Flatten[copy,1]], list]
  ]

Note that the specialized definition for integers avoids unpacking of inner lists in partitions. I have also introduced a sparseness threshold, above which using inds list as a faster hash-table with integer keys becomes too memory-consuming, and then we switch to using SparseArray.

Improve this answer
$\endgroup$
11
  • 1
    $\begingroup$ The copy[[All, All]] trick is cool! $\endgroup$
    – Szabolcs
    Sep 24, 2015 at 21:57
  • 1
    $\begingroup$ It's totally confusing how that works: copy[[All, All]] == copy evaluates to True, and obviously, copy = Range[Length[partitions]] sets copy to {1, 2, 3}. So why does it work? $\endgroup$
    – march
    Sep 24, 2015 at 22:10
  • 2
    $\begingroup$ @march Well, if I have a 2-level list, and make an assignment lst[[All,1]] = 1, say, then all first elements of sublists will be set to 1. The construct I used generalizes that to the case when we set different sublists to different elements. $\endgroup$
    – Leonid Shifrin
    Sep 24, 2015 at 22:13
  • 2
    $\begingroup$ @march Yes. You kind of interate over left-most All, while the right-most All works to say that all elements of a given sub-list should be given one and the same value. $\endgroup$
    – Leonid Shifrin
    Sep 24, 2015 at 22:24
  • 5
    $\begingroup$ @ciao Well, quite frankly, from what I've seen from your posts, you are one of the finest experts on performance-tuning we have on this site, and there is quite a bit for me to learn from you answers on this topic. $\endgroup$
    – Leonid Shifrin
    Sep 24, 2015 at 22:43
2
$\begingroup$ 
fun[lst_, part_] := 
 Flatten[Last@Reap[MapIndexed[Sow[#2[[1]], #1] &, part], lst, #2 &]]

I make no comment re: efficiency and have upvoted Leonid Shifrin and am happy to delete if assessed as non-contributory.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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