Tjyylli

Suppose I have the following matrix:

M = 

 {{0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 

  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, 

  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, 

  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, 

  {0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0}, 

  {0, 0, 0, 0,1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0}, 

  {0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0}, 

  {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}; 



TableForm[M, TableHeadings -> {{S1, S2, S3, S4, S5, S6, S7, S8}}]

In this case, it turns out that rows (S1, S8), (S2, S3, S4), (S5, S6, S7) have equal element values in identical column positions. I have a 1000 x 1000 matrix to examine and would appreciate any assistance in coding this problem.

idx = DeleteDuplicates[Sort /@ Nearest[M -> Automatic, M, {∞, 0}]]

{{1, 8}, {2, 3, 4}, {5, 6, 7}}

In order to obtain the labels of the rows, you may use the following:

labels = {S1, S2, S3, S4, S5, S6, S7, S8};

Map[labels[[#]] &, idx, {2}]

{{S1, S8}, {S2, S3, S4}, {S5, S6, S7}}

The function positionDuplicates [] from How to efficiently find positions of duplicates? does the job, faster than Nearest.

(* Henrik's method *)

posDupes[M_] := DeleteDuplicates[Sort /@ Nearest[M -> Automatic, M, {∞, 0}]]



SeedRandom[0];  (* to make a reproducible 1000 x 1000 matrix *)

foo = Nest[RandomInteger[1, {1000, 1000}] # &, 1, 9];



d1 = Cases[positionDuplicates[foo], dupe_ /; Length[dupe] > 1]; // RepeatedTiming

(*  {0.017, Null}  *)



d2 = Cases[posDupes[foo], dupe_ /; Length[dupe] > 1]; // RepeatedTiming

(*  {0.060, Null}  *)



d1 == d2

(*  True  *)



d1

(*

  {{25, 75, 291, 355, 356, 425, 475, 518, 547, 668, 670, 750, 777},

   {173, 516}, {544, 816}, {610, 720}}

*)

The following shows an order of magnitude difference between the most efficient ordering solution and the least efficient gatherBy solution for a 1000 x 1000 matrix as required by the OP.

ordering[M_] := Sort@SplitBy[Ordering@M, M[[#]] &];

sort[M_] := 

  Sort[#[[All, 2]] & /@ 

    SplitBy[SortBy[Thread[{M, Range@Length@M}], First], First]];

gatherBy[M_] := GatherBy[Range@Length@M, M[[#]] &];

nearest[M_] := 

  DeleteDuplicates[

   Sort /@ Nearest[M -> Automatic, M, {[Infinity], 0}]];

positionIndex[M_] := Values@PositionIndex@M;



SetAttributes[speedTest, HoldAll];



speedTest[functions_, opts : OptionsPattern[]] := 

 Function[inp, speedTest[functions, inp, opts], HoldAll]



speedTest[functions_, inp_, OptionsPattern[]] := Module[{

    tm = Function[fn, 

      Function[x, <|ToString[fn] -> RepeatedTiming@fn@x|>]],

    timesOutputs, times, sameQ},

   timesOutputs = Through[(tm /@ functions)@inp];

   times = 

    SortBy[Query[All, All, First]@timesOutputs, Last] // Dataset;

   sameQ = SameQ @@ (Query[All, Last, 2]@timesOutputs);

   If[OptionValue@"CheckOutputs", 

    Labeled[times, 

     Row[{ToString@Unevaluated@inp, Spacer@80, 

       If[sameQ, Style["[Checkmark]", Green, 20], 

        Style["x", Red, 20]]}], Top], times]

   ];



Options[speedTest] = {"CheckOutputs" -> True};



M1000 = RandomInteger[{0, 1}, {1000, 1000}];



speedTest[{gatherBy, positionIndex, nearest, ordering, sort}]@M1000

Note the green tick indicates the same outputs. The same order and magnitude difference is evident for a 10 0000 x 10 000 matrix with the ordering solution still the fastest but with the sort solution now becoming second fastest.

M10000 = RandomInteger[{0, 1}, {10000, 10000}];

speedTest[{gatherBy, positionIndex, nearest, ordering, sort}]@M10000

I'd use GroupBy.

First the names of the rows: can be anything you like, for example

rownames = Array[ToExpression["S" <> ToString[#]] &, Length[M]]

{S1, S2, S3, S4, S5, S6, S7, S8}

Next the grouping:

groups = GroupBy[Thread[rownames -> M], Last -> First]

<|{0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0} -> {S1, S8},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0} -> {S2, S3, S4},
{0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0} -> {S5, S6, S7}|>

If all you need are the names:

Values[groups]

{{S1, S8}, {S2, S3, S4}, {S5, S6, S7}}