# “Indexing” a vector

I need to "index" a vector according to the first occurence of its distinct elements.

I have written

index[list_] :=
Module[{x = list, p},
p = Flatten /@ Map[Position[x, #] &, DeleteDuplicates@x];
Table[x[[p[[i]]]] = i, {i, 1, Length@p}];
x]


which gives the expected result:

vec= {1, 4, 4, 8, 7, 7, 4};
index @ vec


{1, 2, 2, 3, 4, 4, 2}

(1) How could a more functional / efficient solution look like?

(2) How could such a solution be extended to work with matrices?

mat = {{1, 4}, {2, 7}, {7, 2}, {9, 4}};


should give

{{1, 2}, {3, 4}, {4, 3}, {5, 2}}

-
+1 for the question – Algohi Aug 18 '14 at 21:18
Thanks for the Accept! You should revisit this in a future release as I expect ArrayComponents will eventually be upgraded to be superior (or at least I hope so). – Mr.Wizard Aug 19 '14 at 17:38

The old-school way to do this:

index[a_] := Module[{i = 1, f}, f[x_] := f[x] = i++; f /@ a]

index @ vec

{1, 2, 2, 3, 4, 4, 2}


A method using Assocation, introduced long after ArrayComponents.

index2[a_List] := AssociationThread[#, Range@Length@#] ~Lookup~ a & @ DeleteDuplicates @ a


Edit #2: extended to matrices using eldo's own method:

index2[m_List?MatrixQ] := Partition[index2 @ Flatten @ m, Last @ Dimensions @ m]


halirutan's unflatten could be used in similar fashion for application to arbitrary nested lists of any structure.

### Benchmarks

Needs["GeneralUtilities"]

BenchmarkPlot[{ArrayComponents, index, index2}, RandomInteger[#, 5 #] &, 2^Range[3, 20],
"IncludeFits" -> True, ImageSize -> 600]


Well then, at least on this first test the older ArrayComponents is several times slower than the newer Assocation and Lookup functionality. Let's try benchmarks with first denser and then sparser duplication:

BenchmarkPlot[{ArrayComponents, index, index2}, RandomInteger[99, 5 #] &, 2^Range[3, 20],
"IncludeFits" -> True, ImageSize -> 600]


With dense duplication index2 still beats ArrayComponents. index2 is about six times faster than ArrayCompoents here.

BenchmarkPlot[{ArrayComponents, index, index2}, RandomInteger[15 #, 5 #] &,
2^Range[3, 20], "IncludeFits" -> True, ImageSize -> 600]


With sparse duplication index2 is still the winner, but there is indication that it has higher complexity. Let's try single point test with a larger set. (Each in a fresh kernel.)

SeedRandom[0]
big = RandomInteger[3*^7, 1*^7];
ArrayComponents[big] // Timing // First
MaxMemoryUsed[]

23.758952

2092193592

SeedRandom[0]
big = RandomInteger[3*^7, 1*^7];
index2[a_] := AssociationThread[#, Range@Length@#] ~Lookup~ a & @ DeleteDuplicates @ a
index2[big] // Timing // First
MaxMemoryUsed[]

13.400486

1199556824


Not only does index2 remain faster than ArrayComponents it uses only a bit more than half as much memory.

Alright, a final test: perhaps unpacked data is the Achilles heel of index2:

(* don't forget to reload definitions needed for this plot *)

BenchmarkPlot[{ArrayComponents, index, index2}, "foo" /@ RandomInteger[#, #] &,
2^Range[3, 20], "IncludeFits" -> True, ImageSize -> 600]


Nope! :-) It appears that index2 is superior across the board.

-
I had to take apart index2 to see how it worked. A nice touch. +1 – rcollyer Aug 18 '14 at 17:55
@rcollyer Thanks! :-) – Mr.Wizard Aug 18 '14 at 17:56

I think the built-in function ArrayComponents is what you need:

vec = {1, 4, 4, 8, 7, 7, 4};
ArrayComponents[vec]
(* {1,2,2,3,4,4,2} *)

mat = {{1, 4}, {2, 7}, {7, 2}, {9, 4}};
ArrayComponents[mat]
(* {{1,2},{3,4},{4,3},{5,2}} *)

raggedarray = RandomSample /@ (CharacterRange["a", "z"][[#]] & /@
Range[RandomSample[Range[5]]])
(* {{"a","b"},{"a"},{"c","b","a"},{"d","c","b","a"},{"e","b","c","d","a"}} *)
ArrayComponents[raggedarray]
(* {{1,2},{1},{3,2,1},{4,3,2,1},{5,2,3,4,1}} *)

genericinput = {{"a", "b"}, 1, 2, {3, 4}, {"a"}, "c", "b", "a", {"d", "c", "d"}, {2, 3}} ;
ArrayComponents[genericinput]
(* {{1,2},3,4,{5,6},{1},7,2,1,{8,7,8},{4,5}} *)

-
Should I delete the question? I wouldn't have assumed that there is such an "easy" solution. On the other hand, who knows all of the inbuilt functions? – eldo Aug 18 '14 at 14:14
@eldo, I think you should keep the question unless a duplicate shows up on this site. – kglr Aug 18 '14 at 14:19
@kguler thanks...always learning something new, so agree keep if not duplicate – ubpdqn Aug 18 '14 at 16:39
@eldo The answer is simple but IMO ArrayComponents is not easy to find in the documentation. This should remain open. – Mr.Wizard Aug 18 '14 at 16:42
@Mr.Wizard Your index3 delivers wrong results. I would prefer a dual definition: index[m_?VectorQ] := AssociationThread[#, Range@Length@#]~Lookup~m &@DeleteDuplicates@m and then index[m_?MatrixQ] := Partition[index@Flatten@m, Last@Dimensions@m] – eldo Aug 19 '14 at 15:14

you can also use ClusteringComponents function

inex[m_] := ClusteringComponents[m, Length@m + 1];

vec = {1, 4, 4, 8, 7, 7, 4};
inex[vec]
(*{1, 2, 2, 3, 4, 4, 2}*)

mat = {{1, 4}, {2, 7}, {7, 2}, {9, 4}};

inex[mat]
(*{{1, 2}, {3, 4}, {4, 3}, {5, 2}}*)

-
Unfortunately this scales very poorly due to the clustering overhead: BenchmarkPlot[{ArrayComponents, ClusteringComponents[#, Length@# + 1] &}, RandomInteger[#, 5 #] &, 2^Range[3, 20], "IncludeFits" -> True, ImageSize -> 600] yields i.stack.imgur.com/u5SOg.png – Mr.Wizard Aug 19 '14 at 17:36

Just for fun, here's a way to do it without using the built-in function:

Clear[firstP]
firstP[l_List] := l /. MapIndexed[#1 -> First@#2 &, DeleteDuplicates[Flatten@l]]

firstP /@ {vec, mat}
(* {{1, 2, 2, 3, 4, 4, 2}, {{1, 2}, {3, 4}, {4, 3}, {5, 2}}} *)

-
Interesting, but your results don't agree with kguler's (and the examples in my question) – eldo Aug 18 '14 at 16:42
Sorry I mistakenly thought you wanted something different. It also becomes easier to solve. – seismatica Aug 18 '14 at 16:48
If you add Dispatch` around the list of rules this is pretty competitive in Mr.Wizards benchmark. Graph. +1 – C. E. Aug 18 '14 at 20:16