# Select elements of a Matrix that are the same (or have certain relationship) and return their position and the element itself

I have a matrix and I want to pick the elements that are the same and return their positions and their values. It seems easy to me, but all I know is how to pick elements that satisfy certain conditions, but not in relation to other elements.

-

Union @@ list finds all distinct elements in the matrix. Then we pass each element to Position which will tell us where a certain element exists. The result is a new list of this format: {{value, {positions}},...}.

list = RandomInteger[5, {10, 10}];
{#, Position[list, #]} & /@ Union @@ list


(@@ is short for Apply and /@ for Map, do ask if you have questions. Also you say that you are new to Slot, which I use (it's the same as #). {#,func[#]} & is just a function, where the first argument is #. So what func[#] & /@ {1,2,3} amounts to for example is {func[1], func[2], func[3]}.)

-
This solution will need to traverse the complete matrix once for every distinct element, thus it will have worse complexity than pairing up elements with pre-generated positions. This one will run in time proportional to $n\times u$ where $u$ is the number of unique elements and $n$ is the total number of elements. The GatherBy approach will run in $n \log u$ time. – Szabolcs Dec 20 '13 at 20:17
@Szabolcs True, but it's very straightforward. Thanks for the comment though, it's important/useful information. – C. E. Dec 20 '13 at 20:37
@Szabolcs Regarding the statement that any Position-based solution must have poor complexity, I think that if one writes it like this it might have the same complexity, even if it's slower: Position[ReleaseHold@Thread[# - #2 &[Hold[list], Union @@ list]], 0] – C. E. Dec 20 '13 at 20:58
I agree that it's always good to show the most straightforward solution! (+1). The code you show in the comment still has running time proportional to the number of distinct elements ($u$) because it needs to perform an operation for each element of Union@@list. Having twice as many unique elements will make it twice as slow. GatherBy will go through the list of all elements, and for each one it needs to decide whether it has seen it before or not. For this it can use a more efficient method than just looping through all already seen elements (e.g. it could use binary search). – Szabolcs Dec 20 '13 at 21:03
That said, the fastest solution is not always the best solution. I usually start with the simplest code I can come up with and I only bother with performance if needed. I don't like to sacrifice simplicity and readability if I'm not forced to ... – Szabolcs Dec 20 '13 at 21:05

The key function is GatherBy. There are several ways to do it using this function. Here's one:

mat = RandomInteger[10, {5, 5}]

positions = Tuples[Range /@ Dimensions[mat]]

elements = Flatten[mat]

result = GatherBy[Transpose[{elements, positions}], First]


You'll get sublists of items of the form {element, position}. You can use Part and All to extract what you need.

If performance is key, use this variation on the same approach:

elements = Flatten[mat];
positions = Tuples[Range /@ Dimensions[mat]];
positionClasses = GatherBy[positions, elements[[#]] &];


Now the $i^\text{th}$ element of positionClasses will correspond to the $i^\text{th}$ element of DeleteDuplicates@Flatten[mat]. This will be very fast, and possibly the fastest way unless you're willing to write lengthy and complex code.

This approach is limited by GatherBy and will run in time proportional to $n \log u$ where $n$ is the number of total elements in the matrix and $u$ is the number of distinct elements. If you have lots of distinct elements, this will be much faster than any Position-based approach.

-
Thank you all. My matrix is 1594X1594 . @Szabolcs : strangely my mathematica had trouble performing your second solution ( kernel stopped responding for a while ! ) but your first solution was quite fast. On the other hand I would like to this job with a limited accuracy, meaning I need to collect matrix elements that are for example 10^-5 or smaller apart ... your solutions must work if I can apply certain function that represents this criterion but I don't know how ! – Bahman Dec 20 '13 at 20:52
@Bahman If you can only rely on direct comparisons between elements, then neither of our solutions will work. However, if you can come up with a function that can be used to group the elements into equivalence classes, then you can use this approach. For example, you could Round every element to 0.0001 in GatherBy: GatherBy[positions, Round[elements[[#]], 0.0001] &]. This is not the same as grouping together all those that are close! But in certain situations it is a good alternative. – Szabolcs Dec 20 '13 at 20:56
@Bahman If you need to rely on pairwise comparisons, your program will be much slower (but this won't matter if the matrix is not very big). In that case use the second argument of Gather (not GatherBy) to specify the comparison. – Szabolcs Dec 20 '13 at 20:57
Thank you. I think Round works perfectly here for me. – Bahman Dec 20 '13 at 22:06
@Bahman The problem with Round is this: suppose you have a cluster of values that all lie between 1.45 and 1.55. They're close to each other, all within 0.1. If you now round to multiples of 1, you'll get two clusters instead of one: those greater than 1.5 and those smaller than 1.5. This might not be desirable ... – Szabolcs Dec 20 '13 at 23:07