Я знаю, как сделать простое генерирование и тестирование , чтобы возвращать каждый ответ индивидуально.В следующем примере возвращаются только элементы, которые больше 1.
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.
Я также могу вернуть результаты в виде списка, используя 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 вершинами, у которых ребра не направлены , не имеют циклов (собственные ссылки), не имеют веса и вершины помечены и вершины root нет, а набор графов - это только изоморфных графов .Генерация всех графиков для 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
Однако, поскольку генерируется много избыточных изоморфных графов, путем сокращения списка по мере его увеличения размер N может быть увеличен.См .: Перечислите все неизоморфные графы определенного размера
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).
Тест для изоморфных графов в Прологе.
Примеры сгенерированных графиков:
?- 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 ) по сравнению с желаемыми графиками ( 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ссылка для скачивания на домашней странице .( Руководство пользователя )
Программы написаны на C и используют make и могут работать в Linux.Вместо использования Cygwin в Windows WSL можно установить вместо .
Исходный код можно загрузить с помощью
wget "http://pallini.di.uniroma1.it/nauty26r11.tar.gz"
, а затем
tar xvzf nauty26r11.tar.gz
cd nauty26r11
./configure
make
nauty генерирует выходные данные в формате graph6 по умолчанию, но может быть преобразован в список ребер с помощью 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
Полезные опции для программ
geng
-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 - это размер для10 из A001349
Как создать файл в Windows с помощью WSL
Поскольку 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