代码之家 › 专栏 › 技术社区 › axsuul

匹配列表的谓词(所有可能性)没有重复的整数,长度为N,并且在1到N的域内

prolog

-1

axsuul · 技术社区 · 15 年前

这是给GNU Prolog的

我无法让某个谓词起作用。它的功能是匹配一个整数列表域为1到 N N个 . 基本上我想做的是把它作为输入和输出:

| ?- row_valid(X, 3).

X = [1, 2, 3] ? ;
X = [1, 3, 2] ? ;
X = [2, 1, 3] ? ;
X = [2, 3, 1] ? ;
X = [3, 1, 2] ? ;
X = [3, 2, 1] ? ;

no

| ?- row_valid(X, 2).

X = [1, 2] ? ;
X = [2, 1] ? ;

no

| ?- row_valid(X, 1).

X = [1] ? ;

no

但现在,这是正在发生的事情:

| ?- row_valid(X, 3).

X = [] ? ;

no

这可能是因为 row_valid([], _).

| ?- row_valid([1,2,3], 3).

true ?

yes

下面是定义的谓词。你有什么建议可以让我按我想的方式工作吗?谢谢你的时间。

% row_valid/2: matches if list of integers has domain of 1 to N and is not duplicated
% 1 - list of integers
% 2 - N
row_valid([], _).
row_valid(Row, N) :-
    length(Row, N),                % length
    no_duplicates_within_domain(Row, 1, N),
    row_valid(RestRow, N).

% no_duplicates/1: matches if list doesn't have repeat elements
% 1 - list
no_duplicates([]).        % for empty list always true
no_duplicates([Element | RestElements]) :-
    \+ member(Element, RestElements),        % this element cannot be repeated in the list
    no_duplicates(RestElements).

% within_domain/3 : matches if list integers are within a domain
% 1 - list
% 2 - min
% 3 - max
within_domain(Integers, Min, Max) :-
    max_list(Integers, Max),
    min_list(Integers, Min).

% no_duplicates_within_domain/3: matches if list integers are within a domain and isn't repeated
% 1 - list
% 2 - min
% 3 - max
no_duplicates_within_domain(Integers, Min, Max) :-
    no_duplicates(Integers),
    within_domain(Integers, Min, Max).

2 回复 | 直到 15 年前

1

0

Kaarel 15 年前

这里有一段简单的代码可以在SWI-Prolog中实现这一点。我不知道GNU Prolog是否提供 between/3 和 permutation/2

row_valid(List, N) :-
    findall(X, between(1, N, X), Xs),
    permutation(Xs, List).

用法示例:

?- row_valid(List, 0).
List = [].

?- row_valid(List, 1).
List = [1] ;
false.

?- row_valid(List, 2).
List = [1, 2] ;
List = [2, 1] ;
false.

?- row_valid(List, 3).
List = [1, 2, 3] ;
List = [2, 1, 3] ;
List = [2, 3, 1] ;
List = [1, 3, 2] ;
List = [3, 1, 2] ;
List = [3, 2, 1] ;
false.

2

1

repeat 11 年前

下面呢?

row_valid(Xs,N) :-
   length(Xs,N),
   fd_domain(Xs,1,N),
   fd_all_different(Xs),
   fd_labeling(Xs).

?- row_valid(Xs,N).          

N = 0
Xs = [] ? ;

N = 1
Xs = [1] ? ;

N = 2
Xs = [1,2] ? ;

N = 2
Xs = [2,1] ? ;

N = 3
Xs = [1,2,3] ? ;

N = 3
Xs = [1,3,2] ? ;

N = 3
Xs = [2,1,3] ? ;

N = 3
Xs = [2,3,1] ? ;

N = 3
Xs = [3,1,2] ? ;

N = 3
Xs = [3,2,1] ? ;

N = 4
Xs = [1,2,3,4] ?        % ...and so on...