Generating permutations

Question

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?

Answer 1

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}$

Answer 2

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"}