我遇到了以下难题，无法在 Picat 中制定解决方案:
You will generate 5-digit numbers, where each digit is in
1..5and different from the others, with the constraint that any three adjacent digits used in one number can’t be used in another number. How many different numbers can be obtained according to this rule?
例如，如果我们生成数字
12345 ，则其他数字不能包含 123 、 345 或 456 ，因此以下形式的所有数字都被禁止进入链:123AB, A123B, AB123,
234AB, A234B, AB234,
345AB, A345B, AB345,
我的尝试:
我想我设法为给定的链状态生成了有效的“候选者”，但我不知道如何生成这样的链。
import cp.
import util.
valid(Ls, Cd) ?=>
% verify that the head of the chain is correct?
% so the chain consists of permutations of 12345
foreach (L in Ls)
len(L) = 5,
permutation(L, [1,2,3,4,5])
end,
% generate the candidate
Cd = new_list(5),
permutation(Cd, [1,2,3,4,5]),
% check the candidate against the head of the chain
foreach (L in Ls)
not sublist([L[1],L[2],L[3]], Cd),
not sublist([L[2],L[3],L[4]], Cd),
not sublist([L[3],L[4],L[5]], Cd)
end,
solve(Ls),
printf("Cd: %w\n", Cd),
fail,
nl.
% so that 3 element sublists of 12345 are 123,234 and 345.
sublist(X, S) =>
append(_, T , S),
append(X, _ , T),
X.len #>= 0.
% seems to work, the candidates don't have the banned triplets as sublists.
% so in this case the banned triplets would be
% 123,234,345,543,432,321
go => valid([[1,2,3,4,5], [5,4,3,2,1]], _).
main => go.
[12345,12435,12534,13245,13425,13524,14235,
14325,14523,21543,24153,25413,35421,43152]
Cd1: [5,3,2,1,4]
Cd2: [4,5,3,1,2]
Cd3: [4,5,3,2,1]
Cd3 ，因为它同时包含 453 和 532 它不允许我们选择它之后的任何候选者，所以链结束于 N=15 。如果我们选择
Cd1 ，它会排除 Cd3 但仍然保留 Cd2 ，所以链继续到 N=16 。同样，如果我们选择
Cd2 ，它会排除 Cd3 但仍保留 Cd1 ，因此 N=16 也是可能的。因此，似乎一般而言，某些候选者包含(因此排除)其他候选者，而链条的长度取决于我们是否选择这些候选者。
最佳答案
这是带有 中的模型的 Picat 模型更新 4 和 更新 5 和 更新 6 :http://hakank.org/picat/generating_numbers.pi
更新 6 :这可能是我会写的约束模型，如果不是从一开始就对问题的错误假设误入歧途......这是一种更直接的方法(从约束程序员的角度来看)并且不要使用 permutations/1等等。
比稍慢更新 5 (使用 sat 求解器为 3.7 秒，而 更新 4 模型为 3.3 秒)。然而，cp 求解器在此模型上要慢得多。
在上面引用的 Picat 程序中，它的模型是 go3/0 . (最快的模型是 go/0 。)
该方法:
该模型:
go3 ?=>
nolog,
N = 5,
M = 20,
X = new_array(M,N),
X :: 1..N,
% symmetry breaking
X[1,1] #= 1,X[1,2] #= 2,X[1,3] #= 3,X[1,4] #= 4,X[1,5] #= 5,
foreach(I in 1..M)
all_distinct([X[I,K] : K in 1..N]),
foreach(J in 1..I-1)
foreach(A in 0..2)
foreach(B in 0..2)
sum([X[I,K+A] #= X[J,K+B] : K in 1..3]) #< 3
end
end
end
end,
solve($[ff,split],X),
foreach(P in X)
println(P.to_list)
end,
println(numbers=[[I.to_string : I in T].join('').to_int : T in X]),
nl.
go3 => true.
[12345,35421,23154,25314,43512,32415,32541,12453,21534,14523,
34251,14235,54312,45132,51432,52134,53214,34125,41352,15243]
这里的方法是:
Ps ) 中，构建一个 120 x 120 矩阵 A 0/1 其中 A[P1,P2] = 1意味着 Ps[P1]和 Ps[P2]是兼容的，即它们没有共同的三元组 X长度为 120，其中 X[I] = 1表示排列 Ps[I]应该在序列中(或者更确切地说是“设置”，因为排列的顺序没有区别)。 X[I]*X[J] #= 1 #=> A[I,J]是一种“奇怪”的说法，两者都是 X[I]和 X[J]如果 A[I,J] #= 1 应该在序列中. cp 求解器大约需要 3.3s 才能找到第一个长度为 20 的解。该模型的 sat 求解器较慢:4.8 秒(因此它仍然比 更新 4 版本快得多)。
这里是完整的模型:
go ?=>
N = 5,
Ps = permutations(1..N),
PsLen = Ps.len,
% Compatibility matrix:
% A[P1,P2] = 1 if they don't have any common triple
A = new_array(PsLen,PsLen),
bind_vars(A,0),
foreach(P1 in 1..PsLen)
A[P1,P1] := 1,
foreach(P2 in 1..PsLen, P1 < P2)
if check_perms(Ps[P1],Ps[P2]) then
A[P1,P2] := 1,
A[P2,P1] := 1
end
end
end,
M = 20, % length 20 sequence
println(m=M),
% List of 0/1:
% 1 means that it should be in the sequence
X = new_list(PsLen),
X :: 0..1,
sum(X) #= M, % We want M 1s
X[1] #= 1, % symmetry breaking
foreach(I in 1..PsLen)
foreach(J in 1..I-1)
X[I]*X[J] #= 1 #=> A[I,J]
end
end,
solve($[degree,updown],X),
println(x=X),
Perms = [Ps[I] : I in 1..PsLen, X[I]==1],
foreach(P in Perms)
println(P)
end,
println(numbers=[[I.to_string : I in T].join('').to_int : T in Perms]),
% println("Checking:"),
% foreach(I in 1..Perms.len, J in 1..I-1)
% if not check_perms(Perms[I],Perms[J]) then
% println("ERROR!"=Perms[I]=Perms[J])
% end
% end,
nl,
% fail,
nl.
go4 => true.
% list version
check2(Forbidden,Tri) =>
foreach(PP in Tri)
not membchk(PP,Forbidden)
end.
check_perms(Perm1,Perm2) =>
tri(Perm1,Tri1),
tri(Perm2,Tri2),
foreach(PP in Tri2)
not membchk(PP,Tri1)
end,
foreach(PP in Tri1)
not membchk(PP,Tri2)
end.
tri(P,Tri) :- Tri=[P[K..K+2] : K in 1..3].
x = [1,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1]
[1,2,3,4,5]
[3,2,4,1,5]
[3,4,2,5,1]
[2,1,4,3,5]
[4,3,1,2,5]
[4,1,3,5,2]
[2,4,5,1,3]
[4,2,1,5,3]
[4,5,2,3,1]
[1,4,5,3,2]
[2,3,5,4,1]
[1,3,2,5,4]
[3,5,1,2,4]
[3,1,5,4,2]
[2,5,3,1,4]
[5,2,1,3,4]
[5,3,4,1,2]
[1,5,2,4,3]
[5,1,4,2,3]
[5,4,3,2,1]
numbers = [12345,32415,34251,21435,43125,41352,24513,42153,45231,14532,23541,13254,35124,31542,25314,52134,53412,15243,51423,54321]
CPU time 3.325 seconds. Backtracks: 233455
20 的 seq 是最佳的，原因如下:在 1..5 的 120 个排列的集合中，有 60 个可能的三元组。每个数字由 3 个独特的三元组组成。因此，在这样的序列中不能有超过 60/3 = 20 个数字。
这是一个 20 的数字序列:
[12345,32451,43125,15423,23541,41532,52134,
24135,14352,31524,54321,25314,42513,51243,
34215,53412,45231,35142,21453,13254]
一些评论:
matrix_element/4用于连接Y中的三元组矩阵和 Z 中的数字. Z 中)，因此我们可以确保它们是不同的。 cp模块在更简单的实例(例如长度高达 16)上更快，但对于更大的实例(> 16)然后 sat往往会好得多。 该模型:
import sat, util.
go3 ?=>
nolog,
N = 5,
Ps = permutations(1..N),
PLen = Ps.len,
% Find the triplets
TripletsMap = new_map(),
foreach(P in Ps)
tri(P,Tri),
foreach(T in Tri) TripletsMap.put(T,1) end
end,
% Convert to numbers (123..543)
Triplets = [T[1]*100+T[2]*10+T[3] : T in keys(TripletsMap)].sort,
% length of sequence
member(M,20..20),
println(m=M),
% Indices of the selected permutation
X = new_list(M),
X :: 1..PLen,
% The triplets
Z = new_list(M*3),
Z :: Triplets,
% Y contains the "shortcuts" to the permutations
Y = new_array(M,5),
Y :: 1..N,
all_distinct(X),
all_distinct(Z),
X[1] #= 1, % symmetry breaking
% Fill Y
foreach(I in 1..M)
element(I,X,II),
foreach(K in 1..5)
matrix_element(Ps,II,K,Y[I,K])
end
end,
% Convert triplet list in Y <-> triplet number in Z
C = 1,
foreach(I in 1..M)
foreach(J in 1..3)
to_num([Y[I,J+K] : K in 0..2],10,Z[C]),
C := C+1
end
end,
Vars = Z ++ X ++ Y.vars,
solve($[constr,updown,split],Vars) % split (SAT)
PsX = [Ps[I] : I in X],
println(numbers=[[I.to_string : I in Ps[T]].join('').to_int : T in X]),
nl.
go3 => true.
tri(P,Tri) :- Tri=[P[K..K+2] : K in 1..3].
% converts a number Num to/from a list of integer
% List given a base Base
to_num(List, Base, Num) =>
Len = length(List),
Num #= sum([List[I]*Base**(Len-I) : I in 1..Len]).
更新 3 唉，节目在更新 2 仍然是错误的，因为它只选择了排列列表中较晚的数字。第三个版本使用
permutation(1..5,Next)所以所有数字都有一个变化要选择。go2 ?=>
Ps = permutations(1..5),
Forbidden = [],
gen(Ps,Forbidden,L),
println([[I.to_string : I in C].join('').to_int : C in L]),
println(len=L.len),
nl,
fail,
nl.
go2 => true.
%
% Create triplets (Tri) from the permutation P
%
tri(P,Tri) :- Tri=[P[K..K+2] : K in 1..3].
% list version
check2(Forbidden,Tri) =>
foreach(PP in Tri)
not membchk(PP,Forbidden)
end.
% list version
add_forbidden_triplets2(Forbidden,Triplets) = F =>
foreach(T in Triplets)
Forbidden := Forbidden ++ [T]
end,
F = Forbidden.
gen([],_Forbidden,[]).
gen(Ps,Forbidden,[Next|L]) :-
permutation(1..5,Next),
not membchk(Next,L),
tri(Next,Tri),
check2(Forbidden,Tri),
% Forbidden := add_forbidden_triplets2(Forbidden,Tri),
Forbidden2 = add_forbidden_triplets2(Forbidden,Tri), % better
Ps2 = [PP : PP in Ps, PP != Next],
gen(Ps2,Forbidden2,L).
gen(_Ps,Forbidden,[]) :-
not (permutation(1..5,Next),
tri(Next,Tri),
check2(Forbidden,Tri)).
[12345,12435,12534,13245,13425,13524,14235,14325,
14523,21543,24153,25413,35421,43152,45312,53214]
[12345,12435,12534,13245,13425,13524,14235,14325,
14523,21543,24153,25413,35421,43152,45321]
更新 2 : 中的版本更新 不完全正确(实际上是完全错误的)，因为我忘记将三元组添加到
Forbidden在循环中( add_forbidden_triplets(Forbidden, Triplets) 。程序更新如下。以 12345 开头的第一个解决方案是:
[12345,23145,13245,13425,34125,12435,24135,14235,
14325,43152,42153,45213,45312,53214]
len = 14
更新 :由于我第一次错过了说明中的一个重要约束，这里是基于第一种方法的调整程序。它产生一个长度为 107 的序列。基本的——也是相当简单的——变化是，禁止的三元组现在保存在哈希表
Forbidden 中。 .当没有任何可用号码时(当 Found 为假)时，序列结束。go ?=>
N = 5,
Ps = permutations(1..N),
select(P,Ps,Ps2),
L = [P],
tri(P,Triplets),
Forbidden = new_map(), % keep forbidden triplets in a hash table
add_forbidden_triplets(Forbidden, Triplets), % added in **Update2**
Found = true,
while(Found == true)
if select(NextP,Ps2,Ps3), tri(NextP,PTri), check(Forbidden,PTri) then
L := L ++ [NextP],
add_forbidden_triplets(Forbidden, PTri),
P := NextP,
Ps2 := Ps3
else
Found := false
end
end,
println([[I.to_string : I in C].join('').to_int : C in L]),
println(len=L.len),
nl,
% fail, % generate a new solution
nl.
go => true.
%
% Create triplets (Tri) from the permutation P
%
tri(P,Tri) :- Tri=[P[K..K+2] : K in 1..3].
%
% Check if Tri contain some forbidden triplet
%
check(Forbidden,Tri) =>
foreach(PP in Tri)
not Forbidden.has_key(PP)
end.
%
% Add triplets to Forbidden map
%
add_forbidden_triplets(Forbidden,Triplets) =>
foreach(T in Triplets)
Forbidden.put(T,1)
end.
[12345,23145,13245,31245,32145,32415,32451,13425,
1425,34125,34215,34251,31452,34152,12435,21435,
24135,24315,24351,14235,42135,42315,42351,14325,
41325,43125,43215,43251,14352,41352,43152,43512,
43521,12453,21453,24153,24513,24531,14253,41253,
42153,42513,42531,14523,41523,45213,45231,14532,
41532,45132,45312,45321,21354,23154,23514,23541,
13254,31254,32154,32514,32541,13524,31524,35124,
35214,35241,13542,31542,35142,35412,35421,12534,
21534,25134,25314,25341,52134,52314,15324,51324,
53124,53214,53241,15342,51342,53142,53412,53421,
12543,21543,25143,25413,25431,15243,51243,52143,
52413,52431,15423,51423,54213,54231,15432,51432,
54132,54312,54321]
len = 107
您的程序生成 106+1 个数字(使用初始数字为 12345)，而不是我下面的程序生成的所有 120 个数字。也许我错过了问题中的某些要求？顺便说一句，你不需要
solve/1在您的程序中，因为没有任何限制。以下是我的两种方法:两者都生成长度为 120 的序列，即所有数字都可以“链接”。两者都使用
permutations/1 (来自 util 模块)首先生成所有 120 个排列( 5!=120 )并不确定地选择一些剩余的排列(使用 select/3 )。使用 tri/2 来检查允许的后继者。生成所有三元组和 check/2检查是否有常见的三胞胎。由于我很早就发现所有数字都可以使用(除非我遗漏了一些东西)，因此程序完成时的控制是在没有可用排列时。这可能是我的方法的一个缺点。
import util.
% Using foreach loop
go ?=>
N = 5,
Ps = permutations(1..N),
select(P,Ps,Ps2), % pick the first number (i.e. 12345)
L := [P],
while(Ps2 != [])
tri(P,Forbidden),
select(NextP,Ps2,Ps3),
tri(NextP,PTri),
check(Forbidden,PTri),
L := L ++ [NextP],
P := NextP,
Ps2 := Ps3
end,
println([[I.to_string : I in C].join('').to_int : C in L]), % convert to number
nl.
go => true.
% Using genx/2 ("Prolog style")
go3 ?=>
Ps = permutations(1..5),
PLen = Ps.len,
println(plen=PLen),
genx(Ps,L),
println(len=L.len),
nl.
go3 => true.
% Create triplets (Tri) from the permutation P
tri(P,Tri) :- Tri=[P[K..K+2] : K in 1..3].
% Check if Tri contain some forbidden triplet
check(Forbidden,Tri) =>
foreach(PP in Tri)
not membchk(PP,Forbidden)
end.
% This is the same principal logic as used in go/0
% but in "Prolog style"
genx([],[]).
genx([P],[P]).
genx([P|Ps],[P|L]) :-
tri(P,Forbidden),
select(Next,Ps,Ps2), % pick a new available number
tri(Next,Tri),
check(Forbidden,Tri),
genx([Next|Ps2],L).
go/0 的输出(转换为数字):[12345,23145,21345,23415,13245,23451,31245,32145,32415,
13425,32451,31425,34125,34215,13452,34251,31452,34152,
34512,12435,34521,21435,24135,24315,14235,24351,41235,
42135,42315,14325,42351,41325,43125,43215,14352,43251,
41352,43152,43512,12453,43521,21453,24153,24513,14253,
24531,41253,42153,42513,14523,42531,41523,45123,45213,
14532,45231,41532,45132,45312,12354,45321,21354,23154,
23514,13254,23541,31254,32154,32514,13524,32541,31524,
35124,35214,13542,35241,31542,35142,35412,12534,35421,
21534,25134,25314,15234,25341,51234,52134,52314,15324,
52341,51324,53124,53214,15342,53241,51342,53142,53412,
12543,53421,21543,25143,25413,15243,25431,51243,52143,
52413,15423,52431,51423,54123,54213,15432,54231,51432,
54312,54132,54321]
关于list - "Generating Numbers"拼图，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/66127644/