猜阵列

Question

问题作者：https://stats.ioinformatics.org/people/5815

给出了一个包含数字1, 2, 3, \ldots, n的隐藏排列的系统。你的任务是通过问系统一系列的问题来猜测这个排列。

每个问题包括向系统提供数字1, 2, 3, \ldots, n的排列。系统将响应在您的置换和隐藏排列之间的最长公共子序列长度。

子序列被定义为可以通过删除一些或没有元素而从另一个序列派生的序列，而不改变其余元素的顺序。例如，1, 2将被视为1, 3, 2的子序列。

您必须猜测隐藏的排列，最多使用n^2问题。如果超过此限制，系统将关闭您的程序。

您可以从下面两个中选择一个交互协议。

交互议定书1：

• 通过标准输入和标准输出与系统进行通信。
• 首先，系统为您提供数字n，即数组的长度。
• 要问系统，程序应该将数字1, 2, 3, \ldots, n的单个排列写到标准输出，然后是换行符。
• 系统将以一个整数响应，即程序提供的置换与隐藏置换之间最长的公共子序列的长度。
• 当您从系统接收到数字n时，您就完成了。

交互议定书2：

• 您可以使用一个数字n和一个黑匣子函数作为输入。黑箱函数f(user_input)计算user_input与系统所持有的置换之间最长的公共子序列，条件是user_input也是1, 2, 3, \ldots, n的置换。
• 当您从黑匣子函数接收到n时，您就完成了。
• 对黑匣子函数的调用构成对系统的询问，并计算到您的问题限制。

在这两种交互协议中，如果您愿意，可以通过传递0, 1, 2, 3, \ldots, n - 1的排列来进行通信。

收到n后，我能做什么？

系统停止监视您的程序。你的程序可能崩溃，永远循环或问额外的问题。你已经猜到了，恭喜。

样本交互作用：

Hidden permutation: 3 2 1
---
Input: 3

Output: 1 2 3

Input: 1

Output: 2 1 3

Input: 2

Output: 3 1 2

Input: 2

Output: 3 2 1

Input: 3

现在你已经成功地猜到了排列。

这是密码-高尔夫，最短的代码获胜。

Answer 1

皮斯，71字节

M?&GHeS[gGPHgPGH*qeGeHhgPGPH)0JK.pSQ#
=kh?tK.meShMr8SgLbKJK=ZE=KfqZgkTK

在网上试试！

非常慢，不会在TIO上运行n>5。老实说，我不知道如何证明这将总是猜测n^2中的排列，但假设您没有提出不可能的挑战，那么就会这样做。这里的大思想是，我们总是询问排列，这将提供最大的信息量。也就是说，我们保留一个潜在匹配的列表，每次我们询问一个置换，并接收最长的公共子序列的长度，我们过滤这个列表的排列符合信息。为了选择下一个要问的排列，我们查看所有的排列，并选择一个最能分割我们潜在的匹配项的排列。

解释

首先定义了“最长子序列的长度”函数。

M                                 # define g(G,H)
 ?&GH                        0    # if G or H are empty, return 0
     eS[                    )     # otherwise return the maximum of
        gGPH                      # g(G, H[:-1])
            gPGH                  # g(G[:-1], H)
                *qeGeHhgPGPH      # 1 + g(G[:-1], H[:-1]), but only if G[-1] == H[-1]

然后我们猜数组。

                                            # implicitly assign Q = eval(input())
JK.pSQ                                      # J = K = all possible permutations of [1, ..., Q]
      #                                     # loop infinitely until error
       =kh                                  # set (and print) k to the first element of
          ?tK                               # if K has more than one element
             .m           J                 #   elements of J which minimize lambda b
                      gLbK                  #     map K over g(_, b)
                 hMr8S                      #     get how many of each element there is
               eS                           #     maximum
                           K                # else: K
                            =ZE             # set Z to the next input
                               =K           # set K to
                                 f     K    # K filtered on lambda T
                                  qZgkT     # Z == g(k, T)

Answer 2

Wolfram语言(数学)，151个字节

修改自@Dominic的答复。

金色版，在网上试试！

Module[{g=Range[n],F=0,d,a,b,i,j},For[i=1,i<=n,i++,For[j=1,j<=n,j++,a=DeleteCases[g,i];b=Join[a[[1;;j-1]],{i},a[[-n+j;;]]];d=f[b];If[d>F,F=d;g=b];]];g]

Ungolfed版本

(* First define 'black-box' function *)
lcs[x_List, y_List] := Module[{m = Length[x], n = Length[y], L, i, j},
  L = ConstantArray[0, {m + 1, n + 1}];
  For[i = 0, i <= m, i++,
   For[j = 0, j <= n, j++,
    If[i == 0 || j == 0, L[[i + 1, j + 1]] = 0,
     If[x[[i]] == y[[j]], L[[i + 1, j + 1]] = L[[i, j]] + 1,
      L[[i + 1, j + 1]] = Max[L[[i, j + 1]], L[[i + 1, j]]]
      ]
     ]
    ]
   ];
  L[[m + 1, n + 1]]
  ]

blackBox[x_List] := Module[{n = 0},
  n = n + 1;
  Print["query ", n, " output: ", lcs[x, secret]];
  lcs[x, secret]
  ]

(* Now define our 'guess_the_array' function *)
guessTheArray[f_, n_] := Module[{g = Range[n], F = 0, d, a, b, i, j},
  For[i = 1, i <= n, i++,
   For[j = 1, j <= n, j++,
    a = DeleteCases[g, i];
    b = Join[a[[1 ;; j - 1]], {i}, a[[-n + j ;;]]];
    d = f[b];
    If[d > F, F = d; g = b];
    ]
   ];
  g
  ]

secret = RandomSample[Range[20]];
guess = guessTheArray[blackBox, Length[secret]]