"Generating Numbers" 拼图
"Generating Numbers" Puzzle
我遇到了以下难题，无法在 Picat 中制定解决方案：
You will generate 5-digit numbers, where each digit is in 1..5 and 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]
我们看到 valid/can 附加到此链的三个候选者是：
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是可能的。
所以似乎一般来说一些候选人包含（因此排除）其他人，链的长度取决于我们是否选择这些候选人。
这是 更新 4 和 更新 5 和 更新 6[=151= 中的模型的 Picat 模型]: http://hakank.org/picat/generating_numbers.pi
更新 6：如果没有从一开始就对问题做出错误的假设而误入歧途，这可能是我会编写的约束模型......这是一种更直接的方法（从约束程序员的角度来看）并且不要使用 permutations/1 等
它比 Update 5 稍慢（使用 sat 求解器为 3.7s vs Update 4 模型为 3.3s）。然而，cp 求解器在此模型上要慢得多。
在上面引用的 Picat 程序中，它的模型是 go3/0。 （最快的型号是 go/0。）
方法：
- 创建一个域为 1..5 的 20 x 5 矩阵
- 确保每一行的数字不同
- 并在循环中确保没有公共三元组
型号：
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.
第一个解决方案（3.7s with sat）：
[12345,35421,23154,25314,43512,32415,32541,12453,21534,14523,
34251,14235,54312,45132,51432,52134,53214,34125,41352,15243]
更新 5 这是一个更快的方法：找到第一个解决方案大约需要 3.3 秒，而 更新 4[=151= 中的方法需要 1 分钟 25 秒].
这里的做法是：
- 预处理步骤：从 120 个排列 (
Ps) 构建一个 120 x 120 矩阵 A 的 0/1 其中 A[P1,P2] = 1 表示 Ps[P1] 和 Ps[P2] 是兼容的，即它们没有共同的三元组
- 模型：创建一个长度为 120 的 0/1 列表
X，其中 X[I] = 1 表示排列 Ps[I] 应该在序列中（或者更确切地说是“集合”，因为排列的顺序没有区别）。
- 在 foreach 循环中，
X[I]*X[J] #= 1 #=> A[I,J] 是一种“奇怪”的说法，表示 X[I] 和 X[J] 都应该在序列中 if A[I,J] #= 1.
cp 求解器大约需要 3.3 秒才能找到第一个长度为 20 的解。此模型的 sat 求解器较慢：4.8s（因此它仍然比 Update 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
更新 4 正如评论中提到的，这是一个找到长度为 20 的序列的约束模型。
20 的序列是最优的，推理如下：在 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]
这个使用 sat 求解器的模型需要大约 1 分钟 25 才能完成这个序列。它比以前版本中使用回溯的列表处理的“简单”使用更加复杂，这就是这些方法中获得最大长度序列的问题。
一些评论：
matrix_element/4用于连接Y矩阵中的三元组和Z中的数字。- 三胞胎表示为数字 123..543（在
Z 中），因此我们可以确保它们是不同的。
- 像往常一样，Picat 的
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]).
而且我仍然认为有一些算法可以立即解决这个问题...
Update3 唉，Update2 中的程序仍然是错误的，因为它只选取了排列列表中靠后的数字。第三个版本使用 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)).
第一个解的长度为 16:
[12345,12435,12534,13245,13425,13524,14235,14325,
14523,21543,24153,25413,35421,43152,45312,53214]
下一个解决方案（通过回溯）是 - 但是 - 长度为 15:
[12345,12435,12534,13245,13425,13524,14235,14325,
14523,21543,24153,25413,35421,43152,45321]
所以我 - 仍然 - 不确定 16 是否是最大长度。
Update2: Update 中的版本不完全正确（实际上是完全错误的），因为我忘了添加三元组到Forbidden在循环中（add_forbidden_triplets(Forbidden, Triplets)。下面更新程序。
第一个以12345开头的解是：
[12345,23145,13245,13425,34125,12435,24135,14235,
14325,43152,42153,45213,45312,53214]
len = 14
现在它变得有趣了，因为其他序列的长度（具有不同的起始编号）大约为 12..17 个数字。这是违反直觉的，因为这些东西应该是对称的，不是吗？
更新：由于我第一次错过了说明中的一个重要约束，这里是基于第一种方法的调整程序。它产生一个长度为 107 的序列。基本且非常简单的变化是禁用的三元组现在保存在散列 table 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 非确定性的一些排列（使用 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]
我遇到了以下难题，无法在 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]
我们看到 valid/can 附加到此链的三个候选者是：
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是可能的。
所以似乎一般来说一些候选人包含（因此排除）其他人，链的长度取决于我们是否选择这些候选人。
这是 更新 4 和 更新 5 和 更新 6[=151= 中的模型的 Picat 模型]: http://hakank.org/picat/generating_numbers.pi
更新 6：如果没有从一开始就对问题做出错误的假设而误入歧途，这可能是我会编写的约束模型......这是一种更直接的方法（从约束程序员的角度来看）并且不要使用 permutations/1 等
它比 Update 5 稍慢（使用 sat 求解器为 3.7s vs Update 4 模型为 3.3s）。然而，cp 求解器在此模型上要慢得多。
在上面引用的 Picat 程序中，它的模型是 go3/0。 （最快的型号是 go/0。）
方法：
- 创建一个域为 1..5 的 20 x 5 矩阵
- 确保每一行的数字不同
- 并在循环中确保没有公共三元组
型号：
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.
第一个解决方案（3.7s with sat）：
[12345,35421,23154,25314,43512,32415,32541,12453,21534,14523,
34251,14235,54312,45132,51432,52134,53214,34125,41352,15243]
更新 5 这是一个更快的方法：找到第一个解决方案大约需要 3.3 秒，而 更新 4[=151= 中的方法需要 1 分钟 25 秒].
这里的做法是：
- 预处理步骤：从 120 个排列 (
Ps) 构建一个 120 x 120 矩阵A的 0/1 其中A[P1,P2] = 1表示Ps[P1]和Ps[P2]是兼容的，即它们没有共同的三元组 - 模型：创建一个长度为 120 的 0/1 列表
X，其中X[I] = 1表示排列Ps[I]应该在序列中（或者更确切地说是“集合”，因为排列的顺序没有区别）。 - 在 foreach 循环中，
X[I]*X[J] #= 1 #=> A[I,J]是一种“奇怪”的说法，表示X[I]和X[J]都应该在序列中 ifA[I,J] #= 1.
cp 求解器大约需要 3.3 秒才能找到第一个长度为 20 的解。此模型的 sat 求解器较慢：4.8s（因此它仍然比 Update 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
更新 4 正如评论中提到的，这是一个找到长度为 20 的序列的约束模型。
20 的序列是最优的，推理如下：在 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]
这个使用 sat 求解器的模型需要大约 1 分钟 25 才能完成这个序列。它比以前版本中使用回溯的列表处理的“简单”使用更加复杂，这就是这些方法中获得最大长度序列的问题。
一些评论：
matrix_element/4用于连接Y矩阵中的三元组和Z中的数字。- 三胞胎表示为数字 123..543（在
Z中），因此我们可以确保它们是不同的。 - 像往常一样，Picat 的
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]).
而且我仍然认为有一些算法可以立即解决这个问题...
Update3 唉，Update2 中的程序仍然是错误的，因为它只选取了排列列表中靠后的数字。第三个版本使用 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)).
第一个解的长度为 16:
[12345,12435,12534,13245,13425,13524,14235,14325,
14523,21543,24153,25413,35421,43152,45312,53214]
下一个解决方案（通过回溯）是 - 但是 - 长度为 15:
[12345,12435,12534,13245,13425,13524,14235,14325,
14523,21543,24153,25413,35421,43152,45321]
所以我 - 仍然 - 不确定 16 是否是最大长度。
Update2: Update 中的版本不完全正确（实际上是完全错误的），因为我忘了添加三元组到Forbidden在循环中（add_forbidden_triplets(Forbidden, Triplets)。下面更新程序。
第一个以12345开头的解是：
[12345,23145,13245,13425,34125,12435,24135,14235,
14325,43152,42153,45213,45312,53214]
len = 14
现在它变得有趣了，因为其他序列的长度（具有不同的起始编号）大约为 12..17 个数字。这是违反直觉的，因为这些东西应该是对称的，不是吗？
更新：由于我第一次错过了说明中的一个重要约束，这里是基于第一种方法的调整程序。它产生一个长度为 107 的序列。基本且非常简单的变化是禁用的三元组现在保存在散列 table 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 非确定性的一些排列（使用 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]