7
$\begingroup$

I have a list of different combinations of letters of the alphabet

{{"a"}, {"b"}, {"c"}, {"a", "b"}, {"a", "c"}, {"b", "c"}}

There is no pattern to them - that isn't important to this problem. Let's call a permutation of this list symmetric if they are the same under substitution, i.e. you can get from one to the other by changing a to b and b to c, or b to a and a to b, etc. For example, the list above is symmetric to:

{{"b"}, {"a"}, {"c"}, {"b", "a"}, {"b", "c"}, {"a", "c"}}

Because you can get to the first from the second with a=b, b=a.

What I need to do is generate all permutations of a list which are not symmetric, to the original list or any other list in the set. I would like this algorithm to be as fast as possible.

I can easily generate permutations of a list with Permutations - but I feel like generating permutations and then looping over every element, and checking if it's symmetric to every other element is incredibly inefficient (O(n!)+O(n^2)).

How can I accomplish this in MMA?

$\endgroup$
  • $\begingroup$ Have you tried generating ALL the permutations (should be "fast"), all the SYMMETRIC permutations (also faster than doing all the checks) and then use the Complement command? $\endgroup$ – Fraccalo Jul 9 '18 at 12:03
  • $\begingroup$ Also, with permutations you mean that you assign to a letter the "value" of another letter, or you can also reshape the list? $\endgroup$ – Fraccalo Jul 9 '18 at 12:40
  • $\begingroup$ Do you require breaking of symmetry w.r.t. a full group $ S_n$ of all permutations or w.r.t. any transitive group only? $\endgroup$ – Slepecky Mamut Jul 9 '18 at 12:49
  • $\begingroup$ @Fraccalo The problem is I want to generate symmetri permutations of lists for which mathematica can’t generate all permutations without running out of memory. So I can’t just generate permutations and check which are non symmetric. And you can reshape the list, just like a normal permutation. $\endgroup$ – NMister Jul 9 '18 at 14:18
  • $\begingroup$ @Slepecky Mamut I’m not sure I understand the question but I’m pretty sure the full $S_n$ $\endgroup$ – NMister Jul 9 '18 at 14:20
1
$\begingroup$

Symmetry

The single example provided to illustrate the notion of symmetry doesn't rule out situations where the shape/structure of the two lists may differ. Depending on whether or not we require the two lists to have the same shape in addition to they being same up to relabeling of atomic elements, we can have two different formalizations of symmetry. The first case can be captured using the ArrayComponents of the two lists; if list1 and list2 have the same ArrayComponents they have the same shape and they are same up to relabeling of atomic elements. Symmetry where shape doesn't matter can be checked using Flattenned ArrayComponents of the two lists (or, the same thing, ArrayComponents of the Flattenned lists). For example:

lst0 = {{"a"}, {"b"}, {"c"}, {"a", "b"}, {"a", "c"}, {"b", "c"}};
lst1 = {{"b"}, {"a"}, {"c"}, {"b", "a"}, {"b", "c"}, {"a", "c"}};
lst2 = { {"b", "a"}, {"b", "c"}, {"a", "c"} ,{"b"}, {"a"}, {"c"}}; 
lst3 = {{"a","b","c"}, {"a", "b"}, {"a", "c"}, {"b", "c"}};  

symQ1 = Equal[ArrayComponents[#], ArrayComponents[#2]] &;
symQ1[lst0, #] & /@ {lst1, lst2, lst3}
{True, False, False} 

symQ2 = Equal[Flatten@ArrayComponents[#], Flatten @ ArrayComponents[#2]] &;  
symQ2[lst0, #] & /@ {lst1, lst2, lst3}  
{True, False, True} 

Generating "shuffles"

By "permutations" of lst0 you seem to mean a combination of Permutations[lst0] and relabeling of atomic elements (Permutations[{"a","b","c"}]). Let's call such things shuffles.

abc = {"a", "b", "c"};
rule = Thread[abc -> #] & /@ Permutations[abc];
labelings = lst0 /. rule ;
MemberQ[labelings , #] & /@ {lst0, lst1, lst2, lst3}  

{True, True, False, False}

labelings // Column // TeXForm

$\begin{array}{l} \{\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\}\} \\ \{\{a\},\{c\},\{b\},\{a,c\},\{a,b\},\{c,b\}\} \\ \{\{b\},\{a\},\{c\},\{b,a\},\{b,c\},\{a,c\}\} \\ \{\{b\},\{c\},\{a\},\{b,c\},\{b,a\},\{c,a\}\} \\ \{\{c\},\{a\},\{b\},\{c,a\},\{c,b\},\{a,b\}\} \\ \{\{c\},\{b\},\{a\},\{c,b\},\{c,a\},\{b,a\}\} \\ \end{array}$

perms = Permutations[lst0];
shuffles = Join @@ (perms /. rule);
MemberQ[shuffles , #] & /@ {lst0, lst1, lst2, lst3} 

{True, True, True, False}

Length @ shuffles

4320

shuffles[[;; 10]] // Column // TeXForm

$\begin{array}{l} \{\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\}\} \\ \{\{a\},\{b\},\{c\},\{a,b\},\{b,c\},\{a,c\}\} \\ \{\{a\},\{b\},\{c\},\{a,c\},\{a,b\},\{b,c\}\} \\ \{\{a\},\{b\},\{c\},\{a,c\},\{b,c\},\{a,b\}\} \\ \{\{a\},\{b\},\{c\},\{b,c\},\{a,b\},\{a,c\}\} \\ \{\{a\},\{b\},\{c\},\{b,c\},\{a,c\},\{a,b\}\} \\ \{\{a\},\{b\},\{a,b\},\{c\},\{a,c\},\{b,c\}\} \\ \{\{a\},\{b\},\{a,b\},\{c\},\{b,c\},\{a,c\}\} \\ \{\{a\},\{b\},\{a,b\},\{a,c\},\{c\},\{b,c\}\} \\ \{\{a\},\{b\},\{a,b\},\{a,c\},\{b,c\},\{c\}\} \\ \end{array}$

Symmetry-free subsets

Using symQ1 and symQ2 we get two different symmetry-free subsets of shuffles:

asymm1 = DeleteDuplicatesBy[ArrayComponents][shuffles];
asymm1 // Length

720

MemberQ[asymm1, #] & /@ {lst0, lst1, lst2, lst3} 

{True, False, False, False}

asymm1[[;; 10]] // Column // TeXForm

$\begin{array}{l} \{\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\}\} \\ \{\{a\},\{b\},\{c\},\{a,b\},\{b,c\},\{a,c\}\} \\ \{\{a\},\{b\},\{c\},\{a,c\},\{a,b\},\{b,c\}\} \\ \{\{a\},\{b\},\{c\},\{a,c\},\{b,c\},\{a,b\}\} \\ \{\{a\},\{b\},\{c\},\{b,c\},\{a,b\},\{a,c\}\} \\ \{\{a\},\{b\},\{c\},\{b,c\},\{a,c\},\{a,b\}\} \\ \{\{a\},\{b\},\{a,b\},\{c\},\{a,c\},\{b,c\}\} \\ \{\{a\},\{b\},\{a,b\},\{c\},\{b,c\},\{a,c\}\} \\ \{\{a\},\{b\},\{a,b\},\{a,c\},\{c\},\{b,c\}\} \\ \{\{a\},\{b\},\{a,b\},\{a,c\},\{b,c\},\{c\}\} \\ \end{array}$

asymm2 = DeleteDuplicatesBy[Flatten[ArrayComponents@#] &][shuffles] ;
asymm2 // Length 

213

MemberQ[asymm2, #] & /@ {lst0, lst1, lst2, lst3} 

{True, False, False, False}

asymm2[[;; 10]] // Column // TeXForm

$\begin{array}{l} \{\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\}\} \\ \{\{a\},\{b\},\{c\},\{a,b\},\{b,c\},\{a,c\}\} \\ \{\{a\},\{b\},\{c\},\{a,c\},\{a,b\},\{b,c\}\} \\ \{\{a\},\{b\},\{c\},\{a,c\},\{b,c\},\{a,b\}\} \\ \{\{a\},\{b\},\{c\},\{b,c\},\{a,b\},\{a,c\}\} \\ \{\{a\},\{b\},\{c\},\{b,c\},\{a,c\},\{a,b\}\} \\ \{\{a\},\{b\},\{a,b\},\{c\},\{a,c\},\{b,c\}\} \\ \{\{a\},\{b\},\{a,b\},\{c\},\{b,c\},\{a,c\}\} \\ \{\{a\},\{b\},\{a,b\},\{a,c\},\{c\},\{b,c\}\} \\ \{\{a\},\{b\},\{a,b\},\{a,c\},\{b,c\},\{c\}\} \\ \end{array}$

$\endgroup$
0
$\begingroup$

I'm not 100% positive I understood correctly what you are asking, but I'll give it a try.

I'm not sure of what you mean with permutation of the list here. I'll split my answer in two, for two alternative cases.

FIRST CASE Permutation in the sense that you assign to a letter the value of another letter, but you can't reshape the list: for example "a" -> "b"

In such a case I'd proceed as follows:

list = {{"a"}, {"b"}, {"c"}, {"a", "b"}, {"a", "c"}, {"b", "c"}};
elements = DeleteDuplicates@Flatten@list

{"a", "b", "c"}

allCases = Tuples[elements, 3];

allCases contains all the possible substitutions from {"a", "b", "c"}

symmCases = Permutations[elements]

{{"a", "b", "c"}, {"a", "c", "b"}, {"b", "a", "c"}, {"b", "c", "a"}, {"c", "a", "b"}, {"c", "b", "a"}}

symmCases contains all the symmetric cases.

asymmCases = Complement[allCases, symmCases]

asymmCases contains all the non symmetric cases.

asymmRules =  Apply[{"a" -> #1, "b" -> #2, "c" -> #3} &, #] & /@ asymmCases;
asymmList = list /. asymmRules;

asymmList contains all the non symmetric lists.

SECOND CASE If you actually want to apply Permutations[list] and pick just the non-symmetric case.

permList = Permutations[list];

symmRules = Apply[{"a" -> #1, "b" -> #2, "c" -> #3} &, #] & /@ symmCases;

symmList = list /. symmRules;

asymmList2 = Complement[permList, symmList];

Dimensions@permList
Dimensions@asymmList2

{720, 6}

{719, 6}

It seems that all the permutations of list but one are non symmetric. The symmetric one is just the trivial transformation

{"a"->"a", "b"->"b", "c"->"c"}

$\endgroup$
  • $\begingroup$ Your second interpretation is correct, but seems to give incorrect answers. What about the example in my question - does your asymmList2 include both the original list and that one? If so, it’s not working correctly. $\endgroup$ – NMister Jul 9 '18 at 14:22
  • 1
    $\begingroup$ @NMister {{"b"}, {"a"}, {"c"}, {"b", "a"}, {"b", "c"}, {"a", "c"}} in your original post can't be obtained with Permutations[list] as it seems from your OP. Can you edit your original post giving a precise definition of what kind of permutation you mean? $\endgroup$ – Fraccalo Jul 9 '18 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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