# Efficient conversion between two partition representations

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]]]
• @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. Sep 24, 2015 at 21:35
• @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. Sep 24, 2015 at 21:55
• Do you guarantee that list contains no duplicates? Do you guarantee that every element of list appears exactly once in partitions? Sep 25, 2015 at 3:57
• @EricTowers Yes, that's why I said "I have a list of distinct expressions." Sep 25, 2015 at 6:25

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]];