生成并测试为下一次测试积累有效答案
Generate and Test accumulating valid answer for next test
我知道如何做一个简单的 generate and test 到 return 每个答案。在以下示例中，只有大于 1 的项目才被 returned.
item(1).
item(1).
item(2).
item(3).
item(1).
item(7).
item(1).
item(4).
gen_test(Item) :-
item(Item), % generate
Item > 1. % test
?- gen_test(Item).
Item = 2 ;
Item = 3 ;
Item = 7 ;
Item = 4.
我还可以 return 使用 bagof/3
作为列表的结果
gen_test_bagof(List) :-
bagof(Item,(item(Item),Item > 1), List).
?- gen_test_bagof(List).
List = [2, 3, 7, 4].
现在我希望能够更改测试，以便它使用 member/2 和一个列表，其中列表是所有先前有效答案的累积。
我试过了
gen_test_acc_facts(L) :-
gen_test_acc_facts([],L).
gen_test_acc_facts(Acc0,R) :-
item(H), % generate
(
member(H,Acc0) % test
->
gen_test_acc_facts(Acc0,R) % Passes test, don't accumulate, run generate and test again.
;
gen_test_acc_facts([H|Acc0],R) % Fails test, accumulate, run generate and test again.
).
但由于它是递归的，因此每次调用 item/1 都会导致使用相同的第一个事实。
我怀疑答案将需要消除回溯，就像在此 by mat 中所做的那样，因为这需要 通过回溯 .
保留信息
详情
给出的示例是实际问题的简化版本，即生成具有 N 个顶点的图，其中边为 undirected，没有
loops (self references), have no weights and the vertexes are labeled and there is no root vertex and set of graphs is only the isomorphic graphs。生成 N 的所有图表很容易，虽然我可以先将所有图表累积到一个列表中，然后相互测试所有图表；一旦 N=8，内存就会耗尽。
?- graph_sizes(N,Count).
N = 0, Count = 1 ;
N = Count, Count = 1 ;
N = Count, Count = 2 ;
N = 3, Count = 8 ;
N = 4, Count = 64 ;
N = 5, Count = 1024 ;
N = 6, Count = 32768 ;
N = 7, Count = 2097152 ;
ERROR: Out of global stack
然而，由于生成了很多冗余同构图，通过在列表增长时p运行它，可以增加N的大小。参见：Enumerate all non-isomorphic graphs of a certain size
gen_vertices(N,L) :-
findall(X,between(1,N,X),L).
gen_edges(Vertices, Edges) :-
findall((X,Y), (member(X, Vertices), member(Y, Vertices), X < Y), Edges).
gen_combination_numerator(N,Numerator) :-
findall(X,between(0,N,X),L0),
member(Numerator,L0).
comb(0,_,[]).
comb(N,[X|T],[X|Comb]) :-
N>0,
N1 is N-1,
comb(N1,T,Comb).
comb(N,[_|T],Comb) :-
N>0,
comb(N,T,Comb).
gen_graphs(N,Graph) :-
gen_vertices(N,Vertices),
gen_edges(Vertices,Edges),
length(Edges,Denominator),
gen_combination_numerator(Denominator,Numerator),
comb(Numerator,Edges,Graph).
graph_sizes(N,Count) :-
length(_,N),
findall(.,gen_graphs(N,_), Sols),
length(Sols,Count).
Prolog 中同构图的 。
生成的图表示例：
?- gen_graphs(1,G).
G = [] ;
false.
?- gen_graphs(2,G).
G = [] ;
G = [(1, 2)] ;
false.
?- gen_graphs(3,G).
G = [] ;
G = [(1, 2)] ;
G = [(1, 3)] ;
G = [(2, 3)] ;
G = [(1, 2), (1, 3)] ;
G = [(1, 2), (2, 3)] ;
G = [(1, 3), (2, 3)] ;
G = [(1, 2), (1, 3), (2, 3)] ;
false.
正在生成的所有图表之间的差异（A006125) vs the desired graphs (A001349）。
A006125 A001349 Extraneous
0 1 - 1 = 0
1 1 - 1 = 0
2 2 - 1 = 1
3 8 - 2 = 6
4 64 - 6 = 58
5 1024 - 21 = 1003
6 32768 - 112 = 32656
7 2097152 - 853 = 2096299
8 268435456 - 11117 = 268424339
9 68719476736 - 261080 = 68719215656
10 35184372088832 - 11716571 = 35184360372261
11 36028797018963968 - 1006700565 = 36028796012263403
12 73786976294838206464 - 164059830476 = 73786976130778375988
13 302231454903657293676544 - 50335907869219 = 302231454853321385807325
14 2475880078570760549798248448 - 29003487462848061 = 2475880078541757062335400387
15 40564819207303340847894502572032 - 31397381142761241960 = 40564819207271943466751741330072
使用 geng 和 listg
这两个程序都包含在 nauty and Traces 下载 link home page. (User's guide)
程序是用C编写的，利用了make，可以运行上Linux。而不是在 Windows 上使用 Cygwin，而是 WSL can be installed。
可以使用
下载源代码
wget "http://pallini.di.uniroma1.it/nauty26r11.tar.gz"
然后
tar xvzf nauty26r11.tar.gz
cd nauty26r11
./configure
make
nauty generates output in graph6 format by default but can be converted to list of edges using listg，例如
eric@WINDOWS-XYZ:~/nauty26r11$ ./geng 3 | ./listg -e
>A ./geng -d0D2 n=3 e=0-3
>Z 4 graphs generated in 0.00 sec
Graph 1, order 3.
3 0
Graph 2, order 3.
3 1
0 2
Graph 3, order 3.
3 2
0 2 1 2
Graph 4, order 3.
3 3
0 1 0 2 1 2
程序的有用选项
耿
-help : options
-c : only write connected graphs (A001349)
-u : do not output any graphs, just generate and count them
例子
eric@WINDOWS-ABC:~/nauty26r11$ ./geng -c -u 10
>A ./geng -cd1D9 n=10 e=9-45
>Z 11716571 graphs generated in 5.09 sec
请注意，11716571 是 A001349
中 10 的大小
如何使用 WSL
在 Windows 上创建文件
由于 WSL 可以访问 Windows 文件系统，因此可以将 WSL 命令的输出定向到 Windows 文件，例如
touch /mnt/c/Users/Eric/graphs.txt
不需要触摸步骤，但我先用它创建一个空文件，然后验证它是否在 Windows 上，以确保我输入的路径正确。
这是在用户目录中为 A001349 创建图边列表的示例。
.geng -c 1 | .listg -e >> /mnt/c/Users/Eric/graphs.txt
.geng -c 2 | .listg -e >> /mnt/c/Users/Eric/graphs.txt
在 SWI-Prolog 中，您可以将值存储在 global vars 中：
- 可回溯
b：b_setval、b_getval
- 不可回溯
nb: nb_setval, nb_getval
除了使用 dynamic predicates: assert/retract.
item(1).
item(1).
item(2).
item(3).
item(1).
item(7).
item(1).
item(4).
使用常规列表的解决方案 1
gen_test(Item) :-
nb_setval(sofar, []),
item(Item), % generate
once(
(
nb_getval(sofar, SoFar),
(Item > 1, \+ member(Item, SoFar)), % test custom + on membership in earlier tests
nb_setval(sofar, [Item | SoFar])
)
;
true
),
fail; true.
解决方案 2 使用开放列表
gen_test1(Item) :-
(
item(Item), % generate
Item > 1, lookup(Item, SoFar, ItemExists)),
ItemExists == true -> fail; true
);
append(SoFar, [], SoFar ), % stubbing open list
nb_setval(sofar, Sofar).
lookup( I, [ I | _ ], true).
lookup( I, [ _ | L ], false) :-
var( L ); L == [].
lookup( I, [ _ | L ] ItemExists ):-
lookup( I, L, ItemExists ).
我知道如何做一个简单的 generate and test 到 return 每个答案。在以下示例中，只有大于 1 的项目才被 returned.
item(1).
item(1).
item(2).
item(3).
item(1).
item(7).
item(1).
item(4).
gen_test(Item) :-
item(Item), % generate
Item > 1. % test
?- gen_test(Item).
Item = 2 ;
Item = 3 ;
Item = 7 ;
Item = 4.
我还可以 return 使用 bagof/3
作为列表的结果gen_test_bagof(List) :-
bagof(Item,(item(Item),Item > 1), List).
?- gen_test_bagof(List).
List = [2, 3, 7, 4].
现在我希望能够更改测试，以便它使用 member/2 和一个列表，其中列表是所有先前有效答案的累积。
我试过了
gen_test_acc_facts(L) :-
gen_test_acc_facts([],L).
gen_test_acc_facts(Acc0,R) :-
item(H), % generate
(
member(H,Acc0) % test
->
gen_test_acc_facts(Acc0,R) % Passes test, don't accumulate, run generate and test again.
;
gen_test_acc_facts([H|Acc0],R) % Fails test, accumulate, run generate and test again.
).
但由于它是递归的，因此每次调用 item/1 都会导致使用相同的第一个事实。
我怀疑答案将需要消除回溯，就像在此
详情
给出的示例是实际问题的简化版本，即生成具有 N 个顶点的图，其中边为 undirected，没有 loops (self references), have no weights and the vertexes are labeled and there is no root vertex and set of graphs is only the isomorphic graphs。生成 N 的所有图表很容易，虽然我可以先将所有图表累积到一个列表中，然后相互测试所有图表；一旦 N=8，内存就会耗尽。
?- graph_sizes(N,Count).
N = 0, Count = 1 ;
N = Count, Count = 1 ;
N = Count, Count = 2 ;
N = 3, Count = 8 ;
N = 4, Count = 64 ;
N = 5, Count = 1024 ;
N = 6, Count = 32768 ;
N = 7, Count = 2097152 ;
ERROR: Out of global stack
然而，由于生成了很多冗余同构图，通过在列表增长时p运行它，可以增加N的大小。参见：Enumerate all non-isomorphic graphs of a certain size
gen_vertices(N,L) :-
findall(X,between(1,N,X),L).
gen_edges(Vertices, Edges) :-
findall((X,Y), (member(X, Vertices), member(Y, Vertices), X < Y), Edges).
gen_combination_numerator(N,Numerator) :-
findall(X,between(0,N,X),L0),
member(Numerator,L0).
comb(0,_,[]).
comb(N,[X|T],[X|Comb]) :-
N>0,
N1 is N-1,
comb(N1,T,Comb).
comb(N,[_|T],Comb) :-
N>0,
comb(N,T,Comb).
gen_graphs(N,Graph) :-
gen_vertices(N,Vertices),
gen_edges(Vertices,Edges),
length(Edges,Denominator),
gen_combination_numerator(Denominator,Numerator),
comb(Numerator,Edges,Graph).
graph_sizes(N,Count) :-
length(_,N),
findall(.,gen_graphs(N,_), Sols),
length(Sols,Count).
Prolog 中同构图的
生成的图表示例：
?- gen_graphs(1,G).
G = [] ;
false.
?- gen_graphs(2,G).
G = [] ;
G = [(1, 2)] ;
false.
?- gen_graphs(3,G).
G = [] ;
G = [(1, 2)] ;
G = [(1, 3)] ;
G = [(2, 3)] ;
G = [(1, 2), (1, 3)] ;
G = [(1, 2), (2, 3)] ;
G = [(1, 3), (2, 3)] ;
G = [(1, 2), (1, 3), (2, 3)] ;
false.
正在生成的所有图表之间的差异（A006125) vs the desired graphs (A001349）。
A006125 A001349 Extraneous
0 1 - 1 = 0
1 1 - 1 = 0
2 2 - 1 = 1
3 8 - 2 = 6
4 64 - 6 = 58
5 1024 - 21 = 1003
6 32768 - 112 = 32656
7 2097152 - 853 = 2096299
8 268435456 - 11117 = 268424339
9 68719476736 - 261080 = 68719215656
10 35184372088832 - 11716571 = 35184360372261
11 36028797018963968 - 1006700565 = 36028796012263403
12 73786976294838206464 - 164059830476 = 73786976130778375988
13 302231454903657293676544 - 50335907869219 = 302231454853321385807325
14 2475880078570760549798248448 - 29003487462848061 = 2475880078541757062335400387
15 40564819207303340847894502572032 - 31397381142761241960 = 40564819207271943466751741330072
使用 geng 和 listg
这两个程序都包含在 nauty and Traces 下载 link home page. (User's guide)
程序是用C编写的，利用了make，可以运行上Linux。而不是在 Windows 上使用 Cygwin，而是 WSL can be installed。
可以使用
下载源代码wget "http://pallini.di.uniroma1.it/nauty26r11.tar.gz"
然后
tar xvzf nauty26r11.tar.gz
cd nauty26r11
./configure
make
nauty generates output in graph6 format by default but can be converted to list of edges using listg，例如
eric@WINDOWS-XYZ:~/nauty26r11$ ./geng 3 | ./listg -e
>A ./geng -d0D2 n=3 e=0-3
>Z 4 graphs generated in 0.00 sec
Graph 1, order 3.
3 0
Graph 2, order 3.
3 1
0 2
Graph 3, order 3.
3 2
0 2 1 2
Graph 4, order 3.
3 3
0 1 0 2 1 2
程序的有用选项
耿
-help : options
-c : only write connected graphs (A001349)
-u : do not output any graphs, just generate and count them
例子
eric@WINDOWS-ABC:~/nauty26r11$ ./geng -c -u 10
>A ./geng -cd1D9 n=10 e=9-45
>Z 11716571 graphs generated in 5.09 sec
请注意，11716571 是 A001349
10 的大小
如何使用 WSL
在 Windows 上创建文件由于 WSL 可以访问 Windows 文件系统，因此可以将 WSL 命令的输出定向到 Windows 文件，例如
touch /mnt/c/Users/Eric/graphs.txt
不需要触摸步骤，但我先用它创建一个空文件，然后验证它是否在 Windows 上，以确保我输入的路径正确。
这是在用户目录中为 A001349 创建图边列表的示例。
.geng -c 1 | .listg -e >> /mnt/c/Users/Eric/graphs.txt
.geng -c 2 | .listg -e >> /mnt/c/Users/Eric/graphs.txt
在 SWI-Prolog 中，您可以将值存储在 global vars 中：
- 可回溯
b：b_setval、b_getval - 不可回溯
nb:nb_setval,nb_getval
除了使用 dynamic predicates: assert/retract.
item(1).
item(1).
item(2).
item(3).
item(1).
item(7).
item(1).
item(4).
使用常规列表的解决方案 1
gen_test(Item) :-
nb_setval(sofar, []),
item(Item), % generate
once(
(
nb_getval(sofar, SoFar),
(Item > 1, \+ member(Item, SoFar)), % test custom + on membership in earlier tests
nb_setval(sofar, [Item | SoFar])
)
;
true
),
fail; true.
解决方案 2 使用开放列表
gen_test1(Item) :-
(
item(Item), % generate
Item > 1, lookup(Item, SoFar, ItemExists)),
ItemExists == true -> fail; true
);
append(SoFar, [], SoFar ), % stubbing open list
nb_setval(sofar, Sofar).
lookup( I, [ I | _ ], true).
lookup( I, [ _ | L ], false) :-
var( L ); L == [].
lookup( I, [ _ | L ] ItemExists ):-
lookup( I, L, ItemExists ).