Revision history [back]
 | 1 | initial version |
Since $F$ must preserve the number, it's worth to decompose the problem into smaller subproblems, where the number is fixed. E.g., in the first example, you'd have 3 subproblems with number being 2, 3, and 4, respectively.
Let's consider such a subproblem, where the number is fixed.
Let $A$ be a set of elements from L1, and $A_1$ be the set of elements from LL1. Denote $A_2:=A\setminus A_1$, so that $A = A_1\sqcup A_2$.
Similarly, let $B$ be the set of elements from L2, and $B_1$ be the set of elements from LL2. Denote $B_2:=B\setminus B_1$, so that $B = B_1\sqcup B_2$.
Let $C_1 := A_1 \cap B_1$ and $C_2 := A_2\cap B_2$. Then define $A_1^\star := A_1\setminus C_1$, $A_2^\star := A_2\setminus C_2$, $B_1^\star := B_1\setminus C_1$, $B_2^\star := B_2\setminus C_2$.
From the definition it follows that the sets $A_1^\star, A_2^\star, B_1^\star, B_2^\star, C_1, C_2$ are pairwise disjoint. Furthermore, $$A=A_1^\star \sqcup A_2^\star \sqcup C_1 \sqcup C_2,$$ $$B=B_1^\star \sqcup B_2^\star \sqcup C_1 \sqcup C_2.$$ The properties of $F$ imply that $F(A_1^\star)=B_1^\star$, $F(B_1^\star)=A_1^\star$, $F(A_2^\star)=B_2^\star$, $F(B_2^\star)=A_2^\star$, $F(C_1)=C_1$, and $F(C_2)=C_2$. Other than that $F$ can be an arbitrary involution.
From this consideration, it should be easy to construct a particular $F$.
| | 2 | No.2 Revision |
Since $F$ must preserve the number, it's worth to decompose the problem into smaller subproblems, where the number is fixed. E.g., in the first example, you'd have 3 subproblems with number being 2, 3, and 4, respectively.
Let's consider such a subproblem, where the number is fixed.
Let $A$ be a set of elements from L1, and $A_1$ be the set of elements from LL1. Denote $A_2:=A\setminus A_1$, so that $A = A_1\sqcup A_2$.
Similarly, let $B$ be the set of elements from L2, and $B_1$ be the set of elements from LL2. Denote $B_2:=B\setminus B_1$, so that $B = B_1\sqcup B_2$.
For existence of $F$, it is necessary that $A_1\cap B_2=A_2\cap B_1=\emptyset$.
Let $C_1 := A_1 \cap B_1$ and $C_2 := A_2\cap B_2$. Then define $A_1^\star := A_1\setminus C_1$, $A_2^\star := A_2\setminus C_2$, $B_1^\star := B_1\setminus C_1$, $B_2^\star := B_2\setminus C_2$.
From the definition it follows that the sets $A_1^\star, A_2^\star, B_1^\star, B_2^\star, C_1, C_2$ are pairwise disjoint. Furthermore, $$A=A_1^\star \sqcup A_2^\star \sqcup C_1 \sqcup C_2,$$ $$B=B_1^\star \sqcup B_2^\star \sqcup C_1 \sqcup C_2.$$ The properties of $F$ imply that $F(A_1^\star)=B_1^\star$, $F(B_1^\star)=A_1^\star$, $F(A_2^\star)=B_2^\star$, $F(B_2^\star)=A_2^\star$, $F(C_1)=C_1$, and $F(C_2)=C_2$. Other than that $F$ can be an arbitrary involution.
From this consideration, it should be easy to construct a particular $F$.
| | 3 | No.3 Revision |
Since $F$ must preserve the number, it's worth to decompose the problem into smaller subproblems, where the number is fixed. E.g., in the first example, you'd have 3 subproblems with number being 2, 3, and 4, respectively.
Let's consider such a subproblem, where the number is fixed.
Let $A$ be a set of elements from L1, and $A_1$ be the set of elements from LL1. Denote $A_2:=A\setminus A_1$, so that $A = A_1\sqcup A_2$.
Similarly, let $B$ be the set of elements from L2, and $B_1$ be the set of elements from LL2. Denote $B_2:=B\setminus B_1$, so that $B = B_1\sqcup B_2$.
For existence of $F$, it is necessary that $A_1\cap B_2=A_2\cap B_1=\emptyset$.
Let $C_1 := A_1 \cap B_1$ and $C_2 := A_2\cap B_2$. Then define $A_1^\star := A_1\setminus C_1$, $A_2^\star := A_2\setminus C_2$, $B_1^\star := B_1\setminus C_1$, $B_2^\star := B_2\setminus C_2$.
From the definition it follows that the sets $A_1^\star, A_2^\star, B_1^\star, B_2^\star, C_1, C_2$ are pairwise disjoint. Furthermore, $$A=A_1^\star \sqcup A_2^\star \sqcup C_1 \sqcup C_2,$$ $$B=B_1^\star \sqcup B_2^\star \sqcup C_1 \sqcup C_2.$$ The properties of $F$ imply that $F(A_1^\star)=B_1^\star$, $F(B_1^\star)=A_1^\star$, $F(A_2^\star)=B_2^\star$, $F(B_2^\star)=A_2^\star$, $F(C_1)=C_1$, and $F(C_2)=C_2$. Other than that $F$ can be an arbitrary involution.
From this consideration, it should be it's easy to construct a particular $F$.
Here us a sample code:
def construct_F_fixed_num( L1, LL1, L2, LL2, num ):
A = { tuple(q) for q,n in L1 if n==num }
A1 = { tuple(q) for q,n in LL1 if n==num }
A2 = A - A1
B = { tuple(q) for q,n in L2 if n==num }
B1 = { tuple(q) for q,n in LL2 if n==num }
B2 = B - B1
assert len(A1 & B2) == 0
assert len(A2 & B1) == 0
C1 = A1 & B1
C2 = A2 & B2
A1s = A1 - C1
A2s = A2 - C2
B1s = B1 - C1
B2s = B2 - C2
assert len(A1s) == len(B1s)
assert len(A2s) == len(B2s)
return list( zip(C1,C1,[num]*len(C1)) ) + list( zip(C2,C2,[num]*len(C2)) ) + list( zip(A1s,B1s,[num]*len(A1s)) ) + list( zip(A2s,B2s,[num]*len(A2s)) )
def construct_F( L1, LL1, L2, LL2 ):
N = { n for _,n in L1+L2 }
return sum( (construct_F_fixed_num( L1, LL1, L2, LL2, n ) for n in N), [] )
Running construct_F( L1, LL1, L2, LL2 ) on your first example returns:
[((4, 3, 2, 1), (2, 2, 2, 1), 2),
((2, 3, 2, 1), (2, 3, 2, 1), 3),
((3, 2, 2, 1), (3, 2, 2, 1), 3),
((3, 3, 2, 1), (3, 3, 2, 1), 3),
((2, 2, 2, 1), (4, 3, 2, 1), 4)]
This is not exactly in the format you want, but reformatting should be easy.
| | 4 | No.4 Revision |
Since $F$ must preserve the number, it's worth to decompose the problem into smaller subproblems, where the number is fixed. E.g., in the first example, you'd have 3 subproblems with number being 2, 3, and 4, respectively.
Let's consider such a subproblem, where the number is fixed.
Let $A$ be a set of elements from L1, and $A_1$ be the set of elements from LL1. Denote $A_2:=A\setminus A_1$, so that $A = A_1\sqcup A_2$.
Similarly, let $B$ be the set of elements from L2, and $B_1$ be the set of elements from LL2. Denote $B_2:=B\setminus B_1$, so that $B = B_1\sqcup B_2$.
For existence of $F$, it is necessary that $A_1\cap B_2=A_2\cap B_1=\emptyset$.
Let $C_1 := A_1 \cap B_1$ and $C_2 := A_2\cap B_2$. Then define $A_1^\star := A_1\setminus C_1$, $A_2^\star := A_2\setminus C_2$, $B_1^\star := B_1\setminus C_1$, $B_2^\star := B_2\setminus C_2$.
From the definition it follows that the sets $A_1^\star, A_2^\star, B_1^\star, B_2^\star, C_1, C_2$ are pairwise disjoint. Furthermore, $$A=A_1^\star \sqcup A_2^\star \sqcup C_1 \sqcup C_2,$$ $$B=B_1^\star \sqcup B_2^\star \sqcup C_1 \sqcup C_2.$$ The properties of $F$ imply that $F(A_1^\star)=B_1^\star$, $F(B_1^\star)=A_1^\star$, $F(A_2^\star)=B_2^\star$, $F(B_2^\star)=A_2^\star$, $F(C_1)=C_1$, and $F(C_2)=C_2$. Other than that $F$ can be an arbitrary involution.
From this consideration, it's easy to construct a particular $F$.
Here us a sample code:
def construct_F_fixed_num( L1, LL1, L2, LL2, num ):
A = { tuple(q) for q,n in L1 if n==num }
A1 = { tuple(q) for q,n in LL1 if n==num }
A2 = A - A1
B = { tuple(q) for q,n in L2 if n==num }
B1 = { tuple(q) for q,n in LL2 if n==num }
B2 = B - B1
assert len(A1 & B2) == 0
assert len(A2 & B1) == 0
C1 = A1 & B1
C2 = A2 & B2
A1s = A1 - C1
A2s = A2 - C2
B1s = B1 - C1
B2s = B2 - C2
assert len(A1s) == len(B1s)
assert len(A2s) == len(B2s)
return list( zip(C1,C1,[num]*len(C1)) ) + list( zip(C2,C2,[num]*len(C2)) ) + list( zip(A1s,B1s,[num]*len(A1s)) ) + list( zip(A2s,B2s,[num]*len(A2s)) )
def construct_F( L1, LL1, L2, LL2 ):
N = { n for _,n in L1+L2 }
return sum( (construct_F_fixed_num( L1, LL1, L2, LL2, n ) for n in N), [] )
Running construct_F( L1, LL1, L2, LL2 ) on from your first example returns:
[((4, 3, 2, 1), (2, 2, 2, 1), 2),
((2, 3, 2, 1), (2, 3, 2, 1), 3),
((3, 2, 2, 1), (3, 2, 2, 1), 3),
((3, 3, 2, 1), (3, 3, 2, 1), 3),
((2, 2, 2, 1), (4, 3, 2, 1), 4)]
This is not exactly in the format you want, but reformatting should be easy.
| | 5 | No.5 Revision |
Since $F$ must preserve the number, it's worth to decompose the problem into smaller subproblems, where the number is fixed. E.g., in the first example, you'd have 3 subproblems with number being 2, 3, and 4, respectively.
Let's consider such a subproblem, where the number is fixed.
Let $A$ be a set of elements from L1, and $A_1$ be the set of elements from LL1. Denote $A_2:=A\setminus A_1$, so that $A = A_1\sqcup A_2$.
Similarly, let $B$ be the set of elements from L2, and $B_1$ be the set of elements from LL2. Denote $B_2:=B\setminus B_1$, so that $B = B_1\sqcup B_2$.
For existence of $F$, it is necessary that $A_1\cap B_2=A_2\cap B_1=\emptyset$.
Let $C_1 := A_1 \cap B_1$ and $C_2 := A_2\cap B_2$. Then define $A_1^\star := A_1\setminus C_1$, $A_2^\star := A_2\setminus C_2$, $B_1^\star := B_1\setminus C_1$, $B_2^\star := B_2\setminus C_2$.
From the definition it follows that the sets $A_1^\star, A_2^\star, B_1^\star, B_2^\star, C_1, C_2$ are pairwise disjoint. Furthermore,
$$A=A_1^\star \sqcup A_2^\star \sqcup C_1 \sqcup C_2,$$
$$B=B_1^\star \sqcup B_2^\star \sqcup C_1 \sqcup C_2.$$
The properties of $F$ imply that $F(A_1^\star)=B_1^\star$, $F(B_1^\star)=A_1^\star$, $F(A_2^\star)=B_2^\star$, $F(B_2^\star)=A_2^\star$, $F(C_1)=C_1$, and $F(C_2)=C_2$. Other than that $F$ can be an arbitrary involution.involution.
In particular, we can take $F$ to be the identity on $C_1\cup C_2$.
From this consideration, it's easy to construct a particular $F$.
Here us a sample code:
def construct_F_fixed_num( L1, LL1, L2, LL2, num ):
A = { tuple(q) for q,n in L1 if n==num }
A1 = { tuple(q) for q,n in LL1 if n==num }
A2 = A - A1
B = { tuple(q) for q,n in L2 if n==num }
B1 = { tuple(q) for q,n in LL2 if n==num }
B2 = B - B1
assert len(A1 & B2) == 0
assert len(A2 & B1) == 0
C1 = A1 & B1
C2 = A2 & B2
A1s = A1 - C1
A2s = A2 - C2
B1s = B1 - C1
B2s = B2 - C2
assert len(A1s) == len(B1s)
assert len(A2s) == len(B2s)
C = C1 + C2
return list( zip(C1,C1,[num]*len(C1)) ) + list( zip(C2,C2,[num]*len(C2)) zip(C,C,[num]*len(C)) ) + list( zip(A1s,B1s,[num]*len(A1s)) ) + list( zip(A2s,B2s,[num]*len(A2s)) )
def construct_F( L1, LL1, L2, LL2 ):
N = { n for _,n in L1+L2 }
return sum( (construct_F_fixed_num( L1, LL1, L2, LL2, n ) for n in N), [] )
Running construct_F( L1, LL1, L2, LL2 ) from your first example returns:
[((4, 3, 2, 1), (2, 2, 2, 1), 2),
((2, 3, 2, 1), (2, 3, 2, 1), 3),
((3, 2, 2, 1), (3, 2, 2, 1), 3),
((3, 3, 2, 1), (3, 3, 2, 1), 3),
((2, 2, 2, 1), (4, 3, 2, 1), 4)]
This is not exactly in the format you want, but reformatting should be easy.
| | 6 | No.6 Revision |
Since $F$ must preserve the number, it's worth to decompose the problem into smaller subproblems, where the number is fixed. E.g., in the first example, you'd have 3 subproblems with number being 2, 3, and 4, respectively.
Let's consider such a subproblem, where the number is fixed.
Let $A$ be a set of elements from L1, and $A_1$ be the set of elements from LL1. Denote $A_2:=A\setminus A_1$, so that $A = A_1\sqcup A_2$.
Similarly, let $B$ be the set of elements from L2, and $B_1$ be the set of elements from LL2. Denote $B_2:=B\setminus B_1$, so that $B = B_1\sqcup B_2$.
For existence of $F$, it is necessary that $A_1\cap B_2=A_2\cap B_1=\emptyset$.
Let $C_1 := A_1 \cap B_1$ and $C_2 := A_2\cap B_2$. Then define $A_1^\star := A_1\setminus C_1$, $A_2^\star := A_2\setminus C_2$, $B_1^\star := B_1\setminus C_1$, $B_2^\star := B_2\setminus C_2$.
From the definition it follows that the sets $A_1^\star, A_2^\star, B_1^\star, B_2^\star, C_1, C_2$ are pairwise disjoint. Furthermore, $$A=A_1^\star \sqcup A_2^\star \sqcup C_1 \sqcup C_2,$$ $$B=B_1^\star \sqcup B_2^\star \sqcup C_1 \sqcup C_2.$$ The properties of $F$ imply that $F(A_1^\star)=B_1^\star$, $F(B_1^\star)=A_1^\star$, $F(A_2^\star)=B_2^\star$, $F(B_2^\star)=A_2^\star$, $F(C_1)=C_1$, and $F(C_2)=C_2$. Other than that $F$ can be an arbitrary involution. In particular, we can take $F$ to be the identity on $C_1\cup C_2$.
From this consideration, it's easy to construct a particular $F$.
Here us a sample code:
def construct_F_fixed_num( L1, LL1, L2, LL2, num ):
A = { tuple(q) for q,n in L1 if n==num }
A1 = { tuple(q) for q,n in LL1 if n==num }
A2 = A - A1
B = { tuple(q) for q,n in L2 if n==num }
B1 = { tuple(q) for q,n in LL2 if n==num }
B2 = B - B1
assert len(A1 & B2) == 0
assert len(A2 & B1) == 0
C1 = A1 & B1
C2 = A2 & B2
A1s = A1 - C1
A2s = A2 - C2
B1s = B1 - C1
B2s = B2 - C2
assert len(A1s) == len(B1s)
assert len(A2s) == len(B2s)
C = C1 + | C2
return list( zip(C,C,[num]*len(C)) ) + list( zip(A1s,B1s,[num]*len(A1s)) ) + list( zip(A2s,B2s,[num]*len(A2s)) )
def construct_F( L1, LL1, L2, LL2 ):
N = { n for _,n in L1+L2 }
return sum( (construct_F_fixed_num( L1, LL1, L2, LL2, n ) for n in N), [] )
Running construct_F( L1, LL1, L2, LL2 ) from your first example returns:
[((4, 3, 2, 1), (2, 2, 2, 1), 2),
((2, 3, 2, 1), (2, 3, 2, 1), 3),
((3, 2, 2, 1), (3, 2, 2, 1), 3),
((3, 3, 2, 1), (3, 3, 2, 1), 3),
((2, 2, 2, 1), (4, 3, 2, 1), 4)]
This is not exactly in the format you want, but reformatting should be easy.
| | 7 | No.7 Revision |
Since $F$ must preserve the number, it's worth to decompose the problem into smaller subproblems, where the number is fixed. E.g., in the first example, you'd have 3 subproblems with number being 2, 3, and 4, respectively.
Let's consider such a subproblem, where the number is fixed.
Let $A$ be a set of elements from L1, and $A_1$ be the set of elements from LL1. Denote $A_2:=A\setminus A_1$, so that $A = A_1\sqcup A_2$.
Similarly, let $B$ be the set of elements from L2, and $B_1$ be the set of elements from LL2. Denote $B_2:=B\setminus B_1$, so that $B = B_1\sqcup B_2$.
For existence of $F$, it is necessary that $A_1\cap B_2=A_2\cap B_1=\emptyset$.
Let $C_1 := A_1 \cap B_1$ and $C_2 := A_2\cap B_2$. Then define $A_1^\star := A_1\setminus C_1$, $A_2^\star := A_2\setminus C_2$, $B_1^\star := B_1\setminus C_1$, $B_2^\star := B_2\setminus C_2$.
From the definition it follows that the sets $A_1^\star, A_2^\star, B_1^\star, B_2^\star, C_1, C_2$ are pairwise disjoint. Furthermore, $$A=A_1^\star \sqcup A_2^\star \sqcup C_1 \sqcup C_2,$$ $$B=B_1^\star \sqcup B_2^\star \sqcup C_1 \sqcup C_2.$$ The properties of $F$ imply that $F(A_1^\star)=B_1^\star$, $F(B_1^\star)=A_1^\star$, $F(A_2^\star)=B_2^\star$, $F(B_2^\star)=A_2^\star$, $F(C_1)=C_1$, and $F(C_2)=C_2$. Other than that $F$ can be an arbitrary involution. In particular, we can take $F$ to be the identity on $C_1\cup C_2$.
From this consideration, it's easy to construct a particular $F$.
Here us a sample code:
def construct_F_fixed_num( L1, LL1, L2, LL2, num ):
A = { tuple(q) for q,n in L1 if n==num }
A1 = { tuple(q) for q,n in LL1 if n==num }
A2 = A - A1
B = { tuple(q) for q,n in L2 if n==num }
B1 = { tuple(q) for q,n in LL2 if n==num }
B2 = B - B1
assert len(A1 & B2) == 0
assert len(A2 & B1) == 0
C1 = A1 & B1
C2 = A2 & B2
A1s = A1 - C1
A2s = A2 - C2
B1s = B1 - C1
B2s = B2 - C2
assert len(A1s) == len(B1s)
assert len(A2s) == len(B2s)
C = C1 | C2
return list( zip(C,C,[num]*len(C)) ) + list( zip(A1s,B1s,[num]*len(A1s)) ) + list( zip(A2s,B2s,[num]*len(A2s)) )
def construct_F( L1, LL1, L2, LL2 ):
N = { n for _,n in L1+L2 }
return sum( (construct_F_fixed_num( L1, LL1, L2, LL2, n ) for n in N), [] )
Running construct_F( L1, LL1, L2, LL2 ) on the sets from your first example returns:
[((4, 3, 2, 1), (2, 2, 2, 1), 2),
((2, 3, 2, 1), (2, 3, 2, 1), 3),
((3, 2, 2, 1), (3, 2, 2, 1), 3),
((3, 3, 2, 1), (3, 3, 2, 1), 3),
((2, 2, 2, 1), (4, 3, 2, 1), 4)]
This is not exactly in the format you want, but reformatting should be easy.
| | 8 | No.8 Revision |
Since $F$ must preserve the number, it's worth to decompose the problem into smaller subproblems, where the number is fixed. E.g., in the first example, you'd have 3 subproblems with number being 2, 3, and 4, respectively.
Let's consider such a subproblem, where the number is fixed.
Let $A$ be a set of elements from L1, and $A_1$ be the set of elements from LL1. Denote $A_2:=A\setminus A_1$, so that $A = A_1\sqcup A_2$.
Similarly, let $B$ be the set of elements from L2, and $B_1$ be the set of elements from LL2. Denote $B_2:=B\setminus B_1$, so that $B = B_1\sqcup B_2$.
For existence of $F$, it is necessary that $A_1\cap B_2=A_2\cap B_1=\emptyset$.
Let $C_1 := A_1 \cap B_1$ and $C_2 := A_2\cap B_2$. Then define $A_1^\star := A_1\setminus C_1$, $A_2^\star := A_2\setminus C_2$, $B_1^\star := B_1\setminus C_1$, $B_2^\star := B_2\setminus C_2$.
From the definition it follows that the sets $A_1^\star, A_2^\star, B_1^\star, B_2^\star, C_1, C_2$ are pairwise disjoint. Furthermore, $$A=A_1^\star \sqcup A_2^\star \sqcup C_1 \sqcup C_2,$$ $$B=B_1^\star \sqcup B_2^\star \sqcup C_1 \sqcup C_2.$$ The properties of $F$ imply that $F(A_1^\star)=B_1^\star$, $F(B_1^\star)=A_1^\star$, $F(A_2^\star)=B_2^\star$, $F(B_2^\star)=A_2^\star$, $F(C_1)=C_1$, and $F(C_2)=C_2$. Other than that $F$ can be an arbitrary involution. In particular, we can take $F$ to be the identity on $C_1\cup C_2$.
From this consideration, it's easy to construct a particular $F$.
Here us a sample code:
def construct_F_fixed_num( L1, LL1, L2, LL2, num ):
A = { tuple(q) for q,n in L1 if n==num }
A1 = { tuple(q) for q,n in LL1 if n==num }
A2 = A - A1
B = { tuple(q) for q,n in L2 if n==num }
B1 = { tuple(q) for q,n in LL2 if n==num }
B2 = B - B1
assert len(A1 & B2) == 0
assert len(A2 & B1) == 0
C1 = A1 & B1
C2 = A2 & B2
A1s = A1 - C1
A2s = A2 - C2
B1s = B1 - C1
B2s = B2 - C2
assert len(A1s) == len(B1s)
assert len(A2s) == len(B2s)
C = C1 | C2
return list( zip(C,C,[num]*len(C)) ) + list( zip(A1s,B1s,[num]*len(A1s)) ) + list( zip(A2s,B2s,[num]*len(A2s)) )
def construct_F( L1, LL1, L2, LL2 ):
N = { n for _,n in L1+L2 }
return sum( (construct_F_fixed_num( L1, LL1, L2, LL2, n ) for n in N), [] )
Running construct_F( L1, LL1, L2, LL2 ) on the sets lists from your first example returns:
[((4, 3, 2, 1), (2, 2, 2, 1), 2),
((2, 3, 2, 1), (2, 3, 2, 1), 3),
((3, 2, 2, 1), (3, 2, 2, 1), 3),
((3, 3, 2, 1), (3, 3, 2, 1), 3),
((2, 2, 2, 1), (4, 3, 2, 1), 4)]
This is not exactly in the format you want, but reformatting should be easy.
| | 9 | No.9 Revision |
Since $F$ must preserve the number, it's worth to decompose the problem into smaller subproblems, where the number is fixed. E.g., in the first example, you'd have 3 subproblems with number being 2, 3, and 4, respectively.
Let's consider such a subproblem, where the number is fixed.
Let $A$ be a set of elements from L1, and $A_1$ be the set of elements from LL1. Denote $A_2:=A\setminus A_1$, so that $A = A_1\sqcup A_2$.
Similarly, let $B$ be the set of elements from L2, and $B_1$ be the set of elements from LL2. Denote $B_2:=B\setminus B_1$, so that $B = B_1\sqcup B_2$.
For existence of $F$, it is necessary that $A_1\cap B_2=A_2\cap B_1=\emptyset$.
Let $C_1 := A_1 \cap B_1$ and $C_2 := A_2\cap B_2$. Then define $A_1^\star := A_1\setminus C_1$, $A_2^\star := A_2\setminus C_2$, $B_1^\star := B_1\setminus C_1$, $B_2^\star := B_2\setminus C_2$.
From the definition it follows that the sets $A_1^\star, A_2^\star, B_1^\star, B_2^\star, C_1, C_2$ are pairwise disjoint. Furthermore,
$$A=A_1^\star \sqcup A_2^\star \sqcup C_1 \sqcup C_2,$$
$$B=B_1^\star \sqcup B_2^\star \sqcup C_1 \sqcup C_2.$$
The properties of $F$ imply that $F(A_1^\star)=B_1^\star$, $F(B_1^\star)=A_1^\star$, $F(A_2^\star)=B_2^\star$, $F(B_2^\star)=A_2^\star$, $F(C_1)=C_1$, and $F(C_2)=C_2$. Other than that $F$ can be an arbitrary involution.
involution. In particular, we can take $F$ to be the identity on $C_1\cup C_2$.
UPDATE. Since we are given that $\left.F\right_{A_1\cup B_1} = G$, we only need to define $F$ on $A_2\cup B_2$. In particular, we can take $F$ to be the identity on $C_2$.
From this consideration, it's easy to construct a particular $F$.
Here us a sample code:
def construct_F_fixed_num( L1, LL1, L2, LL2, num ):
A = { tuple(q) for q,n in L1 if n==num }
A1 = { tuple(q) for q,n in LL1 if n==num }
A2 = A - A1
B = { tuple(q) for q,n in L2 if n==num }
B1 = { tuple(q) for q,n in LL2 if n==num }
B2 = B - B1
assert len(A1 & B2) == 0
assert len(A2 & B1) == 0
C1 #C1 = A1 & B1
C2 = A2 & B2
A1s #A1s = A1 - C1
A2s = A2 - C2
B1s #B1s = B1 - C1
B2s = B2 - C2
assert #assert len(A1s) == len(B1s)
assert len(A2s) == len(B2s)
C = C1 | C2
# conversion for output
A2l = [[list(q),num] for q in A2s]
B2l = [[list(q),num] for q in B2s]
C2l = [[list(q),num] for q in C2]
return list( zip(C,C,[num]*len(C)) ) [list(t) for t in zip(C2l,C2l)] + list( zip(A1s,B1s,[num]*len(A1s)) ) + list( zip(A2s,B2s,[num]*len(A2s)) )
[list(t) for t in zip(A2l,B2l)]
def construct_F( L1, LL1, L2, LL2 LL2, G ):
N = { n for _,n in L1+L2 }
return sum( (construct_F_fixed_num( [construct_F_fixed_num( L1, LL1, L2, LL2, n ) for n in N), [] N], G )
Running construct_F( L1, LL1, L2, on the lists from your first example returns:LL2 LL2, G )
[((4, [[[[2, 2, 2, 1], 4], [[4, 3, 2, 1), (2, 2, 2, 1), 2),
((2, 1], 4]],
[[[3, 2, 2, 1], 3], [[2, 3, 2, 1), (2, 1], 3]],
[[[2, 3, 2, 1), 3),
((3, 2, 2, 1), (3, 2, 2, 1), 3),
((3, 1], 3], [[3, 2, 2, 1], 3]],
[[[4, 3, 2, 1), (3, 1], 2], [[2, 2, 2, 1], 2]],
[[[3, 3, 2, 1), 3),
((2, 2, 2, 1), (4, 1], 3], [[3, 3, 2, 1), 4)]
1], 3]]]
This
As for the number of different involutions $F$, it equals $$|A_2|!\cdot \iota(|C_2|),$$ where $\iota(\cdot)$
is| | 10 | No.10 Revision |
Since $F$ must preserve the number, it's worth to decompose the problem into smaller subproblems, where the number is fixed. E.g., in the first example, you'd have 3 subproblems with number being 2, 3, and 4, respectively.
Let's consider such a subproblem, where the number is fixed.
Let $A$ be a set of elements from L1, and $A_1$ be the set of elements from LL1. Denote $A_2:=A\setminus A_1$, so that $A = A_1\sqcup A_2$.
Similarly, let $B$ be the set of elements from L2, and $B_1$ be the set of elements from LL2. Denote $B_2:=B\setminus B_1$, so that $B = B_1\sqcup B_2$.
For existence of $F$, it is necessary that $A_1\cap B_2=A_2\cap B_1=\emptyset$.
Let $C_1 := A_1 \cap B_1$ and $C_2 := A_2\cap B_2$. Then define $A_1^\star := A_1\setminus C_1$, $A_2^\star := A_2\setminus C_2$, $B_1^\star := B_1\setminus C_1$, $B_2^\star := B_2\setminus C_2$.
From the definition it follows that the sets $A_1^\star, A_2^\star, B_1^\star, B_2^\star, C_1, C_2$ are pairwise disjoint. Furthermore,
$$A=A_1^\star \sqcup A_2^\star \sqcup C_1 \sqcup C_2,$$
$$B=B_1^\star \sqcup B_2^\star \sqcup C_1 \sqcup C_2.$$
The properties of $F$ imply that $F(A_1^\star)=B_1^\star$, $F(B_1^\star)=A_1^\star$, $F(A_2^\star)=B_2^\star$, $F(B_2^\star)=A_2^\star$, $F(C_1)=C_1$, and $F(C_2)=C_2$. Other than that $F$ can be an arbitrary involution. In particular, we can take $F$ to be the identity on $C_1\cup C_2$.
UPDATE. Since we are given that $\left.F\right_{A_1\cup B_1} = G$, we only need to define $F$ on $A_2\cup B_2$. In particular, we can take $F$ to be the identity on $C_2$.
From this consideration, it's easy to construct a particular $F$.
Here us a sample code:
def construct_F_fixed_num( L1, LL1, L2, LL2, num ):
A = { tuple(q) for q,n in L1 if n==num }
A1 = { tuple(q) for q,n in LL1 if n==num }
A2 = A - A1
B = { tuple(q) for q,n in L2 if n==num }
B1 = { tuple(q) for q,n in LL2 if n==num }
B2 = B - B1
assert len(A1 & B2) == 0
assert len(A2 & B1) == 0
#C1 = A1 & B1
C2 = A2 & B2
#A1s = A1 - C1
A2s = A2 - C2
#B1s = B1 - C1
B2s = B2 - C2
#assert len(A1s) == len(B1s)
assert len(A2s) == len(B2s)
# conversion for output
A2l = [[list(q),num] for q in A2s]
B2l = [[list(q),num] for q in B2s]
C2l = [[list(q),num] for q in C2]
return [list(t) for t in zip(C2l,C2l)] + [list(t) for t in zip(A2l,B2l)]
def construct_F( L1, LL1, L2, LL2, G ):
N = { n for _,n in L1+L2 }
return sum( [construct_F_fixed_num( L1, LL1, L2, LL2, n ) for n in N], G )
Running construct_F( L1, LL1, L2, LL2, G ) on the lists from your first example returns:
[[[[2, 2, 2, 1], 4], [[4, 3, 2, 1], 4]],
[[[3, 2, 2, 1], 3], [[2, 3, 2, 1], 3]],
[[[2, 3, 2, 1], 3], [[3, 2, 2, 1], 3]],
[[[4, 3, 2, 1], 2], [[2, 2, 2, 1], 2]],
[[[3, 3, 2, 1], 3], [[3, 3, 2, 1], 3]]]
As for the number of different involutions $F$, it equals $$|A_2|!\cdot \iota(|C_2|),$$ where $\iota(\cdot)$ is the involution number given by OEIS A000085. The factor $|A_2|!$ accounts for bijections between on $A_2^\star$ and $B_2^\star$, while $\iota(|C_2|)$ accounts for involutions on $C_2$.
| | 11 | No.11 Revision |
Since $F$ must preserve the number, it's worth to decompose the problem into smaller subproblems, where the number is fixed. E.g., in the first example, you'd have 3 subproblems with number being 2, 3, and 4, respectively.
Let's consider such a subproblem, where the number is fixed.
Let $A$ be a set of elements from L1, and $A_1$ be the set of elements from LL1. Denote $A_2:=A\setminus A_1$, so that $A = A_1\sqcup A_2$.
Similarly, let $B$ be the set of elements from L2, and $B_1$ be the set of elements from LL2. Denote $B_2:=B\setminus B_1$, so that $B = B_1\sqcup B_2$.
For existence of $F$, it is necessary that $A_1\cap B_2=A_2\cap B_1=\emptyset$.
Let $C_1 := A_1 \cap B_1$ and $C_2 := A_2\cap B_2$. Then define $A_1^\star := A_1\setminus C_1$, $A_2^\star := A_2\setminus C_2$, $B_1^\star := B_1\setminus C_1$, $B_2^\star := B_2\setminus C_2$.
From the definition it follows that the sets $A_1^\star, A_2^\star, B_1^\star, B_2^\star, C_1, C_2$ are pairwise disjoint. Furthermore,
$$A=A_1^\star \sqcup A_2^\star \sqcup C_1 \sqcup C_2,$$
$$B=B_1^\star \sqcup B_2^\star \sqcup C_1 \sqcup C_2.$$
The properties of $F$ imply that $F(A_1^\star)=B_1^\star$, $F(B_1^\star)=A_1^\star$, $F(A_2^\star)=B_2^\star$, $F(B_2^\star)=A_2^\star$, $F(C_1)=C_1$, and $F(C_2)=C_2$. Other than that $F$ can be an arbitrary involution. In particular, we can take $F$ to be the identity on $C_1\cup C_2$.
UPDATE. Since we are given that $\left.F\right_{A_1\cup $\left.F\right|_{A_1\cup B_1} = G$, we only need to define $F$ on $A_2\cup B_2$. In particular, we can take $F$ to be the identity on $C_2$.
From this consideration, it's easy to construct a particular $F$.
Here us a sample code:
def construct_F_fixed_num( L1, LL1, L2, LL2, num ):
A = { tuple(q) for q,n in L1 if n==num }
A1 = { tuple(q) for q,n in LL1 if n==num }
A2 = A - A1
B = { tuple(q) for q,n in L2 if n==num }
B1 = { tuple(q) for q,n in LL2 if n==num }
B2 = B - B1
assert len(A1 & B2) == 0
assert len(A2 & B1) == 0
#C1 = A1 & B1
C2 = A2 & B2
#A1s = A1 - C1
A2s = A2 - C2
#B1s = B1 - C1
B2s = B2 - C2
#assert len(A1s) == len(B1s)
assert len(A2s) == len(B2s)
# conversion for output
A2l = [[list(q),num] for q in A2s]
B2l = [[list(q),num] for q in B2s]
C2l = [[list(q),num] for q in C2]
return [list(t) for t in zip(C2l,C2l)] + [list(t) for t in zip(A2l,B2l)]
def construct_F( L1, LL1, L2, LL2, G ):
N = { n for _,n in L1+L2 }
return sum( [construct_F_fixed_num( L1, LL1, L2, LL2, n ) for n in N], G )
Running construct_F( L1, LL1, L2, LL2, G ) on the lists from your first example returns:
[[[[2, 2, 2, 1], 4], [[4, 3, 2, 1], 4]],
[[[3, 2, 2, 1], 3], [[2, 3, 2, 1], 3]],
[[[2, 3, 2, 1], 3], [[3, 2, 2, 1], 3]],
[[[4, 3, 2, 1], 2], [[2, 2, 2, 1], 2]],
[[[3, 3, 2, 1], 3], [[3, 3, 2, 1], 3]]]
As for the number of different involutions $F$, it equals $$|A_2|!\cdot \iota(|C_2|),$$ where $\iota(\cdot)$ is the involution number given by OEIS A000085. The factor $|A_2|!$ accounts for bijections between on $A_2^\star$ and $B_2^\star$, while $\iota(|C_2|)$ accounts for involutions on $C_2$.
| | 12 | No.12 Revision |
Since $F$ must preserve the number, it's worth to decompose the problem into smaller subproblems, where the number is fixed. E.g., in the first example, you'd have 3 subproblems with number being 2, 3, and 4, respectively.
Let's consider such a subproblem, where the number is fixed.
Let $A$ be a set of elements from L1, and $A_1$ be the set of elements from LL1. Denote $A_2:=A\setminus A_1$, so that $A = A_1\sqcup A_2$.
Similarly, let $B$ be the set of elements from L2, and $B_1$ be the set of elements from LL2. Denote $B_2:=B\setminus B_1$, so that $B = B_1\sqcup B_2$.
For existence of $F$, it is necessary that $A_1\cap B_2=A_2\cap B_1=\emptyset$.
Let $C_1 := A_1 \cap B_1$ and $C_2 := A_2\cap B_2$. Then define $A_1^\star := A_1\setminus C_1$, $A_2^\star := A_2\setminus C_2$, $B_1^\star := B_1\setminus C_1$, $B_2^\star := B_2\setminus C_2$.
From the definition it follows that the sets $A_1^\star, A_2^\star, B_1^\star, B_2^\star, C_1, C_2$ are pairwise disjoint. Furthermore,
$$A=A_1^\star \sqcup A_2^\star \sqcup C_1 \sqcup C_2,$$
$$B=B_1^\star \sqcup B_2^\star \sqcup C_1 \sqcup C_2.$$
The properties of $F$ imply that $F(A_1^\star)=B_1^\star$, $F(B_1^\star)=A_1^\star$, $F(A_2^\star)=B_2^\star$, $F(B_2^\star)=A_2^\star$, $F(C_1)=C_1$, and $F(C_2)=C_2$. Other than that $F$ can be an arbitrary involution. In particular, we can take $F$ to be the identity on $C_1\cup C_2$.
UPDATE. Since we are given that $\left.F\right|_{A_1\cup B_1} = G$, we only need to define $F$ on $A_2\cup B_2$. In particular, we can take $F$ to be the identity on $C_2$.
From this consideration, it's easy to construct a particular $F$.
Here us a sample code:
def construct_F_fixed_num( L1, LL1, L2, LL2, num ):
A = { tuple(q) for q,n in L1 if n==num }
A1 = { tuple(q) for q,n in LL1 if n==num }
A2 = A - A1
B = { tuple(q) for q,n in L2 if n==num }
B1 = { tuple(q) for q,n in LL2 if n==num }
B2 = B - B1
assert len(A1 & B2) == 0
assert len(A2 & B1) == 0
#C1 = A1 & B1
C2 = A2 & B2
#A1s = A1 - C1
A2s = A2 - C2
#B1s = B1 - C1
B2s = B2 - C2
#assert len(A1s) == len(B1s)
assert len(A2s) == len(B2s)
# conversion for output
A2l = [[list(q),num] for q in A2s]
B2l = [[list(q),num] for q in B2s]
C2l = [[list(q),num] for q in C2]
return [list(t) for t in zip(C2l,C2l)] + [list(t) for t in zip(A2l,B2l)]
def construct_F( L1, LL1, L2, LL2, G ):
N = { n for _,n in L1+L2 }
return sum( [construct_F_fixed_num( L1, LL1, L2, LL2, n ) for n in N], G )
Running construct_F( L1, LL1, L2, LL2, G ) on the lists from your first example returns:
[[[[2, 2, 2, 1], 4], [[4, 3, 2, 1], 4]],
[[[3, 2, 2, 1], 3], [[2, 3, 2, 1], 3]],
[[[2, 3, 2, 1], 3], [[3, 2, 2, 1], 3]],
[[[4, 3, 2, 1], 2], [[2, 2, 2, 1], 2]],
[[[3, 3, 2, 1], 3], [[3, 3, 2, 1], 3]]]
As for the number of different involutions $F$, it equals
$$|A_2|!\cdot $$|A_2^\star|!\cdot \iota(|C_2|),$$
where $\iota(\cdot)$ is the involution number given by OEIS A000085. The factor $|A_2|!$ $|A_2^\star|!$ accounts for bijections between on $A_2^\star$ and $B_2^\star$, while $\iota(|C_2|)$ accounts for involutions on $C_2$.
| | 13 | No.13 Revision |
Since $F$ must preserve the number, it's worth to decompose the problem into smaller subproblems, where the number is fixed. E.g., in the first example, you'd have 3 subproblems with number being 2, 3, and 4, respectively.
Let's consider such a subproblem, where the number is fixed.
Let $A$ be a set of elements from L1, and $A_1$ be the set of elements from LL1. Denote $A_2:=A\setminus A_1$, so that $A = A_1\sqcup A_2$.
Similarly, let $B$ be the set of elements from L2, and $B_1$ be the set of elements from LL2. Denote $B_2:=B\setminus B_1$, so that $B = B_1\sqcup B_2$.
For existence of $F$, it is necessary that $A_1\cap B_2=A_2\cap B_1=\emptyset$.
Let $C_1 := A_1 \cap B_1$ and $C_2 := A_2\cap B_2$. Then define $A_1^\star := A_1\setminus C_1$, $A_2^\star := A_2\setminus C_2$, $B_1^\star := B_1\setminus C_1$, $B_2^\star := B_2\setminus C_2$.
From the definition it follows that the sets $A_1^\star, A_2^\star, B_1^\star, B_2^\star, C_1, C_2$ are pairwise disjoint. Furthermore,
$$A=A_1^\star \sqcup A_2^\star \sqcup C_1 \sqcup C_2,$$
$$B=B_1^\star \sqcup B_2^\star \sqcup C_1 \sqcup C_2.$$
The properties of $F$ imply that $F(A_1^\star)=B_1^\star$, $F(B_1^\star)=A_1^\star$, $F(A_2^\star)=B_2^\star$, $F(B_2^\star)=A_2^\star$, $F(C_1)=C_1$, and $F(C_2)=C_2$. Other than that $F$ can be an arbitrary involution. In particular, we can take $F$ to be the identity on $C_1\cup C_2$.
UPDATE. Since we are given that $\left.F\right|_{A_1\cup B_1} = G$, we only need to define $F$ on $A_2\cup B_2$. B_2 = A_2^\star \sqcup B_2^\star \sqcup C_2$. In particular, we can take $F$ to be the identity on $C_2$.
From this consideration, it's easy to construct a particular $F$.
Here us a sample code:
def construct_F_fixed_num( L1, LL1, L2, LL2, num ):
A = { tuple(q) for q,n in L1 if n==num }
A1 = { tuple(q) for q,n in LL1 if n==num }
A2 = A - A1
B = { tuple(q) for q,n in L2 if n==num }
B1 = { tuple(q) for q,n in LL2 if n==num }
B2 = B - B1
assert len(A1 & B2) == 0
assert len(A2 & B1) == 0
#C1 = A1 & B1
C2 = A2 & B2
#A1s = A1 - C1
A2s = A2 - C2
#B1s = B1 - C1
B2s = B2 - C2
#assert len(A1s) == len(B1s)
assert len(A2s) == len(B2s)
# conversion for output
A2l = [[list(q),num] for q in A2s]
B2l = [[list(q),num] for q in B2s]
C2l = [[list(q),num] for q in C2]
return [list(t) for t in zip(C2l,C2l)] + [list(t) for t in zip(A2l,B2l)]
def construct_F( L1, LL1, L2, LL2, G ):
N = { n for _,n in L1+L2 }
return sum( [construct_F_fixed_num( L1, LL1, L2, LL2, n ) for n in N], G )
Running construct_F( L1, LL1, L2, LL2, G ) on the lists from your first example returns:
[[[[2, 2, 2, 1], 4], [[4, 3, 2, 1], 4]],
[[[3, 2, 2, 1], 3], [[2, 3, 2, 1], 3]],
[[[2, 3, 2, 1], 3], [[3, 2, 2, 1], 3]],
[[[4, 3, 2, 1], 2], [[2, 2, 2, 1], 2]],
[[[3, 3, 2, 1], 3], [[3, 3, 2, 1], 3]]]
As for the number of different involutions $F$, it equals $$|A_2^\star|!\cdot \iota(|C_2|),$$ where $\iota(\cdot)$ is the involution number given by OEIS A000085. The factor $|A_2^\star|!$ accounts for bijections between on $A_2^\star$ and $B_2^\star$, while $\iota(|C_2|)$ accounts for involutions on $C_2$.
