Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?

ad (2)

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

should give

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

share|improve this question
    
+1 for the question –  Algohi Aug 18 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 at 17:38

4 Answers 4

up vote 11 down vote accepted

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]

enter image description here

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]

enter image description here

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]

enter image description here

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] 

enter image description here

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

share|improve this answer
    
I had to take apart index2 to see how it worked. A nice touch. +1 –  rcollyer Aug 18 at 17:55
    
@rcollyer Thanks! :-) –  Mr.Wizard Aug 18 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}} *)
share|improve this answer
    
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 at 14:14
3  
@eldo, I think you should keep the question unless a duplicate shows up on this site. –  kguler Aug 18 at 14:19
    
@kguler thanks...always learning something new, so agree keep if not duplicate –  ubpdqn Aug 18 at 16:39
2  
@eldo The answer is simple but IMO ArrayComponents is not easy to find in the documentation. This should remain open. –  Mr.Wizard Aug 18 at 16:42
1  
@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 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}}*)
share|improve this answer
    
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 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}}} *)
share|improve this answer
    
Interesting, but your results don't agree with kguler's (and the examples in my question) –  eldo Aug 18 at 16:42
    
Sorry I mistakenly thought you wanted something different. It also becomes easier to solve. –  seismatica Aug 18 at 16:48
2  
If you add Dispatch around the list of rules this is pretty competitive in Mr.Wizards benchmark. Graph. +1 –  Pickett Aug 18 at 20:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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