如何生成给定长度的只有两个 1 和其他 0 的列表？

Question

我必须生成包含 2 个“1”而其他元素为“0”的列表。我尝试了以下代码，但它不起作用：

count([], _, 0).
count([X|T], X, Y) :- count(T, X, Z), Y is 1+Z.
count([X1|T],X,Z):- X1\=X,count(T,X,Z).

two(X) :- count(X, 1, Counter), Counter =:= 2.

查询 length(Vs, 4), Vs ins 0..1, two(Vs). 没有任何结果。

如何正确生成这样的列表？我希望得到类似 [1, 1, 0, 0], [1, 0, 1, 0] ... [0, 0, 1, 1] 的东西。

Answer 1

twoones(Bs) :-
   Bs ins 0..1,
   sum(Bs, #=, 2).

| ?- length(Bs,4), twoones(Bs).
Bs = [_A,_B,_C,_D],
clpz:(_A+_B+_C+_D#=2),
clpz:(_A in 0..1),
clpz:(_B in 0..1),
clpz:(_C in 0..1),
clpz:(_D in 0..1) ? 
yes
| ?- length(Bs,4), twoones(Bs), labeling([], Bs).
Bs = [0,0,1,1] ? ;
Bs = [0,1,0,1] ? ;
Bs = [0,1,1,0] ? ...

在这里，我使用 library(clpz)，它是 library(clpfd) 的继承者。对于像这样简单的例子，差别不大。

Answer 2

我认为你把它弄得太复杂了。不用在这里使用 clpfd，您可以只创建一个生成此类列表的谓词。

我们可以先做一个谓词，统一所有只包含 0s 的列表：

all0([]).
all0([0|T]) :-
    all0(T).

接下来我们可以创建一个谓词 with1s(N, l) 它将 "inject" N 它生成的列表中的那些：

with1s(0, L) :-
    all0(L).
with1s(N, [H|T]) :-
    N > 0,
    ((H=1, N1 is N-1);
     (H=0, N1 = N)),
    with1s(N1, T).

例如，对于包含三个元素的列表，我们得到：

?- L = [_,_,_], with1s(2, L).
L = [1, 1, 0] ;
L = [1, 0, 1] ;
L = [0, 1, 1] ;
false.

这当然不是双向的，我把它留作进一步改进谓词的练习。

Answer 3

这些都是很好的答案。

这是另一个。 nth0 来自 library(lists).

SWI Prolog nth0
SICStus nth0
出于说明目的，两个 1 已被 a 和 b 取代。
findall(0, between(1, Zlen, _), Zlist) 创建一个长度为 Zlen 的 0 (Zlist) 列表。参见 between。

gimme(List,Len) :- Len >= 2,                    
                   Zlen is Len-2,
                   findall(0, between(1, Zlen, _), Zlist),
                   between(0, Zlen, Pos1),                 % we will insert 'a' at Pos1
                   Pos1n is Pos1+1,
                   between(Pos1n,Len,Pos2),                % we will insert 'b' at Pos2, always after 'a'
                   nth0(Pos1, Tlist, a, Zlist),            % Zlist -morph-> Tlist
                   nth0(Pos2, List, b, Tlist).             % Tlist -morph-> List

?- gimme(L,2).
L = [a, b] ;
false.

?- gimme(L,3).
L = [a, b, 0] ;
L = [a, 0, b] ;
L = [0, a, b] ;
false.

?- gimme(L,4).
L = [a, b, 0, 0] ;
L = [a, 0, b, 0] ;
L = [a, 0, 0, b] ;
L = [0, a, b, 0] ;
L = [0, a, 0, b] ;
L = [0, 0, a, b] ;
false.

?- gimme(L,5).
L = [a, b, 0, 0, 0] ;
L = [a, 0, b, 0, 0] ;
L = [a, 0, 0, b, 0] ;
L = [a, 0, 0, 0, b] ;
L = [0, a, b, 0, 0] ;
L = [0, a, 0, b, 0] ;
L = [0, a, 0, 0, b] ;
L = [0, 0, a, b, 0] ;
L = [0, 0, a, 0, b] ;
L = [0, 0, 0, a, b] ;

Answer 4

文法是指定列表模式的一种很自然的方式：

two --> [1], one ; [0], two.
one --> [1], zeros ; [0], one.
zeros --> [] ; [0], zeros.

调用示例：

?- length(Xs, 3), phrase(two, Xs, []).
Xs = [1, 1, 0]
Yes (0.00s cpu, solution 1, maybe more)
Xs = [1, 0, 1]
Yes (0.00s cpu, solution 2, maybe more)
Xs = [0, 1, 1]
Yes (0.00s cpu, solution 3, maybe more)
No (0.00s cpu)

Answer 5

指定此模式的另一种方法：

two_ones_n_zeros(N, L) :-
    length(Z, N),
    maplist(=(0), Z),
    nth1(I, L0, 1, Z),
    nth1(J, L, 1, L0),
    I < J.

示例：

?- two_ones_n_zeros(2, L).
L = [1, 1, 0, 0] ;
L = [1, 0, 1, 0] ;
L = [1, 0, 0, 1] ;
L = [0, 1, 1, 0] ;
L = [0, 1, 0, 1] ;
L = [0, 0, 1, 1] ;
false.

不同方法的效率比较

two_ones_n_zeros_dcg(N, L) :-
    M is N + 2,
    length(L, M),
    phrase((zeros, [1], zeros, [1], zeros), L).

two --> [1], one ; [0], two.
one --> [1], zeros ; [0], one.
zeros --> [] ; [0], zeros.

:- use_module(library(clpfd)).

two_ones_n_zeros_clp(N, L) :-
    M is N + 2,
    length(L, M),
    twoones(L),
    labeling([], L).

twoones(Bs) :-
   Bs ins 0..1,
   sum(Bs, #=, 2).

comparison(N) :-
    write('\nLists: '),
    garbage_collect,
    time(forall(two_ones_n_zeros(N, _), true)),
    write('\nDCG: '),
    garbage_collect,
    time(forall(two_ones_n_zeros_dcg(N, _), true)),
    write('\nCLP: '),
    garbage_collect,
    time(forall(two_ones_n_zeros_clp(N, _), true)).

经验结果，使用swi-prolog（版本 8.4.2）：

?- two_ones_n_zeros(1, L1).
L1 = [1, 1, 0] ;
L1 = [1, 0, 1] ;
L1 = [0, 1, 1] ;
false.

?- two_ones_n_zeros_dcg(1, L1).
L1 = [1, 1, 0] ;
L1 = [1, 0, 1] ;
L1 = [0, 1, 1] ;
false.

?- two_ones_n_zeros_clp(1, L1).
L1 = [0, 1, 1] ;
L1 = [1, 0, 1] ;
L1 = [1, 1, 0].

?- comparison(400).

Lists: 
% 323,613 inferences, 0.031 CPU in 0.031 seconds (100% CPU, 10355616 Lips)

DCG: 
% 11,152,272 inferences, 0.391 CPU in 0.391 seconds (100% CPU, 28549816 Lips)

CLP: 
% 1,302,560,369 inferences, 94.063 CPU in 94.110 seconds (100% CPU, 13847818 Lips)
true.

如何生成给定长度的只有两个 1 和其他 0 的列表？

How to generate a list with only two 1s and other 0s of the given length?

list

prolog

clpfd