在约束成立和不成立的情况下生成随机值

Question

我有以下内容：

:-use_module(library(clpfd)).

list_index_value(List,Index,Value):-
  nth0(Index,List,Value).

length_conindexes_conrandomvector(Length,Conindexs,Randomvector):-
  length(Randomvector,Length),
  same_length(Conindexs,Ones),
  maplist(=(1),Ones),
  maplist(list_index_value(Randomvector),Conindexs,Ones),
  term_variables(Randomvector,Vars),
  maplist(random_between(0,1),Vars).

length_conindexes_notconrandomvector(Length,Conindexes,Randomvector):-
  length(Randomvector,Length),
  length(Conindexes,NumberOfCons),
  same_length(Conindexes,Values),
  sum(Values,#\=,NumberOfCons),
  maplist(list_index_value(Randomvector),Conindexes,Values),
  term_variables(Randomvector,Vars),
  repeat,
  maplist(random_between(0,1),Vars).

length_conindexes_conrandomvector/3用于生成一个由1和0组成的随机向量，conindex位置的元素为1。

 ?-length_conindexes_conrandomvector(4,[0,1],R).
 R = [1, 1, 0, 1].

length_conindexes_notconrandomvector/3 用于生成一个随机向量，其中并非所有的 conindexes 都是 1。

?- length_conindexes_notconrandomvector(3,[0,1,2],R).
R = [1, 0, 1] ;
R = [0, 1, 1] ;
R = [1, 1, 0]

这个我觉得我有 'hacked' 和 repeat 命令。做这个的最好方式是什么？如果我使用标签，那么这些值将不是随机的？如果经常违反约束，那么搜索将非常低效。最好的方法是什么？

Answer 1

在 SWI-Prolog 中，我将使用 CLP(B) 约束来完成所有这些操作。

例如¹:

:- use_module(library(clpb)).

length_conindices_notconrandomvector(L, Cs, Rs):-
        L #> 0,
        LMax #= L - 1,
        numlist(0, LMax, Is),
        pairs_keys_values(Pairs, Is, _),
        list_to_assoc(Pairs, A),
        maplist(assoc_index_value(A), Cs, Vs),
        sat(~ *(Vs)),
        assoc_to_values(A, Rs).

assoc_index_value(A, I, V) :- get_assoc(I, A, V).

请注意，我还冒昧地将用于获取所需元素的 O(N²) 方法转换为 O(N×log N) 一.

示例查询：

?- length_conindices_notconrandomvector(4, [0,1], Rs).
Rs = [X1, X2, X3, X4],
sat(1#X1*X2).

始终建议将建模部分分离到它自己的谓词中，我们称之为核心关系。要获得具体的解决方案，您可以使用例如 random_labeling/2:

?- length_conindices_notconrandomvector(4, [0,1], Rs),
   length(_, Seed),
   random_labeling(Seed, Rs).
Rs = [0, 1, 1, 1],
Seed = 0 ;
Rs = [1, 0, 0, 1],
Seed = 1 ;
Rs = [1, 0, 1, 1],
Seed = 2 ;
Rs = [1, 0, 0, 1],
Seed = 3 .

CLP(B) 的 random_labeling/2 的实现方式是每个解决方案 等概率 。

_{¹当然，我假设您的 ~/.swiplrc 中已经有 :- use_module(library(clpfd)).。}

在约束成立和不成立的情况下生成随机值

Generating random values where a constraint does and does not hold

prolog

clpfd

clpb