2
$\begingroup$
DeleteDuplicates[Permute[{g, g, g, g, g, e, r}, AlternatingGroup[7]]]

How to count number of lists automatically?

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

2 Answers 2

3
$\begingroup$

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.

While:

Timing@f2[{a, a, a, a, a, a, a, a, b, b, c, c}, AlternatingGroup]
(*
 {2.265625, 2970}
*)
$\endgroup$
5
  • $\begingroup$ I think ... Length@DeleteDuplicates[Permute[{g, g, g, g, g, e, r}, AlternatingGroup[7]]] is fine to get it. $\endgroup$
    – santosh
    Commented May 8, 2014 at 14:28
  • $\begingroup$ @santosh Sorry.What do you mean? $\endgroup$ Commented May 8, 2014 at 14:37
  • $\begingroup$ I just want to count the number of permutations. $\endgroup$
    – santosh
    Commented May 8, 2014 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$ Commented May 8, 2014 at 14:44
  • $\begingroup$ ok thanks...I got it. $\endgroup$
    – santosh
    Commented May 8, 2014 at 14:47
0
$\begingroup$

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?

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

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.