% % http://www.iki.fi/~kartturi/matikka/Nekomorphisms/nrgatoms.txt % % % by Antti Karttunen, May 2003, http://www.iki.fi/~kartturi/ % % Some of the definitions & conditions are elaborated here % with the Prolog-code. % % This works with GNU prolog http://www.gnu.org/software/prolog % % Load as: % consult('c:\\matikka\\Nekomorphisms\\nrgatoms.txt'). % cons(CAR,CDR,[CAR|CDR]). %% Few examples of simple non-recursive gatomorphisms: %% 0 non-default clauses and 0 opening (closing) conses: a001477(X,X). %% Identity. % % A B --> B A % \ / \ / % X Y %% 1 non-default clause and 1 opening (closing) cons: a069770(X,Y) :- cons(A,B,X), % -- cons(B,A,Y), !. a069770(X,X). %% The default clause, fix S-exprs (here just []) the above clause could not handle. %% One non-default clause and two opening (closing) conses: % % B C A C % \ / \ / % A M --> B N % \ / \ / % X Y a072796(X,Y) :- cons(A,M,X), cons(B,C,M), % -- cons(A,C,N), cons(B,N,Y), !. a072796(X,X). %% Fix [] and S-exprs of length 1. % % C B C A % \ / \ / % M A --> N B % \ / \ / % X Y a072797(X,Y) :- cons(M,A,X), cons(C,B,M), % -- cons(C,A,N), cons(N,B,Y), !. a072797(X,X). %% Fix the rest. % % B C A B % \ / \ / % A M --> N C A [] --> [] A % \ / \ / \ / \ / % X Y X Y %% Two non-default clauses with 2 & 1 opening (closing) conses: a074679(X,Y) :- cons(A,M,X), cons(B,C,M), % -- cons(A,B,N), cons(N,C,Y), !. a074679(X,Y) :- cons(A,B,X), % B = [] by above clause. % -- cons(B,A,Y), !. a074679(X,X). %% Fix the rest. % % C B B A % \ / \ / % M A --> C N [] B --> B [] % \ / \ / \ / \ / % X Y X Y a074680(X,Y) :- cons(M,A,X), cons(C,B,M), % -- cons(B,A,N), cons(C,N,Y), !. % Above clause implies that A = []. a074680(X,Y) :- cons(A,B,X), % -- cons(B,A,Y), !. a074680(X,X). %% Fix the rest. %% %% (define (gmA082351! s) %% (cond ((not (pair? s)) s) %% ((not (pair? (car s))) s) %% ((not (pair? (cdr s))) (robl! (swap! s))) %% (else (robl! s)) %% ) %% ) %% %% (define (gmA082352! s) %% (cond ((not (pair? s)) s) %% ((not (pair? (car s))) s) %% ((not (pair? (caar s))) (swap! (robr! s))) %% (else (robr! s)) %% ) %% ) %% % A D % \ / % A D B C Q B A B [] A % \ / \ / \ / \ / \ / and by default: % P M --> N C M [] --> N B [] A [] A % \ / \ / \ / \ / \ / --> \ / % X Y X Y X Y %% Two non-default clauses with 3 & 2 = 5 opening (closing) conses: a082351(X,Y) :- cons(P,M,X), cons(A,D,P), cons(B,C,M), % -- cons(A,D,Q), %% Note: Q is equal to P. cons(Q,B,N), cons(N,C,Y), !. % Above clause implies that C=[]. a082351(X,Y) :- cons(M,C,X), cons(A,B,M), % -- cons(C,A,N), cons(N,B,Y), !. a082351(X,X). %% Fix the rest. % D C % \ / % P B D C B A [] B B A % \ / \ / \ / \ / \ / and by default: % M A --> Q N M A --> N [] [] A [] A % \ / \ / \ / \ / \ / --> \ / % X Y X Y X Y a082352(X,Y) :- cons(M,A,X), cons(P,B,M), cons(D,C,P), % -- cons(D,C,Q), % Note that Q is equal to P. cons(B,A,N), cons(Q,N,Y), !. a082352(X,Y) :- cons(M,A,X), cons(C,B,M), % -- cons(B,A,N), cons(N,C,Y), !. a082352(X,X). %% Fix the rest. %% %% We see that there are Cat(n)*(n+1)! (= A001813[n]) ways to form %% such gatomorphism of one non-default clause of n opening (closing) %% conses, of which only (Cat(n)*((n+1)!-1)) = A001813[n]-A000108[n] %% 0,1,10,115,1666,30198,665148,17296851,518916970,... (not in OEIS) %% result a non-identity permutation. %% %% Then for multiclause gatomorphisms, one clause can be constructed %% in Cat(n)*Cat(n)*(n+1)! (= A001246[n]*A000142[n+1] = A001813[n]*A000108[n]) %% ways: 1,2,24,600,23520,1270080,87816960,7420533120,742053312000 (not in EIS) %% and taking Cameron's inverse of this sequence (from a(n>=1) = 2 onward): %% INVERT([seq(Cat(n)*Cat(n)*(n+1)!,n=1..9)]); %% --> [2,28,704,26800,1404416,94890112,7887853568,779773444864,89407927009280,...] %% we get an absolute upper bound for number of (distinct) simple nonrecursive %% gatomorphisms of total n opening (closing) conses. %% upto3q.txt: Iterated over 31 candidates, of which 30 were filtered and 1 did remain. %% upto7q.txt: Iterated over 735 candidates, of which 722 were filtered and 13 did remain. %% upto15q.txt: Iterated over 27535 candidates, of which 26802 were filtered and 733 did remain. %% upto31q.txt: Iterated over 1431951 candidates, of which 1391570 were filtered and 40381 did remain. %% %% (- 1431951 27535) --> 1404416 %% (- 27535 735) --> 26800 %% (- 735 31) --> 704 %% %% This is because we can say that a sequence of triplets (X_i,Y_i,P_{i+1}) like: %% ((X_i1,Y_i1,P_{i1+1}),(X_i2,Y_i2,P_{i2+1}),...,(X_ik,Y_ik,P_{ik+1})) %% where i1+i2+...+ik = n %% contains sufficient information to define a simple nonrecursive %% gatomorphism of total n opening (closing) conses in k clauses. %% X_i ("source") and Y_i ("destination") refer to arbitrary binary trees %% of i+1 leaves (enumerated by Cat(i)), and P_{i+1} (enumerated by (i+1)!) %% refers to an arbitrary reordering of those i+1 leaves. Possibilities %% for one clause is a cartesian product of these three components. %% However, we can considerably improve the above upper bound by subtracting from it %% [seq((Cat(n)-1)*Cat(n)*(n+1)!,n=1..9)]; to get: %% [2,16,224,4960,164576,7738432,484617728,38239051264,3644207367680,...] %% because no clause with "source" and "destination"-subtrees of different %% shape can occur alone as a "stand-alone" clause: %% there is a binary tree A for which any such clause will succeed, %% but the resulting tree B will not, and because there are no %% other non-default clauses the B will be fixed, thus we have %% two binary trees A & B which map to the same tree B, and thus %% the clause does not result an injection, and cannot thus be %% a bijection either. %% %% There are also other ways to prune the search space. %% For example, it doesn't make sense to examine sequences %% (if we are looking only for distinct, new gatomorphisms that %% have not appeared for any smaller value of n) %% where a later triplet has a (source) binary tree X_j %% which is a super-tree of an earlier (source) binary tree X_i %% (in other words X_i is a subtree of X_j, i.e. X_i = A082858(X_i,X_j)), %% because then the latter clause is no-op, as the first clause %% will always succeed for any tree which would succeed for the latter clause. %% %% Questions: %% %% Is there some a priori way of determining which such triplet-combinations %% result a gatomorphism (i.e. a bijection on the set of binary trees)? %% %% If not, then what is the sure(st) technique for determining whether %% a collection of such clauses indeed result a gatomorphism, i.e. a true bijection? %% Is it enough to check that the candidate gatomorphism looks like %% a bijection up to a certain size s of the binary trees? %% (where s depends only on the sequence of clauses in the candidate gatomorphism) %% %% %% After discarding the duplicates we should get the following triangle, %% where on the n:th row and m:th pos. on that row (both 1-based) %% we have number of non-duplicated gatomorphisms of total n opening %% conses and m non-default clauses: %% Row sums %% 1 1 %% 10 0 10 %% 115 10 0 125 = 5^3 %% 1666 139 0 1805 = 5*19^2 %% 30198 2570 0 0 32768 = 32^3 %% ..... .... .. .. %% Note that it seems that there is the following correspondence between cases %% (2+1 node clauses) = (2 node single clauses) = 10 %% (3+1 node clauses) = (3 node single clauses) = 115 %% (4+1 node clauses) = (4 node single clauses) = 1666 %% %% Clearly number of (n+1 node clauses) is at least equivalent %% to number of single n node clauses (= Cat(n)*((n+1)!-1), %% as in the former case the last clause can only be a swap, %% and thus for each single stand-alone clause of n nodes %% we have another gatomorphism which we obtain by composing %% it with a069770. %% % Two non-default clauses with 3 + 1 = 4 opening (closing) conses: % % % A B C D B A D C % \ / \ / \ / \ / % M N --> P Q A B --> B A % \ / \ / \ / \ / % X Y X Y %% Alternatively, for the first clause we could have any other permutation of the %% four leaves A,B,C & D, as long as we keep the shape of src- & dst-tree same. %% Here we notice that the first clause implies that if we ever %% come to the second clause, then either A or B (the left or right-hand-side subtree) %% is empty, []. %% Both clauses would work as stand-alone clauses, but they also work %% together because the trees for which they succeed are never in the same %% orbit. (The orbit counts of the combination should be easy to compute %% from the orbit counts of the separate clauses? Here the combination %% has the same orbit profile as the latter clause alone (a069770), %% both are involutions.) %% Is this a general condition for the set of stand-alone clauses to work %% together as a bijection? example1(X,Y) :- cons(M,N,X), cons(A,B,M), cons(C,D,N), % -- cons(B,A,P), cons(D,C,Q), cons(P,Q,Y), !. example1(X,Y) :- cons(A,B,X), % -- cons(B,A,Y), !. example1(X,X). %% Fix the rest. % Here the permutation we apply to A,B,C,D is identity, so the first % clause keeps intact trees whose car and cdr side are not nil: % % % A B C D A B C D % \ / \ / \ / \ / % M N --> P Q A B --> B A % \ / \ / \ / \ / % X Y X Y % i.e. this is equal to % (define (example2! s) % (cond ((or (not (pair? (car s))) % (not (pair? (cdr s))) % ) % (gma069770! s) % ) % ) % s % ) % example2(X,Y) :- cons(M,N,X), cons(A,B,M), cons(C,D,N), % -- cons(A,B,P), cons(C,D,Q), cons(P,Q,Y), !. example2(X,Y) :- cons(A,B,X), % -- cons(B,A,Y), !. example2(X,X). %% Fix the rest. %% Two non-default clauses with 2 + 1 = 3 opening (closing) conses: % % % B C C A % \ / \ / % A M --> B P A [] --> [] A % \ / \ / \ / \ / % X Y X Y % %% This is NOT a bijection as we notice that the first clause implies that %% if we ever come to the second clause, then its B (the right-hand-side %% subtree) is empty, []. %% Both clauses would work as stand-alone clauses, as they are just %% permutations of certain branches of otherwise fixed-shape subtree. %% However, as together they don't form a bijection, because %% the first clause maps %% %% [] s s r %% \ / \ / %% r . --> [] . %% \ / \ / %% . . %% %% to which the second clause also maps this tree: %% %% s r %% \ / %% . [] %% \ / %% . %% %% (which will be left alone by the first clause, because its right %% subtree is []). %% So again, the injectivity is broken, thus we have no bijection either. %% example3(X,Y) :- cons(A,M,X), cons(B,C,M), % -- cons(C,A,P), cons(B,P,Y), !. example3(X,Y) :- cons(A,B,X), % -- cons(B,A,Y), !. example3(X,X). %% Fix the rest. % Three non-default clauses with 3 + 2 + 2 = 7 opening (closing) conses: % % % A B C D B A D C A B B A B C C B % \ / \ / \ / \ / \ / \ / \ / \ / % X1 X2 --> Y1 Y2 X1 C --> Y1 C A X1 --> A Y1 % \ / \ / \ / \ / \ / \ / % X Y X Y X Y %% Alternatively, for the first clause we could have any other permutation of the %% four leaves A,B,C & D, as long as we keep the shape of src- & dst-tree same. example4(X,Y) :- cons(X1,X2,X), cons(A,B,X1), cons(C,D,X2), % -- cons(B,A,Y1), cons(D,C,Y2), cons(Y1,Y2,Y), !. example4(X,Y) :- cons(X1,C,X), %% C is implied (). cons(A,B,X1), % -- cons(B,A,Y1), cons(Y1,C,Y), !. example4(X,Y) :- cons(A,X1,X), %% A is implied (). cons(B,C,X1), % -- cons(C,B,Y1), cons(A,Y1,Y), !. example4(X,X). %% Fix the rest. %% Here the execution order of the second and third clause %% can be swapped: example4b(X,Y) :- cons(X1,X2,X), cons(A,B,X1), cons(C,D,X2), % -- cons(B,A,Y1), cons(D,C,Y2), cons(Y1,Y2,Y), !. example4b(X,Y) :- cons(A,X1,X), %% A is implied (). cons(B,C,X1), % -- cons(C,B,Y1), cons(A,Y1,Y), !. example4b(X,Y) :- cons(X1,C,X), %% C is implied (). cons(A,B,X1), % -- cons(B,A,Y1), cons(Y1,C,Y), !. example4b(X,X). %% Fix the rest. % Three non-default clauses with 4 + 4 + 3 = 11 opening (closing) conses: % % The first clause: % % L1 L2 L3 L4 L2 L3 L4 L1 % \ / \ / \ / \ / % X2 X3 --> Y2 Y3 % \ / \ / % X1 L5 Y1 L5 % \ / \ / % X Y example5(X,Y) :- cons(X1,L5,X), cons(X2,X3,X1), cons(L1,L2,X2), cons(L3,L4,X3), % -- cons(L2,L3,Y2), cons(L4,L1,Y3), cons(Y2,Y3,Y1), cons(Y1,L5,Y), !. % The second clause: % % L2 L3 L4 L5 L3 L2 L5 L4 % \ / \ / \ / \ / % X2 X3 --> Y2 Y3 % \ / \ / % L1 X1 L1 Y1 % \ / \ / % X Y example5(X,Y) :- cons(L1,X1,X), cons(X2,X3,X1), cons(L2,L3,X2), cons(L4,L5,X3), % -- cons(L3,L2,Y2), cons(L5,L4,Y3), cons(Y2,Y3,Y1), cons(L1,Y1,Y), !. % The third clause: % The top leaves are permuted as (1 2)(3 4), which is allowed. % % L1 L2 L3 L4 L2 L1 L4 L3 % \ / \ / \ / \ / % X1 X2 Y1 Y2 % \ / \ / % X Y example5(X,Y) :- cons(X1,X2,X), cons(L1,L2,X1), cons(L3,L4,X2), % -- cons(L2,L1,Y1), cons(L4,L3,Y2), cons(Y1,Y2,Y), !. example5(X,X). %% Fix the rest. % Three non-default clauses with 4 + 4 + 3 = 11 opening (closing) conses: % % The first clause: % % L1 L2 L3 L4 L2 L3 L4 L1 % \ / \ / \ / \ / % X2 X3 --> Y2 Y3 % \ / \ / % X1 L5 Y1 L5 % \ / \ / % X Y example5b(X,Y) :- cons(X1,L5,X), cons(X2,X3,X1), cons(L1,L2,X2), cons(L3,L4,X3), % -- cons(L2,L3,Y2), cons(L4,L1,Y3), cons(Y2,Y3,Y1), cons(Y1,L5,Y), !. % The second clause: % % L2 L3 L4 L5 L3 L2 L5 L4 % \ / \ / \ / \ / % X2 X3 --> Y2 Y3 % \ / \ / % L1 X1 L1 Y1 % \ / \ / % X Y % % Note that in all these cases example5 - example5e % if the second clause is triggered, it implies the condition % (A082858(L1,[[[]],[]]) != [[[]],[]]) % i.e. in Scheme-terms: (or (null? L1) (null? (car L1)) (null? (cdr L1))) example5b(X,Y) :- cons(L1,X1,X), cons(X2,X3,X1), cons(L2,L3,X2), cons(L4,L5,X3), % -- cons(L3,L2,Y2), cons(L5,L4,Y3), cons(Y2,Y3,Y1), cons(L1,Y1,Y), !. % The third clause: % The top leaves are permuted as (1 3)(2 4), which is allowed. % % Note that in all these cases example5 - example5e % if the third clause is triggered, it implies the condition % ((A082858(L1,[[]]) != [[]]) or (A082858(L2,[[]]) != [[]])) % and % ((A082858(L3,[[]]) != [[]]) or (A082858(L4,[[]]) != [[]])) % and as [[]] is a subtree of all non-nil trees (including itself), % we can tidy this to a condition: % (((L1 == []) or (L2 == [])) and ((L3 == []) or (L4 == []))) % i.e. both at the left side and right side, at least either of the % top leaves must be NIL. % % L1 L2 L3 L4 L3 L4 L1 L2 % \ / \ / \ / \ / % X1 X2 Y1 Y2 % \ / \ / % X Y example5b(X,Y) :- cons(X1,X2,X), cons(L1,L2,X1), cons(L3,L4,X2), % -- cons(L3,L4,Y1), cons(L1,L2,Y2), cons(Y1,Y2,Y), !. example5b(X,X). %% Fix the rest. % Three non-default clauses with 4 + 4 + 3 = 11 opening (closing) conses: % % The first clause: % % L1 L2 L3 L4 L2 L3 L4 L1 % \ / \ / \ / \ / % X2 X3 --> Y2 Y3 % \ / \ / % X1 L5 Y1 L5 % \ / \ / % X Y example5c(X,Y) :- cons(X1,L5,X), cons(X2,X3,X1), cons(L1,L2,X2), cons(L3,L4,X3), % -- cons(L2,L3,Y2), cons(L4,L1,Y3), cons(Y2,Y3,Y1), cons(Y1,L5,Y), !. % The second clause: % % L2 L3 L4 L5 L3 L2 L5 L4 % \ / \ / \ / \ / % X2 X3 --> Y2 Y3 % \ / \ / % L1 X1 L1 Y1 % \ / \ / % X Y example5c(X,Y) :- cons(L1,X1,X), cons(X2,X3,X1), cons(L2,L3,X2), cons(L4,L5,X3), % -- cons(L3,L2,Y2), cons(L5,L4,Y3), cons(Y2,Y3,Y1), cons(L1,Y1,Y), !. % The third clause: % The top leaves are permuted as (1 4)(2 3), which is allowed. % % L1 L2 L3 L4 L4 L3 L2 L1 % \ / \ / \ / \ / % X1 X2 Y1 Y2 % \ / \ / % X Y example5c(X,Y) :- cons(X1,X2,X), cons(L1,L2,X1), cons(L3,L4,X2), % -- cons(L4,L3,Y1), cons(L2,L1,Y2), cons(Y1,Y2,Y), !. example5c(X,X). %% Fix the rest. % Three non-default clauses with 4 + 4 + 3 = 11 opening (closing) conses: % % The first clause: % % L1 L2 L3 L4 L2 L3 L4 L1 % \ / \ / \ / \ / % X2 X3 --> Y2 Y3 % \ / \ / % X1 L5 Y1 L5 % \ / \ / % X Y example5d(X,Y) :- cons(X1,L5,X), cons(X2,X3,X1), cons(L1,L2,X2), cons(L3,L4,X3), % -- cons(L2,L3,Y2), cons(L4,L1,Y3), cons(Y2,Y3,Y1), cons(Y1,L5,Y), !. % The second clause: % % L2 L3 L4 L5 L3 L2 L5 L4 % \ / \ / \ / \ / % X2 X3 --> Y2 Y3 % \ / \ / % L1 X1 L1 Y1 % \ / \ / % X Y example5d(X,Y) :- cons(L1,X1,X), cons(X2,X3,X1), cons(L2,L3,X2), cons(L4,L5,X3), % -- cons(L3,L2,Y2), cons(L5,L4,Y3), cons(Y2,Y3,Y1), cons(L1,Y1,Y), !. % The third clause: % The top leaves are permuted as (1 3 2 4), which is allowed. % % L1 L2 L3 L4 L3 L4 L2 L1 % \ / \ / \ / \ / % X1 X2 Y1 Y2 % \ / \ / % X Y example5d(X,Y) :- cons(X1,X2,X), cons(L1,L2,X1), cons(L3,L4,X2), % -- cons(L3,L4,Y1), cons(L2,L1,Y2), cons(Y1,Y2,Y), !. example5d(X,X). %% Fix the rest. % Three non-default clauses with 4 + 4 + 3 = 11 opening (closing) conses: % % The first clause: % % L1 L2 L3 L4 L2 L3 L4 L1 % \ / \ / \ / \ / % X2 X3 --> Y2 Y3 % \ / \ / % X1 L5 Y1 L5 % \ / \ / % X Y example5e(X,Y) :- cons(X1,L5,X), cons(X2,X3,X1), cons(L1,L2,X2), cons(L3,L4,X3), % -- cons(L2,L3,Y2), cons(L4,L1,Y3), cons(Y2,Y3,Y1), cons(Y1,L5,Y), !. % The second clause: % % L2 L3 L4 L5 L3 L2 L5 L4 % \ / \ / \ / \ / % X2 X3 --> Y2 Y3 % \ / \ / % L1 X1 L1 Y1 % \ / \ / % X Y example5e(X,Y) :- cons(L1,X1,X), cons(X2,X3,X1), cons(L2,L3,X2), cons(L4,L5,X3), % -- cons(L3,L2,Y2), cons(L5,L4,Y3), cons(Y2,Y3,Y1), cons(L1,Y1,Y), !. % The third clause: % The top leaves are permuted as (1 2 3 4), which is NOT allowed. % E.g. if we originally had NILs _only_ in L2 and L3, thus triggering % this third clause instead of the first or the second one, % then this will move them to L1 and L2, meaning that the next % time the second clause is triggered, breaking the injectivity. % % L1 L2 L3 L4 L2 L3 L4 L1 % \ / \ / \ / \ / % X1 X2 Y1 Y2 % \ / \ / % X Y example5e(X,Y) :- cons(X1,X2,X), cons(L1,L2,X1), cons(L3,L4,X2), % -- cons(L2,L3,Y1), cons(L4,L1,Y2), cons(Y1,Y2,Y), !. example5e(X,X). %% Fix the rest. %% | ?- checkUptoN(example5e,4). --> yes %% | ?- checkUptoN(example5e,5). --> no %% Another example of non-bijective combination. %% First try robl, then robr: %% %% B C A B %% \ / \ / %% A M --> N C %% \ / \ / %% X Y %% Red cuts! nbexample1(X,Y) :- cons(A,M,X), cons(B,C,M), % -- cons(A,B,N), cons(N,C,Y), !. %% Otherwise, try robr: %% %% C B B [] %% \ / \ / %% M [] --> C N %% \ / \ / %% X Y %% Note that A = []. nbexample1(X,Y) :- cons(M,A,X), cons(C,B,M), % -- cons(B,A,N), cons(C,N,Y), !. nbexample1(X,X). %% Fix the rest. %% This follows: %% %% [] [] [] [] %% \ / \ / %% [] . [] [][] [] . [] %% \ / \ / \ / \ / %% [] . --> . . --> . [] %% \ / \ / <-- \ / %% . . . %% %% [[],[],[]] [[[]],[]] [[[[]]]] %% %% | ?- nbexample1([[],[]],X). %% %% X = [[[]]] %% %% yes %% | ?- nbexample1([[[]]],X). %% %% X = [[],[]] %% %% yes %% | ?- nbexample1([[],[],[]],X). %% %% X = [[[]],[]] %% %% yes %% | ?- nbexample1([[[]],[]],X). %% %% X = [[[[]]]] %% %% yes %% | ?- nbexample1([[[[]]]],X). %% %% X = [[[]],[]] %% %% yes %% | ?- nbexample1(X,[[[[]]]]). %% %% X = [[[]],[]] %% %% yes %% | ?- nbexample1(X,[[[]],[]]). %% %% X = [[],[],[]] %% %% yes %% %% | ?- nbexample1(X,[[],[],[]]). %% %% X = [[[]],[]] %% %% | ?- nbexample1([[[[]]]], [[],[[]]]). %% %% no %% | ?- nbexample1([[[]],[]], [[[[]]]]). %% %% yes %% | ?- nbexample1([[[]],[]], [[],[],[]]). %% %% yes %% %% %% Same second time, with green cuts. %% First try robl, then robr: %% %% B C A B %% \ / \ / %% A M --> N C %% \ / \ / %% X Y nbexample2(X,Y) :- cons(A,M,X), cons(B,C,M), % -- cons(A,B,N), cons(N,C,Y), !. %% Otherwise, try robr: %% %% C B B [] %% \ / \ / %% M [] --> C N %% \ / \ / %% X Y %% nbexample2(X,Y) :- cons(M,[],X), cons(C,B,M), % -- cons(B,[],N), cons(C,N,Y), !. nbexample2([[]],[[]]). %% Fix the rest. nbexample2([],[]). %% yes, explicitly. %% Third time, no cuts at all: nbexample3(X,Y) :- cons(A,M,X), cons(B,C,M), % -- cons(A,B,N), cons(N,C,Y). %% Otherwise, try robr: %% %% C B B [] %% \ / \ / %% M [] --> C N %% \ / \ / %% X Y %% nbexample3(X,Y) :- cons(M,[],X), cons(C,B,M), % -- cons(B,[],N), cons(C,N,Y). nbexample3([[]],[[]]). %% Fix the rest. nbexample3([],[]). %% yes, explicitly. %% | ?- nbexample2([[],[],[]],X). %% %% X = [[[]],[]] %% %% yes %% | ?- nbexample2([[[]],[]],X). %% %% X = [[[[]]]] %% %% yes %% | ?- nbexample2([[[[]]]],X). %% %% X = [[[]],[]] %% %% yes %% | ?- nbexample2(X,[[[[]]]]). %% %% X = [[[]],[]] %% %% yes %% | ?- nbexample2(X,[[[]],[]]). %% %% X = [[],[],[]] %% %% yes %% | ?- nbexample2(X,[[],[],[]]). %% %% no %% | ?- %% % % The first clause: % % L1 L2 L3 L4 L2 L3 L4 L1 % \ / \ / \ / \ / % X2 X3 --> Y2 Y3 % \ / \ / % X1 L5 Y1 L5 % \ / \ / % X Y nbexample5(X,Y) :- cons(X1,L5,X), cons(X2,X3,X1), cons(L1,L2,X2), cons(L3,L4,X3), % -- cons(L2,L3,Y2), cons(L4,L1,Y3), cons(Y2,Y3,Y1), cons(Y1,L5,Y), !. % The second clause: % % L2 L3 L4 L5 L3 L2 L1 L4 % \ / \ / \ / \ / % X2 X3 --> Y2 Y3 % \ / \ / % L1 X1 L5 Y1 % \ / \ / % X Y nbexample5(X,Y) :- cons(L1,X1,X), cons(X2,X3,X1), cons(L2,L3,X2), cons(L4,L5,X3), % -- cons(L3,L2,Y2), cons(L1,L4,Y3), cons(Y2,Y3,Y1), cons(L5,Y1,Y), !. nbexample5(X,X). %% Fix the rest. %% Note that we must check up to the size 4+3 = 7 before %% the program sees that the above is not a bijection: %% %% | ?- checkUptoN(nbexample5,6). %% (30 ms) yes %% | ?- checkUptoN(nbexample5,7). %% (240 ms) no applygat(a001477,X,Y) :- a001477(X,Y). applygat(a069770,X,Y) :- a069770(X,Y). applygat(a072796,X,Y) :- a072796(X,Y). applygat(a072797,X,Y) :- a072797(X,Y). applygat(a074679,X,Y) :- a074679(X,Y). applygat(a074680,X,Y) :- a074680(X,Y). applygat(a082351,X,Y) :- a082351(X,Y). applygat(a082352,X,Y) :- a082352(X,Y). applygat(example1,X,Y) :- example1(X,Y). applygat(example2,X,Y) :- example2(X,Y). applygat(example3,X,Y) :- example3(X,Y). applygat(example4,X,Y) :- example4(X,Y). applygat(example4b,X,Y) :- example4b(X,Y). applygat(example5,X,Y) :- example5(X,Y). applygat(example5b,X,Y) :- example5b(X,Y). applygat(example5c,X,Y) :- example5c(X,Y). applygat(example5d,X,Y) :- example5d(X,Y). applygat(example5e,X,Y) :- example5e(X,Y). applygat(nbexample1,X,Y) :- nbexample1(X,Y). applygat(nbexample2,X,Y) :- nbexample2(X,Y). applygat(nbexample3,X,Y) :- nbexample3(X,Y). applygat(nbexample5,X,Y) :- nbexample5(X,Y). %% findall(G,try8(G),Gatot). %% Gatot = [a069770,a082351,example1,example2,example4,example5,example5b,example5c,example5d,a074679,a001477] try8(a069770) :- checkUptoN(a069770,8). try8(a082351) :- checkUptoN(a082351,8). try8(example1) :- checkUptoN(example1,8). try8(example2) :- checkUptoN(example2,8). try8(example3) :- checkUptoN(example3,8). try8(example4) :- checkUptoN(example4,8). try8(example5) :- checkUptoN(example5,8). try8(example5b) :- checkUptoN(example5b,8). try8(example5c) :- checkUptoN(example5c,8). try8(example5d) :- checkUptoN(example5d,8). try8(example5e) :- checkUptoN(example5e,8). try8(a074679) :- checkUptoN(a074679,8). try8(a001477) :- checkUptoN(a001477,8). %% Neither this will work, I think: %% %% B C C B %% \ / \ / %% A M --> A P A B --> B A %% \ / \ / \ / \ / %% X Y X Y %% %% %% %% By Antti Karttunen, 18. - 19. May 2003. %%