0
$\begingroup$

I need a math formula for counting distinct n- letter long array permutations.

Let me explain. Let's say we have 3 arrays of following letters: A, B, C, where A is a 4 member long array (A[0],A[1],A[2],A[3]), B is a 4 member long array and C is a 1 member long array.

How do I calculate the total number of all unique n-letter long permutations, without programmatically permuting through them?

--

EXAMPLE

Letter combination:

A, B, B, C

Given array lengths of each letter (as described above) I know there are 768 unique permutations. I got to 768 by writing a program that goes through all of the combinations, discarding duplicates.

These are unique combinations such as:

A[0],B[0],B[0],C[0]

or

C[0],B[3],A[3],B[1]

However, I need a mathematical formula to answer how many unique permutations are there for any number of letters and any length of the letter arrays.

I need this for my open source project that solves tetronimo based puzzles: https://github.com/JozefJarosciak/TetronimoPuzzleSolver/

$\endgroup$
  • $\begingroup$ I'm a little confused about your example. Do the combinations need to consist of one choice from the $A$ array, two from the $B$ array, and one from the $C$ array, in any order? $\endgroup$ – Y. Forman Jan 19 '18 at 14:34
  • $\begingroup$ Exactly correct. One from each letter array in any order. For example, if I have A, C, A, A, then there have to be four letters in any order... $\endgroup$ – jjj Jan 19 '18 at 14:52
  • $\begingroup$ Okay. I'm about to write an answer, but I just want to confirm -- are you sure you got 786 and not 768? $\endgroup$ – Y. Forman Jan 19 '18 at 14:59
  • $\begingroup$ yes, that was a mistake on my part... thanks $\endgroup$ – jjj Jan 19 '18 at 15:27
1
$\begingroup$

I'll state the problem as follows: we have $k$ different arrays, and in each array $A_\ell$ (for $1 \leq \ell \leq k$), we have a choice of $m_\ell$ elements. We are given a number of elements $n_\ell$ to use from each array $A_\ell$ to create an (ordered) $n$-element string, with $n = \sum_{\ell=1}^kn_\ell$. (The choice is made "with replacement," i.e., the same element is allowed to appear multliple times in the string.) How many strings are possible?

One method to do this is to first determine the ordering of the arrays, then make the choices in each slot. I.e., first we create a string that looks like $A_1 A_3 A_2 A_2$, then we choose a particular element from $A_1$ for the first slot, a particular element from $A_3$ for the second slot, etc. The number of ways to order the arrays is given by the multinomial coefficient $$\binom{n}{n_1, n_2, \dotsc, n_k} = \frac{n!}{n_1!n_2!\cdots n_k!}$$ The number of choices in a particular slot in which $A_\ell$ appears is $m_\ell$, and since $A_\ell$ appears in $n_\ell$ slots, the total number of choices for all appearances of $A_\ell$ is $m_\ell^{n_\ell}$. Thus the total number of possible strings is $$\frac{n!}{n_1!n_2!\cdots n_k!} m_1^{n_1} m_2^{n_2} \dotsc m_k^{n_k} $$

In your example, I'll call your arrays $A = A_1$, $B = A_2$, and $C= A_3$. Then we have $m_1 = m_2 = 4$, $m_3 = 1$, $n_1 = n_3 = 1$, $n_2 = 2$, $n = 1 + 2 + 1 = 4$. We thus get an answer of $$ \frac{4!}{1!2!1!}4^14^21^1 = 768$$

$\endgroup$
  • $\begingroup$ This is a perfect answer, exactly what I needed. Thank you so much, it'll certainly be fun coding this into app, much appreciated. $\endgroup$ – jjj Jan 19 '18 at 15:27
  • 1
    $\begingroup$ @jjj You're welcome. Enjoy the coding! $\endgroup$ – Y. Forman Jan 19 '18 at 15:31
  • $\begingroup$ Let's say I have the following 5 tetronimo blocks: J, L, L, O, O. That's 5 letters. Each block has following number of possible states: J - 4; L - 4; L - 4; O - 1; O - 1. Now let's group them: 1 x J - each has 4 states = 4¹; 2 x L - each has 4 states = 4²; 2 x O - each has 1 state = 1². Calculation: (5! / (1!x2!x2!)) x (4¹x4²x1²), goes to (120 / 4) x (4x16x1); then (120 / 4) x (4x16x1); which is (30) x (64) and the result = 1920. This really works like a charm. Thanks. $\endgroup$ – jjj Jan 19 '18 at 16:11
  • $\begingroup$ The code is now working, check it out: blockpuzzlesolver.com $\endgroup$ – jjj Jan 21 '18 at 2:16

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.