2

我遇到了以下难题，无法在 Picat 中制定解决方案：

您将生成 5 位数字，其中每个数字都在其中，1..5并且与其他数字不同，约束条件是一个数字中使用的任何三个相邻数字都不能用于另一个数字。根据这个规则可以得到多少个不同的数字？

例如，如果我们生成数字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是可能的。

因此，一般来说，一些候选者似乎包含（并因此排除）其他候选者，而链的长度取决于我们是否选择这些候选者。

4

1 回答 1

2

这是带有更新 4和更新 5和更新 6中的模型的 Picat 模型：http : //hakank.org/picat/generating_numbers.pi

更新 6：如果不是从一开始就对问题的错误假设误入歧途，这可能是我会编写的约束模型......这是一种更直接的方法（从约束程序员的角度来看）并且不要使用permutations/1等。

它比Update 5稍慢（使用 sat 求解器为 3.7 秒，而Update 4模型为 3.3 秒）。然而，cp 求解器在这个模型上要慢得多。在上面引用的 Picat 程序中，它是 model 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.

第一个解决方案（SAT 3.7s）：

 [12345,35421,23154,25314,43512,32415,32541,12453,21534,14523,
  34251,14235,54312,45132,51432,52134,53214,34125,41352,15243]

更新 5这是一个更快的方法：找到第一个解决方案大约需要 3.3 秒，而更新 4中的方法需要 1 分钟 25 秒。

这里的方法是：

  • 预处理步骤：从Ps120个A排列（A[P1,P2] = 1Ps[P1]Ps[P2]
  • 模型：创建一个X长度为 120 的 0/1 列表，这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.8 秒（因此它仍然比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 的 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]

该模型使用 sat 求解器大约需要 1 分钟 25 分钟才能完成此序列。它比以前使用回溯的版本中“简单”地使用列表处理要复杂一些，这就是这些方法中获得最大长度序列的问题。

一些评论：

  • matrix_element/4用于连接Y矩阵中的三元组和 中的数字Z。
  • 三元组表示为数字 123..543（in 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 的序列。基本且非常简单的更改是禁止三元组现在保存在哈希表中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]
于 2021-02-11T06:07:53.770 回答