mpmp8 stackfolding

README.md

This gist describes my solution to Matt Parker's puzzle #8:

• http://think-maths.co.uk/foldingchallenge
• https://www.youtube.com/watch?v=GpClxF41ugg

My solution involves looking at the pattern of folds when viewing the folded stack from the sides. And then using some python code to generate all possible ways the folds can match up in a way that you will still end up with two rows of 4 sheets.

The list below shows all ways to fold a piece of paper, including ways where the top-left ends up on the inside of the folded stack.

Here I made some ascii drawings for the examples Matt showed in his video:

---------
 A D E H
 B C F G
---------

view from bottom      view from left
    -A----\                 -A--\
    -B--\ |                 -B--/
/----C--/ |                 -C--\  
| /--D----/                 -D--/  
| \--E----\                 -E--\  
\----F--\ |                 -F--/  
    -G--/ |                 -G--\  
    -H----/                 -H--/  


---------
 A H G D
 B C F E
---------

view from bottom      view from left
  -A------\               -A--\
  -B--\   |               -B--/
/--C--/   |               -C----\
| -D----\ |               -D--\ |
| -E--\ | |               -E--/ |
\--F--/ | |               -F--\ |
/--G----/ |               -G--/ |
\--H------/               -H----/


---------
 A H B G
 D E C F
---------

 view from bottom      view from left
    -A--------\          -A----\
/----B------\ |          -B--\ |
| /--C----\ | |          -C--/ | 
| | -D--\ | | |          -D----/
| \--E--/ | | |          -E----\ 
|   -F----/ | |          -F--\ | 
|   -G------/ |          -G--/ | 
\----H--------/          -H----/ 

This is a list of all ways to pair up sheets, and still have a valid folding.

40 with the 'A' on one of the outer corners of the sheet.

(AD, BC, EH, FG) (CF, DE) --> (AB, CD, EF, GH)    (A, D, E, H) (B, C, F, G)    << #0      
(AH, BC, DG, EF) (CF, GH) --> (AB, CH, DE, FG)    (E, F, C, B) (D, G, H, A)    << #1      
(AH, BG, CF, DE) (BH, CE) --> (AD, BC, EH, FG)    (D, E, C, F) (A, H, B, G)    << #2      
(AB, CH, DG, EF) (BE, CD) --> (AH, BC, DE, FG)    (A, B, E, F) (H, C, D, G)               
(AB, CH, DE, FG) (BG, CD) --> (AH, BC, DG, EF)    (A, B, G, F) (H, C, D, E)               
(AB, CH, DE, FG) (BF, CE) --> (AH, BC, DG, EF)    (A, B, F, G) (H, C, E, D)               
(AB, CD, EH, FG) (BF, CE) --> (AD, BC, EF, GH)    (A, B, F, G) (D, C, E, H)               
(AB, CD, EF, GH) (BH, CE) --> (AD, BC, EH, FG)    (D, C, E, F) (A, B, H, G)               
(AB, CH, DG, EF) (BG, CF) --> (AH, BC, DE, FG)    (E, F, C, H) (D, G, B, A)               
(AF, BE, CD, GH) (BG, CF) --> (AH, BC, DE, FG)    (A, F, C, D) (H, G, B, E)               
(AB, CD, EF, GH) (BG, CF) --> (AD, BC, EH, FG)    (D, C, F, E) (A, B, G, H)               
(AH, BE, CD, FG) (BH, CG) --> (AF, BC, DE, GH)    (D, C, G, F) (E, B, H, A)               
(AB, CD, EH, FG) (BH, CG) --> (AD, BC, EF, GH)    (D, C, G, F) (A, B, H, E)               
(AB, CH, DG, EF) (BC, DE) --> (AF, BE, CD, GH)    (F, E, D, G) (A, B, C, H)               
(AB, CF, DE, GH) (BC, DG) --> (AH, BG, CD, EF)    (H, G, D, E) (A, B, C, F)               
(AB, CD, EF, GH) (BC, FG) --> (AH, BG, CF, DE)    (H, G, F, E) (A, B, C, D)               
(AF, BC, DE, GH) (BG, EF) --> (AH, BE, CD, FG)    (A, F, E, D) (H, G, B, C)               
(AB, CH, DG, EF) (BH, EG) --> (AF, BE, CD, GH)    (D, G, E, F) (C, H, B, A)               
(AH, BC, DE, FG) (BH, EG) --> (AF, BE, CD, GH)    (D, E, G, F) (C, B, H, A)               
(AB, CD, EF, GH) (BD, EG) --> (AH, BG, CF, DE)    (C, D, B, A) (F, E, G, H)               
(AD, BC, EH, FG) (BD, EG) --> (AH, BG, CF, DE)    (A, D, B, C) (H, E, G, F)               
(AB, CF, DE, GH) (BE, FG) --> (AH, BG, CD, EF)    (D, E, B, A) (C, F, G, H)               
(AD, BC, EF, GH) (CH, DE) --> (AB, CD, EH, FG)    (B, C, H, G) (A, D, E, F)               
(AF, BC, DE, GH) (CG, DF) --> (AH, BE, CD, FG)    (A, F, D, E) (H, G, C, B)               
(AD, BC, EF, GH) (CG, DF) --> (AB, CD, EH, FG)    (A, D, F, E) (B, C, G, H)               
(AH, BC, DE, FG) (CH, DG) --> (AF, BE, CD, GH)    (E, D, G, F) (B, C, H, A)               
(AD, BC, EH, FG) (CH, DG) --> (AB, CD, EF, GH)    (A, D, G, F) (B, C, H, E)               
(AH, BG, CF, DE) (CH, DG) --> (AB, CD, EF, GH)    (B, G, D, E) (A, H, C, F)               
(AD, BC, EH, FG) (CD, EF) --> (AH, BG, CF, DE)    (G, F, E, H) (B, C, D, A)               
(AH, BC, DG, EF) (CD, EH) --> (AB, CH, DE, FG)    (A, H, E, F) (B, C, D, G)               
(AH, BC, DE, FG) (CD, GH) --> (AB, CH, DG, EF)    (A, H, G, F) (B, C, D, E)               
(AH, BG, CD, EF) (CH, FG) --> (AB, CF, DE, GH)    (A, H, C, D) (B, G, F, E)               
(AF, BE, CD, GH) (CE, FH) --> (AB, CH, DG, EF)    (G, H, F, A) (D, C, E, B)               
(AH, BC, DE, FG) (CE, FH) --> (AB, CH, DG, EF)    (A, H, F, G) (B, C, E, D)               
(AF, BE, CD, GH) (DG, EF) --> (AH, BC, DE, FG)    (C, D, G, H) (B, E, F, A)               
(AH, BE, CD, FG) (DH, EG) --> (AF, BC, DE, GH)    (B, E, G, F) (C, D, H, A)               
(AH, BG, CD, EF) (DH, EG) --> (AB, CF, DE, GH)    (B, G, E, F) (A, H, D, C)               
(AF, BE, CD, GH) (DE, FG) --> (AB, CH, DG, EF)    (B, E, D, C) (A, F, G, H)               
(AH, BG, CF, DE) (EH, FG) --> (AB, CD, EF, GH)    (A, H, E, D) (B, G, F, C)               
(AH, BG, CF, DE) (EF, GH) --> (AD, BC, EH, FG)    (C, F, E, D) (B, G, H, A)               

40 with the 'A' somewhere in the center squares.

(AH, BG, CF, DE) (AD, BC) --> (AB, CD, EF, GH)    (E, D, A, H) (F, C, B, G)               
(AH, BG, CD, EF) (AF, BC) --> (AB, CF, DE, GH)    (E, F, A, H) (D, C, B, G)               
(AF, BE, CD, GH) (AH, BC) --> (AB, CH, DG, EF)    (D, C, B, E) (G, H, A, F)               
(AH, BC, DG, EF) (AE, BD) --> (AB, CH, DE, FG)    (F, E, A, H) (G, D, B, C)               
(AH, BG, CD, EF) (AE, BD) --> (AB, CF, DE, GH)    (F, E, A, H) (C, D, B, G)               
(AF, BE, CD, GH) (AG, BD) --> (AB, CH, DG, EF)    (F, A, G, H) (E, B, D, C)               
(AH, BC, DE, FG) (AG, BD) --> (AB, CH, DG, EF)    (F, G, A, H) (E, D, B, C)               
(AH, BC, DE, FG) (AF, BE) --> (AB, CH, DG, EF)    (G, F, A, H) (D, E, B, C)               
(AD, BC, EH, FG) (AF, BE) --> (AB, CD, EF, GH)    (D, A, F, G) (C, B, E, H)               
(AH, BG, CF, DE) (AF, BE) --> (AB, CD, EF, GH)    (C, F, A, H) (D, E, B, G)               
(AD, BC, EF, GH) (AH, BE) --> (AB, CD, EH, FG)    (C, B, E, F) (D, A, H, G)               
(AH, BC, DG, EF) (AG, BF) --> (AB, CH, DE, FG)    (C, B, F, E) (H, A, G, D)               
(AD, BC, EF, GH) (AG, BF) --> (AB, CD, EH, FG)    (C, B, F, E) (D, A, G, H)               
(AD, BC, EH, FG) (AH, BG) --> (AB, CD, EF, GH)    (C, B, G, F) (D, A, H, E)               
(AH, BG, CF, DE) (AB, CD) --> (AD, BC, EH, FG)    (E, D, C, F) (H, A, B, G)               
(AH, BE, CD, FG) (AB, CF) --> (AF, BC, DE, GH)    (G, F, C, D) (H, A, B, E)               
(AF, BE, CD, GH) (AB, CH) --> (AH, BC, DE, FG)    (G, H, C, D) (F, A, B, E)               
(AH, BC, DE, FG) (AB, EF) --> (AF, BE, CD, GH)    (G, F, E, D) (H, A, B, C)               
(AF, BC, DE, GH) (AB, EH) --> (AH, BE, CD, FG)    (G, H, E, D) (F, A, B, C)               
(AD, BC, EH, FG) (AB, GH) --> (AH, BG, CF, DE)    (E, H, G, F) (D, A, B, C)               
(AB, CD, EH, FG) (AF, DE) --> (AD, BC, EF, GH)    (B, A, F, G) (C, D, E, H)               
(AB, CD, EF, GH) (AH, DE) --> (AD, BC, EH, FG)    (C, D, E, F) (B, A, H, G)               
(AB, CD, EF, GH) (AG, DF) --> (AD, BC, EH, FG)    (B, A, G, H) (C, D, F, E)               
(AH, BG, CF, DE) (AG, DF) --> (AD, BC, EH, FG)    (B, G, A, H) (C, F, D, E)               
(AB, CD, EH, FG) (AH, DG) --> (AD, BC, EF, GH)    (C, D, G, F) (B, A, H, E)               
(AB, CH, DG, EF) (AC, DF) --> (AF, BE, CD, GH)    (E, F, D, G) (B, A, C, H)               
(AH, BC, DE, FG) (AC, DF) --> (AF, BE, CD, GH)    (G, F, D, E) (H, A, C, B)               
(AB, CF, DE, GH) (AC, DH) --> (AH, BG, CD, EF)    (F, C, A, B) (E, D, H, G)               
(AF, BC, DE, GH) (AC, DH) --> (AH, BE, CD, FG)    (B, C, A, F) (E, D, H, G)               
(AB, CD, EF, GH) (AC, FH) --> (AH, BG, CF, DE)    (G, H, F, E) (B, A, C, D)               
(AD, BC, EH, FG) (AC, FH) --> (AH, BG, CF, DE)    (E, H, F, G) (D, A, C, B)               
(AH, BE, CD, FG) (AD, EF) --> (AF, BC, DE, GH)    (C, D, A, H) (B, E, F, G)               
(AB, CD, EF, GH) (AD, EH) --> (AH, BG, CF, DE)    (G, H, E, F) (B, A, D, C)               
(AB, CH, DG, EF) (AD, EH) --> (AH, BC, DE, FG)    (C, H, E, F) (B, A, D, G)               
(AF, BE, CD, GH) (AD, EH) --> (AH, BC, DE, FG)    (G, H, E, B) (F, A, D, C)               
(AB, CH, DE, FG) (AD, GH) --> (AH, BC, DG, EF)    (E, D, A, B) (F, G, H, C)               
(AB, CH, DG, EF) (AH, FG) --> (AF, BE, CD, GH)    (D, G, F, E) (C, H, A, B)               
(AB, CF, DE, GH) (AE, FH) --> (AH, BG, CD, EF)    (G, H, F, C) (B, A, E, D)               
(AB, CH, DE, FG) (AE, FH) --> (AH, BC, DG, EF)    (C, H, F, G) (B, A, E, D)               
(AB, CH, DG, EF) (AF, GH) --> (AH, BC, DE, FG)    (E, F, A, B) (D, G, H, C)               

Here in a slightly different notation, using brackets to indicate which sheets are connected together.

40 with the 'A' on one of the outer corners of the sheet.

<(A(BC)D)(E(FG)H)> + <AB(C(DE)F)GH> -> <(AB)(CD)(EF)(GH)>    << #0      
<(A(BC)(D(EF)G)H)> + <AB(CDEF)(GH)> -> <(AB)(C(DE)(FG)H)>    << #1      
<(A(B(C(DE)F)G)H)> + <A(B(CDE)FGH)> -> <(A(BC)D)(E(FG)H)>    << #2      
<(AB)(C(D(EF)G)H)> + <A(B(CD)E)FGH> -> <(A(BC)(DE)(FG)H)>
<(AB)(C(DE)(FG)H)> + <A(B(CD)EFG)H> -> <(A(BC)(D(EF)G)H)>
<(AB)(C(DE)(FG)H)> + <A(B(CDE)F)GH> -> <(A(BC)(D(EF)G)H)>
<(AB)(CD)(E(FG)H)> + <A(B(CDE)F)GH> -> <(A(BC)D)(EF)(GH)>
<(AB)(CD)(EF)(GH)> + <A(B(CDE)FGH)> -> <(A(BC)D)(E(FG)H)>
<(AB)(C(D(EF)G)H)> + <A(B(CDEF)G)H> -> <(A(BC)(DE)(FG)H)>
<(A(B(CD)E)F)(GH)> + <A(B(CDEF)G)H> -> <(A(BC)(DE)(FG)H)>
<(AB)(CD)(EF)(GH)> + <A(B(CDEF)G)H> -> <(A(BC)D)(E(FG)H)>
<(A(B(CD)E)(FG)H)> + <A(B(CDEFG)H)> -> <(A(BC)(DE)F)(GH)>
<(AB)(CD)(E(FG)H)> + <A(B(CDEFG)H)> -> <(A(BC)D)(EF)(GH)>
<(AB)(C(D(EF)G)H)> + <A(BC)(DE)FGH> -> <(A(B(CD)E)F)(GH)>
<(AB)(C(DE)F)(GH)> + <A(BC)(DEFG)H> -> <(A(B(CD)(EF)G)H)>
<(AB)(CD)(EF)(GH)> + <A(BC)DE(FG)H> -> <(A(B(C(DE)F)G)H)>
<(A(BC)(DE)F)(GH)> + <A(BCD(EF)G)H> -> <(A(B(CD)E)(FG)H)>
<(AB)(C(D(EF)G)H)> + <A(BCD(EFG)H)> -> <(A(B(CD)E)F)(GH)>
<(A(BC)(DE)(FG)H)> + <A(BCD(EFG)H)> -> <(A(B(CD)E)F)(GH)>
<(AB)(CD)(EF)(GH)> + <A(BCD)(EFG)H> -> <(A(B(C(DE)F)G)H)>
<(A(BC)D)(E(FG)H)> + <A(BCD)(EFG)H> -> <(A(B(C(DE)F)G)H)>
<(AB)(C(DE)F)(GH)> + <A(BCDE)(FG)H> -> <(A(B(CD)(EF)G)H)>
<(A(BC)D)(EF)(GH)> + <AB(C(DE)FGH)> -> <(AB)(CD)(E(FG)H)>
<(A(BC)(DE)F)(GH)> + <AB(C(DEF)G)H> -> <(A(B(CD)E)(FG)H)>
<(A(BC)D)(EF)(GH)> + <AB(C(DEF)G)H> -> <(AB)(CD)(E(FG)H)>
<(A(BC)(DE)(FG)H)> + <AB(C(DEFG)H)> -> <(A(B(CD)E)F)(GH)>
<(A(BC)D)(E(FG)H)> + <AB(C(DEFG)H)> -> <(AB)(CD)(EF)(GH)>
<(A(B(C(DE)F)G)H)> + <AB(C(DEFG)H)> -> <(AB)(CD)(EF)(GH)>
<(A(BC)D)(E(FG)H)> + <AB(CD)(EF)GH> -> <(A(B(C(DE)F)G)H)>
<(A(BC)(D(EF)G)H)> + <AB(CD)(EFGH)> -> <(AB)(C(DE)(FG)H)>
<(A(BC)(DE)(FG)H)> + <AB(CD)EF(GH)> -> <(AB)(C(D(EF)G)H)>
<(A(B(CD)(EF)G)H)> + <AB(CDE(FG)H)> -> <(AB)(C(DE)F)(GH)>
<(A(B(CD)E)F)(GH)> + <AB(CDE)(FGH)> -> <(AB)(C(D(EF)G)H)>
<(A(BC)(DE)(FG)H)> + <AB(CDE)(FGH)> -> <(AB)(C(D(EF)G)H)>
<(A(B(CD)E)F)(GH)> + <ABC(D(EF)G)H> -> <(A(BC)(DE)(FG)H)>
<(A(B(CD)E)(FG)H)> + <ABC(D(EFG)H)> -> <(A(BC)(DE)F)(GH)>
<(A(B(CD)(EF)G)H)> + <ABC(D(EFG)H)> -> <(AB)(C(DE)F)(GH)>
<(A(B(CD)E)F)(GH)> + <ABC(DE)(FG)H> -> <(AB)(C(D(EF)G)H)>
<(A(B(C(DE)F)G)H)> + <ABCD(E(FG)H)> -> <(AB)(CD)(EF)(GH)>
<(A(B(C(DE)F)G)H)> + <ABCD(EF)(GH)> -> <(A(BC)D)(E(FG)H)>

40 with the 'A' somewhere in the center squares.

<(A(B(C(DE)F)G)H)> + <(A(BC)D)EFGH> -> <(AB)(CD)(EF)(GH)>
<(A(B(CD)(EF)G)H)> + <(A(BC)DEF)GH> -> <(AB)(C(DE)F)(GH)>
<(A(B(CD)E)F)(GH)> + <(A(BC)DEFGH)> -> <(AB)(C(D(EF)G)H)>
<(A(BC)(D(EF)G)H)> + <(A(BCD)E)FGH> -> <(AB)(C(DE)(FG)H)>
<(A(B(CD)(EF)G)H)> + <(A(BCD)E)FGH> -> <(AB)(C(DE)F)(GH)>
<(A(B(CD)E)F)(GH)> + <(A(BCD)EFG)H> -> <(AB)(C(D(EF)G)H)>
<(A(BC)(DE)(FG)H)> + <(A(BCD)EFG)H> -> <(AB)(C(D(EF)G)H)>
<(A(BC)(DE)(FG)H)> + <(A(BCDE)F)GH> -> <(AB)(C(D(EF)G)H)>
<(A(BC)D)(E(FG)H)> + <(A(BCDE)F)GH> -> <(AB)(CD)(EF)(GH)>
<(A(B(C(DE)F)G)H)> + <(A(BCDE)F)GH> -> <(AB)(CD)(EF)(GH)>
<(A(BC)D)(EF)(GH)> + <(A(BCDE)FGH)> -> <(AB)(CD)(E(FG)H)>
<(A(BC)(D(EF)G)H)> + <(A(BCDEF)G)H> -> <(AB)(C(DE)(FG)H)>
<(A(BC)D)(EF)(GH)> + <(A(BCDEF)G)H> -> <(AB)(CD)(E(FG)H)>
<(A(BC)D)(E(FG)H)> + <(A(BCDEFG)H)> -> <(AB)(CD)(EF)(GH)>
<(A(B(C(DE)F)G)H)> + <(AB)(CD)EFGH> -> <(A(BC)D)(E(FG)H)>
<(A(B(CD)E)(FG)H)> + <(AB)(CDEF)GH> -> <(A(BC)(DE)F)(GH)>
<(A(B(CD)E)F)(GH)> + <(AB)(CDEFGH)> -> <(A(BC)(DE)(FG)H)>
<(A(BC)(DE)(FG)H)> + <(AB)CD(EF)GH> -> <(A(B(CD)E)F)(GH)>
<(A(BC)(DE)F)(GH)> + <(AB)CD(EFGH)> -> <(A(B(CD)E)(FG)H)>
<(A(BC)D)(E(FG)H)> + <(AB)CDEF(GH)> -> <(A(B(C(DE)F)G)H)>
<(AB)(CD)(E(FG)H)> + <(ABC(DE)F)GH> -> <(A(BC)D)(EF)(GH)>
<(AB)(CD)(EF)(GH)> + <(ABC(DE)FGH)> -> <(A(BC)D)(E(FG)H)>
<(AB)(CD)(EF)(GH)> + <(ABC(DEF)G)H> -> <(A(BC)D)(E(FG)H)>
<(A(B(C(DE)F)G)H)> + <(ABC(DEF)G)H> -> <(A(BC)D)(E(FG)H)>
<(AB)(CD)(E(FG)H)> + <(ABC(DEFG)H)> -> <(A(BC)D)(EF)(GH)>
<(AB)(C(D(EF)G)H)> + <(ABC)(DEF)GH> -> <(A(B(CD)E)F)(GH)>
<(A(BC)(DE)(FG)H)> + <(ABC)(DEF)GH> -> <(A(B(CD)E)F)(GH)>
<(AB)(C(DE)F)(GH)> + <(ABC)(DEFGH)> -> <(A(B(CD)(EF)G)H)>
<(A(BC)(DE)F)(GH)> + <(ABC)(DEFGH)> -> <(A(B(CD)E)(FG)H)>
<(AB)(CD)(EF)(GH)> + <(ABC)DE(FGH)> -> <(A(B(C(DE)F)G)H)>
<(A(BC)D)(E(FG)H)> + <(ABC)DE(FGH)> -> <(A(B(C(DE)F)G)H)>
<(A(B(CD)E)(FG)H)> + <(ABCD)(EF)GH> -> <(A(BC)(DE)F)(GH)>
<(AB)(CD)(EF)(GH)> + <(ABCD)(EFGH)> -> <(A(B(C(DE)F)G)H)>
<(AB)(C(D(EF)G)H)> + <(ABCD)(EFGH)> -> <(A(BC)(DE)(FG)H)>
<(A(B(CD)E)F)(GH)> + <(ABCD)(EFGH)> -> <(A(BC)(DE)(FG)H)>
<(AB)(C(DE)(FG)H)> + <(ABCD)EF(GH)> -> <(A(BC)(D(EF)G)H)>
<(AB)(C(D(EF)G)H)> + <(ABCDE(FG)H)> -> <(A(B(CD)E)F)(GH)>
<(AB)(C(DE)F)(GH)> + <(ABCDE)(FGH)> -> <(A(B(CD)(EF)G)H)>
<(AB)(C(DE)(FG)H)> + <(ABCDE)(FGH)> -> <(A(BC)(D(EF)G)H)>
<(AB)(C(D(EF)G)H)> + <(ABCDEF)(GH)> -> <(A(BC)(DE)(FG)H)>

foldpicking.py

from itertools import combinations, product
"""
Find all possible ways to fold an 4x2 sheet of paper.

example:

the unfolder paper
---------
 A H G D
 B C F E
---------

I do this by finding all possible ways to have the folds organised
on the various sides where the sheets are connected together.

         +---+
  left > |   |
  view > | A |
       > |   |
         +---+
          ^^^
        bottom view


view from bottom      view from left
    -A------\               -A--\
    -B--\   |               -B--/
  /--C--/   |               -C----\
  | -D----\ |               -D--\ |
  | -E--\ | |               -E--/ |
  \--F--/ | |               -F--\ |
  /--G----/ |               -G--/ |
  \--H------/               -H----/

  ^       ^                    ^
two     four                 four


Author: Willem Hengeveld <itsme@xs4all.nl>

"""


def genpairs(first, last):
    """
    generate all ways to pick pairs from the numbers in the range [first, last)

    This returns a list of sets of pairs.
    """
    results = []
    for a, b in combinations(range(first, last), 2):
        pair = {tuple(sorted((a,b)))}
        ranges = [[pair]]

        left = list(genpairs(first, a))
        if left: ranges.append(left)

        middle = list(genpairs(a+1, b))
        if middle: ranges.append(middle)

        right = list(genpairs(b+1, last))
        if right: ranges.append(right)

        for pairs in product(*ranges):
            yield set.union(*pairs)


def gentwofolds(n):
    """
    Generate all ways of connecting two pairs of sheets out of n
    """
    for pairs in set(map(frozenset, genpairs(0, n))):
        for a, b in combinations(pairs, 2):
            yield {a, b}


def genfourfolds(n):
    """
    Generate all ways of connecting four pairs of sheets out of n
    """
    for pairs in set(map(frozenset, genpairs(0, n))):
        if len(pairs)==n//2:
            yield pairs


def pickitemwith(pairs, x):
    """
    Find the first pair where one of the elements is 'x'.
    """
    for a, b in pairs:
        if a==x or b==x:
            return (a,b)


def findchains(a, b):
    """
    Piece the pairs together like dominoes.
    'b' contains only two pairs, 'a' contains 4 pairs,
    so the 'b' pair will be in the middle.
    """
    # no loops
    if set(a) & set(b):
        #print("have loop", a, b)
        return

    a = list(a)
    b = list(b)

    chains = []

    for _ in range(2):
        # start with center from 'b'
        y = b.pop()
        # find matching pairs from 'a'
        x = pickitemwith(a, y[0])
        if not x:
            #print("no dominoe in a for y0", a, b)
            return
        a.remove(x)

        # make sure order is ok.
        if x[0]==y[0]:
            x = x[::-1]

        z = pickitemwith(a, y[1])
        if not z:
            #print("no dominoe in a for y1", a, b)
            return
        a.remove(z)

        # make sure order is ok.
        if y[1] == z[1]:
            z = z[::-1]

        chains.append((x, y, z))

    if len(chains)==2 and len(a)==0 and len(b)==0:
        return chains
    print("?", len(chains), len(a), len(b))


def generatechains(fourfolds, twofolds):
    """
    go over all combinations of folds on the left and right.
    returning only this which result in two chains of 4 sheets.
    """
    def getchain(chain):
        return chain[0][0], chain[0][1], chain[1][1], chain[2][1]

    for a in fourfolds:
        for b in twofolds:
            chains = findchains(a, b)
            if chains:
                yield a, b, [getchain(_) for _ in chains]


def solutionsmatch(a, b):
    """
    Check if these solutions are equal when ordered properly.
    """
    a = sorted(sorted(pair) for pair in a)
    b = sorted(sorted(pair) for pair in b)
    return a == b

def isvalidfold(fold, fourfolds):
    for x in fourfolds:
        if solutionsmatch(x, fold):
            return True

def toalpha(x):
    """
    Attempt to pretty print my lists, tuples and sets.
    """
    def elem(x):
        return list(x)[0]
    def sortelem(x):
        return sorted(tuple(sorted(_)) for _ in x)
    if type(x) == tuple and len(x)==2 and type(x[0])==int:
        return "".join(toalpha(_) for _ in sorted(x))
    if type(x) in (frozenset, set, list, tuple):
        if type(elem(x)) == tuple:
            return "(" + ", ".join(toalpha(_) for _ in sortelem(x)) + ")"
        else:
            return "(" + ", ".join(toalpha(_) for _ in x) + ")"
    if type(x) == int:
        return chr(65+x)
    return "???"


def bracketed(n, pairs):
    """
    A different way of representing the folds, by bracketing sheets which are connected together.
    """
    txt = [ chr(65+(_//3)) if _%3==1 else '' for _ in range(n*3)]

    for a, b in pairs:
        if a>b: a, b = b, a
        txt[3*a] = '('
        txt[3*b+2] = ')'
    return "<"+"".join(txt)+">"


def main():

    """
    my 'n' is actually kind of fixed.

    Currently the 'generatechains', 'findchains' and 'main' functions are coded with
    the specific 4 x 2 shape in mind. This code is not easily modified to find solutions for
    differently shaped papers.
    """
    n = 8

    # first generate all unique 2 and 4 foldings
    twofolds = list(gentwofolds(n))
    fourfolds = list(genfourfolds(n))

    solutions = set()
    # now try to find chains in all combinations of a 'twofolds' and a 'fourfolds'
    for a, b, chains in generatechains(fourfolds, twofolds):
        c1 = chains[0]
        c2 = chains[1]

        # loop for trying c2 in two directions.
        for i in range(2):
            otherside = sorted((c,d) for c, d in zip(c1, c2))

            # now find which of the 'bottom' folds match.
            if isvalidfold(otherside, fourfolds):
                tag = "%s + %s -> %s" % (bracketed(n, a), bracketed(n, b), bracketed(n, otherside))
                if tag not in solutions:
                    solutions.add(tag)
                    print("%s %s --> %s    %s %s  ; %s" % (toalpha(a), toalpha(b), toalpha(otherside), toalpha(c1), toalpha(c2), tag))

            # reverse chain, and try again.
            c2 = c2[::-1]


if __name__ == '__main__':
    main()