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]]]
$\endgroup$
  • $\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 '15 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 '15 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 '15 at 3:57
  • 1
    $\begingroup$ @EricTowers Yes, that's why I said "I have a list of distinct expressions." $\endgroup$ – Szabolcs Sep 25 '15 at 6:25
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.

$\endgroup$
  • 1
    $\begingroup$ The copy[[All, All]] trick is cool! $\endgroup$ – Szabolcs Sep 24 '15 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 '15 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 '15 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 '15 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 '15 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.

$\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.