Count of permutations with N fixed order elements (chromozomes)

Question

I found this question

It is about count of permutations with preserving order of elements in different sets, eg. in case of two sets [A,B,C] [1,2,3] one of solutions might be {A 1 B C 2 3}. In my case there is unlimited number N of sets of variable lengths, for example (N = 4) [A,B] [1,2,3,4] [a,b,c] [-,*,/]. In my final solution chars in these sets has to preserve this given order, so:

[a, A, 1, 2, b, c, -, B, 3, *, /, 4] is valid

[a, 3, A, 1, 2, b, c, -, B, *, /, 4] is invalid.

I am generating solutions like this to generate population in genetic algorithm and I need to calculate how many unique chromozomes is one generation capable of. Is there a nice way how to calculate it? I can't state any of mine resources since I am pretty stuck on this. Thanks for your answer.

Answer 1

hope everything is going well.

I took a look at this and believe I have found a general formula. I also wrote some Python code (at the end) that can find the answers for particular sequences. I am working on a combinatorial explanation, so keep posted.

Given a set $S = \{\{a_1, a_2, \dotsc, a_n\}, \{b_1, b_2, \dotsc, b_m\}, \dotsc, \{c_1, c_2, \dotsc, c_k\} \}$ the number of chromozones (without repetition, i.e. $\{a_1, a_2, \dotsc, a_n\} \cap \{b_1, b_2, \dotsc, b_m\} \cap \dotsc \cap \{c_1, c_2, \dotsc, c_k\} = \emptyset$) formed from these sets in $S$ is equal to

$$\frac{(\sum_{s\in S} |s|)!}{\prod_{s\in S}|s|!}$$

where $|s|$ denotes the cardinality of the subset $s$.

Now onto the code. Here is the output for some examples \begin{align} &\text{# Chromozones for } \{\{1\}, \{2\}, \{3\}, \{4\}\} = 24\\ &\text{# Chromozones for } \{\{a,b,c\}, \{A,B,C\}\} = 20\\ &\text{# Chromozones for } \{\{a,b,c\}, \{1,2\}, \{3,4\}\} = 210\\ &\text{# Chromozones for } \{\{a,b,c\}, \{1\}, \{3,4\}\} = 60\\ &\text{# Chromozones for } \{\{a,b,c\}, \{1\}, \{3\}\} = 20\\ &\text{# Chromozones for } \{\{a,b\}, \{1\}, \{3\}\} = 12\\ &\text{# Chromozones for } \{\{a,b\}, \{1\}\} = 3\\ \end{align}

For your example in particular, the output is:

Invalid and Valid Permutations = 720
('A', 'B', 'C', 'a', 'b', 'c')
('A', 'B', 'a', 'C', 'b', 'c')
('A', 'B', 'a', 'b', 'C', 'c')
('A', 'B', 'a', 'b', 'c', 'C')
('A', 'a', 'B', 'C', 'b', 'c')
('A', 'a', 'B', 'b', 'C', 'c')
('A', 'a', 'B', 'b', 'c', 'C')
('A', 'a', 'b', 'B', 'C', 'c')
('A', 'a', 'b', 'B', 'c', 'C')
('A', 'a', 'b', 'c', 'B', 'C')
('a', 'A', 'B', 'C', 'b', 'c')
('a', 'A', 'B', 'b', 'C', 'c')
('a', 'A', 'B', 'b', 'c', 'C')
('a', 'A', 'b', 'B', 'C', 'c')
('a', 'A', 'b', 'B', 'c', 'C')
('a', 'A', 'b', 'c', 'B', 'C')
('a', 'b', 'A', 'B', 'C', 'c')
('a', 'b', 'A', 'B', 'c', 'C')
('a', 'b', 'A', 'c', 'B', 'C')
('a', 'b', 'c', 'A', 'B', 'C')
# Valid Permutations = 20

Use this code for a particular sequence you are going to have to edit the seq, S, and total variables.

import itertools as it
seq1 = ['A','B']
seq2 = ['a']
seq3 = ['1']
#seq4 = ['5']
S = [seq1, seq2,seq3]
total = seq1+seq2+seq3
total_perms = list(it.permutations(total))
print('Invalid and Valid Permutations =',len(total_perms))
def bad_perms(perm):
    for index, seq in enumerate(S):
        S_rest = [elt for elt in S if elt != seq]
        S_rest = [sub_elt for elt in S_rest for sub_elt in elt]
        perm_minus = [elt for elt in perm if elt not in S_rest]
        if perm_minus != seq:
            return True
    return False
g_perm = 0
b_perm = 0
for perm in total_perms:
    if bad_perms(perm) == True:
        b_perm += 1
        #total_perms.remove(perm)

    else:
        print(perm)
        g_perm += 1
print('# Valid Permutations =', g_perm)

Answer 2

Since you know what the order is in different sets, all you need to know is where to put the sets themselves. If the total number of letters is n, and the cardinalities of the sets are $m_1, \dotsc, m_k,$ so that $m_1 + \dotsc + m_k = n,$ then the answer is just the multinomial coeffficient:

$$\frac{n!}{m_1! \dotsc m_k!}.$$