DeleteDuplicates[Permute[{g, g, g, g, g, e, r}, AlternatingGroup[7]]]

How to count number of lists automatically?

  • $\begingroup$ Would you explain more? $\endgroup$ – DavidC May 7 '14 at 21:59
  • $\begingroup$ There is nothing built-in to count restricted permutations of this type. $\endgroup$ – ciao May 7 '14 at 23:48
  • $\begingroup$ If all you want is the count, use Multinomial. Multinomial[5,1,1] Out[18]= 42 $\endgroup$ – Daniel Lichtblau Oct 19 '14 at 18:50

Let's define your function and my proposal:

f1[l_, gr_] := Length@DeleteDuplicates@Permute[l, gr@Length@l]
f2[l_, gr_] := GroupOrder@gr@Length@l /
               GroupOrder@GroupSetwiseStabilizer[gr@Length@l, {l}, Permute]

f2 isn't always faster than f1,but can calculate things where f1 fails due to memory constraints. For example:

Timing@f1[{a, a, a, a, a, a, a, a, b, b, c, c}, AlternatingGroup]

Permute::nomem: The current computation was aborted because there was insufficient memory available to complete the computation.


Timing@f2[{a, a, a, a, a, a, a, a, b, b, c, c}, AlternatingGroup]
 {2.265625, 2970}
| improve this answer | |
  • $\begingroup$ I think ... Length@DeleteDuplicates[Permute[{g, g, g, g, g, e, r}, AlternatingGroup[7]]] is fine to get it. $\endgroup$ – santosh May 8 '14 at 14:28
  • $\begingroup$ @santosh Sorry.What do you mean? $\endgroup$ – Dr. belisarius May 8 '14 at 14:37
  • $\begingroup$ I just want to count the number of permutations. $\endgroup$ – santosh May 8 '14 at 14:41
  • 1
    $\begingroup$ @santosh f1 (your way) and f2 (my function) both count that. But f2 works for a larger set of lists (and larger lists). Also, it's faster in many cases. $\endgroup$ – Dr. belisarius May 8 '14 at 14:44
  • $\begingroup$ ok thanks...I got it. $\endgroup$ – santosh May 8 '14 at 14:47

If it's the number of permutations you want, wouldn't it be easier to just use factorials? Please let me know if I'm missing something, but I think you could compute it as follows:

Suppose you have a list $\ell$ of $m$ entries containing $k\leq m$ distinct elements and let $n_k$ be the number of occurrences of the $k$-th element. For instance, suppose our list is $$ \ell\ =\ (a_1, a_2, a_2, a_3, a_3, a_3, a_3, a_3) $$ In this case, $m=8$, $k=3$, $n_1=1$, $n_2=2$, $n_3=5$.

The number of permutations is computed from $m$ and the $n_i$'s as: $$ \#\text{perms}\ =\ \frac{m!}{n_1!\ \cdots\ n_k!} $$ This is implemented in Mathematica by the Multinomial function. For instance, the above example is written as:

perms[list_]:= Multinomial @@ Tally[list][[All,2]]

Correct me if I'm wrong, but doesn't this improve performance immensely?

| improve this answer | |
  • $\begingroup$ Hi! I think you missed an important part of the question. The title says "under a permutation group" :) $\endgroup$ – Dr. belisarius Oct 19 '14 at 11:14
  • $\begingroup$ Ah, I see.. thanks! $\endgroup$ – Kris Oct 19 '14 at 13:29

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.