10
$\begingroup$

I need all the possible 3x3 binary tensors, but I'd like to have this account for symmetries. I've started by using the Tuples command.

Tuples[{1, 0}, {3, 3}]

This tuples command produces 512 binary tensors. If I consider tensors that are symmetric by any permutation to be redundant, how can I remove the extraneous ones from the output? Here are a few examples of tensors that I'd like to consider as the same:

{{0, 1, 0}, {0, 1, 0}, {1, 1, 0}} // MatrixForm
{{1, 1, 0}, {0, 1, 0}, {0, 1, 0}} // MatrixForm
{{0, 1, 0}, {0, 1, 0}, {0, 1, 1}} // MatrixForm
{{0, 0, 1}, {1, 1, 1}, {0, 0, 0}} // MatrixForm

Additionally, I'd like to remove tensors that are equal if you replace the 1's with 0's, and vice versa, such that these two tensors are equivalent:

{{1, 0, 1}, {1, 0, 1}, {0, 1, 0}} // MatrixForm
{{0, 1, 0}, {0, 1, 0}, {1, 0, 1}} // MatrixForm

By my estimation, this should reduce the output from 512 to ~50 tensors.

Any help would be greatly appreciated.

Clarification of "permutations" for the original question:

I'm not sure the most accurate way to describe it. Imagine taking a 3x3 array of 1's and iteratively changing each 1 to a 0 until you have an array of 0's. I consider a duplicate being an array that is identical under any rotation or mirror around any row or diagonal.

For example, if you start with:

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

There are only three distinct 1's that can be removed:

{{0, 1, 1}, {1, 1, 1}, {1, 1, 1}}
{{1, 0, 1}, {1, 1, 1}, {1, 1, 1}} 
{{1, 1, 1}, {1, 0, 1}, {1, 1, 1}}
$\endgroup$
4
  • 1
    $\begingroup$ It is unclear what you mean by "permutation." Is it that (1) the permutation group $S_9$ on all nine tensor elements is acting (probably not; you would get only five equivalence classes--but your example strongly suggests this is what you mean) or (2) $S_3$ acts independently on the two indexes (a group of order $36$) or (3) $S_3$ acts simultaneously on the two indexes (a group of order $6$)? $\endgroup$
    – whuber
    Mar 10, 2013 at 15:17
  • $\begingroup$ Can you clarify what you mean by permutation? What is it that you are permuting exactly? Rows? Columns? Both at the same time? Tensor indices? $\endgroup$
    – Szabolcs
    Mar 10, 2013 at 16:53
  • $\begingroup$ @whuber (3) would amount to constructing all unlabelled graphs with at most 3 vertices, right? $\endgroup$
    – Szabolcs
    Mar 10, 2013 at 17:00
  • $\begingroup$ @Szabolcs I believe so, upon interpreting these arrays as incidence matrices. I think you need to use graphs with exactly three vertices and to allow edges to connect vertices to themselves. Clearly such arrays do determine graphs; conversely, given such a graph, we may label its vertices in one of six unique ways (this is why three vertices are needed, not just at most three) and such a labeling determines a $3\times 3$ incidence matrix; a change of labels simultaneously permutes both the rows and columns of that matrix. $\endgroup$
    – whuber
    Mar 10, 2013 at 17:18

3 Answers 3

7
$\begingroup$

First, get set t2 by removing those tensors that are permutations. Second, get set t3 by removing the tensors that are equivalent when the 0-1 substitutions are considered.

t = Tuples[{1, 0}, {3, 3}];
t2 = DeleteDuplicates[t, Sort@#1 == Sort@#2 &];
t3 = DeleteDuplicates[t2, Sort@(#1 /. {0 -> 1, 1 -> 0}) == Sort@#2 &];
Length@t3

This gives a list with 60 tensors.

Edit:

Given the enhanced explanation about the permitted transformations, I think the following approach may give some idea on how to remove the redundant tensors. Here, I consider the rules that check the mirroring. In its present form, this solution gives 212 matrices (in t2), the number of which can be further reduced by including additional conditions for equivalent tensors (like the 0-1 substitutions). If you also consider tensors being equivalent after multiple mirroring operations, etc., those have to be also implemented. Although this approach seems quite tedious, I hope it may still be satisfactory.

t = Tuples[{1, 0}, {3, 3}];
t2 = DeleteDuplicates[t,
     #1 == Reverse@#2(*mirror with respect to the 2nd row*)||
     #1 == Reverse[#2, 2](*mirror with respect to the 2nd column*)||
     #1 == Transpose@#2(*diagonal*)||
     #1 == Reverse@Transpose@Reverse@#2(*the other diagonal*)
     &];

Edit 2:

Ok, so let me try to complete this answer. The solution by @dpholmes provides the answer to the first part of the question. Here, I will continue from that (list t2) and show how to take into account also the 0-1 substitutions. This results in 51 distinct arrays (t3).

t = Tuples[{1, 0}, {3, 3}];
t2 = DeleteDuplicates[t,
     #1 == Reverse@#2(*mirror with respect to the 2nd row*)||
     #1 == Reverse[#2, 2](*mirror with respect to the 2nd column*)||
     #1 == Transpose@#2(*diagonal*)||
     #1 == Reverse@Transpose@Reverse@#2(*the other diagonal*)|| 
     #1 == Reverse@Transpose@Reverse@Reverse[#2, 1]
     (*mirror with respect to the 2nd row and first diagonal*)||
     #1 == Reverse@Transpose@Reverse@Reverse[#2, 2]
     (*mirror with respect to the 2nd row and other diagonal*)||
     #1 == Reverse[Reverse[#2], 2]
     (*mirror with respect to the 2nd row and the 2nd column*)
     &];
t3 = DeleteDuplicates[t2,
     (#1 /. {1 -> 0, 0 -> 1}) == Reverse@#2(*mirror with respect to the 2nd row*)||
     (#1 /. {1 -> 0, 0 -> 1}) == Reverse[#2, 2](*mirror with respect to the 2nd column*)||
     (#1 /. {1 -> 0, 0 -> 1}) == Transpose@#2(*diagonal*)||
     (#1 /. {1 -> 0, 0 -> 1}) == Reverse@Transpose@Reverse@#2(*the other diagonal*)|| 
     (#1 /. {1 -> 0, 0 -> 1}) == Reverse@Transpose@Reverse@Reverse[#2, 1]
     (*mirror with respect to the 2nd row and first diagonal*)||
     (#1 /. {1 -> 0, 0 -> 1}) == Reverse@Transpose@Reverse@Reverse[#2, 2]
     (*mirror with respect to the 2nd row and other diagonal*)||
     (#1 /. {1 -> 0, 0 -> 1}) == Reverse[Reverse[#2], 2]
     (*mirror with respect to the 2nd row and the 2nd column*)
     &];
$\endgroup$
6
  • 1
    $\begingroup$ This does not seem to account for permutations of the second component, which--according to the example--appear to be involved, too. (I have requested clarification from the OP concerning what is really meant by "permutation," because the question is currently ambiguous.) $\endgroup$
    – whuber
    Mar 10, 2013 at 15:20
  • $\begingroup$ @whuber Given the fourth line in the first example (in the question), it seems the first line could be replaced by t2 = DeleteDuplicates[t, Total@#1 == Total@#2 &]; $\endgroup$ Mar 10, 2013 at 15:29
  • $\begingroup$ @belisarius Right: that's the $S_9$ case, but because it results in only $5$ distinct tensors (upon accounting for the interchange of $0$ and $1$), it does not seem consistent with the OP's expectations. $\endgroup$
    – whuber
    Mar 10, 2013 at 15:50
  • $\begingroup$ @whuber goodreads.com/quotes/… $\endgroup$ Mar 10, 2013 at 15:54
  • $\begingroup$ Sorry about the ambiguity regarding "permutations." I'm not sure the most accurate way to describe it. Imagine taking a 3x3 array of 1's and iteratively changing each 1 to a 0 until you have an array of 0's. I consider a duplicate being an array that is identical under any rotation or mirror around any row or diagonal. j--'s solution is pretty close, although it still misses some. For example, if you do the following command (just to visualize it) you'll see that the 2nd and 5th arrays are the same. ArrayPlot[#, ImageSize -> 20, Mesh -> All] & /@ t3 $\endgroup$
    – dpholmes
    Mar 10, 2013 at 21:08
2
$\begingroup$

In all my notebooks I use a few common customized functions. One is a generic and fault tolerant version of the solution to your question:

(* Eliminate duplicates of any permutation in a list *)
noDups@in_ := If[ListQ@in, DeleteDuplicates[
    DeleteDuplicates@in, 
    If[#2 == {}, True, MemberQ[Permutations@#2, #1]] &], in];

It returns in if it is not a list and does a first order DeleteDuplicates@in before proceeding to eliminate the permutations.

Of course, the specific replacement rules (as given in the first answer) are not part of that common function.

$\endgroup$
8
  • $\begingroup$ Thanks for the tag wiki edits. :-) $\endgroup$
    – Mr.Wizard
    Mar 10, 2013 at 18:35
  • 1
    $\begingroup$ By the way, I believe that there are more efficient ways to write your noDups function. For example: noDups2[other_] := other; noDups2[in_List] := GatherBy[in ~DeleteCases~ {}, Sort][[All, 1]] (Version 7 users will need to use Sort[#]& in place of Sort because of this bug.) $\endgroup$
    – Mr.Wizard
    Mar 10, 2013 at 18:50
  • $\begingroup$ Could you give me an example of the failure, please? $\endgroup$
    – Mr.Wizard
    Mar 12, 2013 at 2:09
  • $\begingroup$ the GatherBy code throws: Sort::normal: Nonatomic expression expected at position 1 in Sort[2]. (I thought I had a fix, but not yet...) $\endgroup$ Mar 12, 2013 at 2:21
  • $\begingroup$ I guess I didn't understand noDups as I had thought; what kind of input may this function receive? I had assumed a list of lists, though I didn't put that in the Pattern. $\endgroup$
    – Mr.Wizard
    Mar 12, 2013 at 2:30
0
$\begingroup$

First, many thanks to @j--, his answer was both helpful and educational (the commented code was especially insightful).

This answer is in regard to the first part of the question. It requires checking for symmetry with respect to mirrors of the second row, the second column, and the two diagonals (thanks to @j-- for instruction. But, it also requires checking for symmetry by mirror of the second row and each diagonal, and mirroring about the second row and column (together).

The resulting code is (admittedly tedious and unoptimized):

t = Tuples[{1, 0}, {3, 3}];
t2 = DeleteDuplicates[
   t, #1 == Reverse@#2(*mirror with respect to the 2nd row*)|| #1 == 
      Reverse[#2, 2](*mirror with respect to the 2nd column*)|| #1 == 
      Transpose@#2(*diagonal*)|| #1 == 
      Reverse@Transpose@Reverse@#2(*the other diagonal*)|| #1 == 
      Reverse@Transpose@
        Reverse@Reverse[#2, 
          1](*mirror with respect to the 2nd row and first \
diagonal*)|| #1 == 
      Reverse@Transpose@
        Reverse@Reverse[#2, 
          2](*mirror with respect to the 2nd row and other \
diagonal*)|| #1 == 
      Reverse[Reverse[#2], 
       2](*mirror with respect to the 2nd row and the 2nd column*)&];

This code results in 102 distinct arrays, which matches the original expectation (from doing it out by hand...).

The second part of this question is still unanswered, it should result in 51 distinct arrays.

$\endgroup$
1
  • 1
    $\begingroup$ I have updated my answer based on your solution by including a check for the similarity after the 0-1 substitutions. Now, I get 51 distinct arrays. $\endgroup$
    – j--
    Mar 12, 2013 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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