相同元素不能位于匹配位置的两个列表的组合

Question

鉴于几局剪刀石头布的玩法（乱序）和没有平局的事实，我想找出可能的顺序。（来自 Hubert Phillips 的谜题。）

所以我有两个看起来像 [Rock, Rock, Scissors...].

的列表

这是在 Python 中找到一个解决方案的方法：

one, two = 'rrrssssssp', 'rrsssspppp'

while True in [t[0] == t[1] for t in zip(one, two)]:
    one = one[1:] + one[0]

print(one, two)

（并且通过对该方法进行更长时间的迭代，似乎只有一种可能的解决方案。）

Prolog 中似乎应该有更优雅的方法来解决这个问题。是这样的吗？

% results.pl
one([r, r, r, s, s, s, s, s, s, p]).
two([r, r, s, s, s, s, p, p, p, p]).

ordered_results(L) :-
        findall((I,J), (member(I, one), member(J, one), I \== J), []).

?- [results].
?- ordered_results(one, two).

但这只是 returns 正确

Answer 1

我们只需要重新订购其中之一：

one_two_ordered(X,Y):-
  one(X),
  two(B),
  permutation(B,Y),
  maplist(\=,X,Y).

这会产生很多很多答案。

如果你想要效率，你需要将最后两个目标融合在一起。或者我们可以尝试使用 dif/2 并切换执行顺序，让 permutation 的选择 受制于 的约束：

one_two_(X,Y):-
  one(X),
  maplist(dif,X,Y),
  two(B),
  permutation(B,Y).

这现在在 689 次推理后找到第一个解决方案，在 SWI Prolog 中，而不是 7,677,050第一版推论

Answer 2

@Will Ness 的解决方案被修改为只考虑旋转，就像在 Python 版本中所做的那样（只要 one/1 和 two/1 中的值是已排序）。

one([r, r, r, s, s, s, s, s, s, p]).
two([r, r, s, s, s, s, p, p, p, p]).

rotation(X, Y) :-
    append(A, B, X),
    append(B, A, Y).

one_two_ordered(X,Y):-
  one(X),
  two(B),
  rotation(B,Y),
  maplist(\=,X,Y).

Answer 3

这个谜语没有正确的解决方案是不直观的，然后我编写了一个求解器，超出了你的问题：

/*  File:    rock_paper_scissor.pl
    Author:  Carlo,,,
    Created: Sep 20 2021
    Purpose: 
*/

:- module(rock_paper_scissor,
          [puzzle/2]).

:- set_prolog_flag(double_quotes, chars).

puzzle(WhoWins, ByHowMuch) :-
    count_wins("rrrssssssp", "rrsssspppp", WinAdam, WinEve),
    (   WinAdam > WinEve
    ->  WhoWins = adam, ByHowMuch is WinAdam - WinEve
    ;   WhoWins = eve , ByHowMuch is WinEve - WinAdam
    ).

win(r,s).
win(p,r).
win(s,p).

count_wins([A|As], Es, WinAdam, WinEve) :-
    select(E,Es,Er),
    E\=A,
    count_wins(As, Er, WinAdam1, WinEve1),
    (   win(A,E)
    ->  WinAdam is WinAdam1+1, WinEve is WinEve1
    ;   WinAdam is WinAdam1, WinEve is WinEve1+1
    ).
count_wins([], [], 0, 0).

产量

?- setof(W-N,puzzle(W,N),L).
L = [adam-4].

交换亚当和夏娃的移动（即 count_wins("rrsssspppp", "rrrssssssp", WinAdam, WinEve),）我们得到 [eve-4]。看来是对的...

相同元素不能位于匹配位置的两个列表的组合

Combinations of two lists where same element can't be in matching position

prolog