项链分裂问题

Question

背景

我的灵感来自3个Blue1Brown的S最近的视频关于项链分裂问题 (或者他称之为偷来的项链问题)及其与Borsuk-Ulam定理的关系。

在这个问题上，两个小偷偷了一条由几种不同类型的珠宝组成的贵重项链。每种宝石的数量都是偶数，窃贼希望在两种宝石之间平均分配每一种宝石。问题是，他们必须将项链分割成一定数量的连续段，并在它们之间分配这些段。

下面是一个有四种宝石类型的示例，分别表示S、E、D和R (分别用于蓝宝石、绿宝石、钻石和红宝石)。让我们假设这条项链如下：

[S,S,S,E,S,D,E,R,S,R,E,S,S,S,D,R,E,E,R,E,D,E,R,R,D,E,E,E]

有8蓝宝石，10祖母绿，4钻石和6红宝石。我们可以把项链分成以下几个部分：

[[S],[S],[S,E,S,D,E,R,S],[R,E,S,S,S,D,R,E,E,R,E,D,E],[R,R,D,E,E,E]]

然后，如果我们把第一、第三和第五段交给一个小偷，把第二和第四段交给另一个小偷，每一段最后都会得到4蓝宝石、5翡翠、2钻石和3红宝石：

[S],    [S,E,S,D,E,R,S],                            [R,R,D,E,E,E]
    [S],                [R,E,S,S,S,D,R,E,E,R,E,D,E],

使用0-indexing，这些削减发生在索引[1,2,9,22]上。

目标

事实证明，这种公平的划分总是可以使用最多的n裁剪，其中n是珠宝类型的数量。您的任务是编写一个完整的程序或函数，它以项链为输入，并输出最小的这样的分割(最少的切割次数)。

输入

输入可以采用任何方便的格式。项链应该是珠宝序列，而不是别的；例如，一个整数列表，带有代表宝石类型的键的字典，以及作为索引列表的值。你可以选择包括项链的长度或不同类型的宝石数量，但你不应该接受任何其他输入。

您可以假设输入项链是有效的。你不需要处理一个特定类型的珠宝数量奇数或项链是空的情况。

输出

同样，输出可以采用任何方便的格式；例如，分段列表、切割位置列表、带有表示两个窃贼的键的字典以及表示分段列表的值等。分段可以用它们的起始索引、结束索引、连续索引列表、珠宝列表、长度等来表示。您可以使用0-或1索引。如果排序对您的格式没有意义，那么您的输出可以是任意顺序的。以下是以上几种不同格式的输出：

list of segments: [[S],[S],[S,E,S,D,E,R,S],[R,E,S,S,S,D,R,E,E,R,E,D,E],[R,R,D,E,E,E]]
list of cuts:     [1,2,9,22]
list of lengths:  [1,1,7,13,6]
dictionary:       {'thief1' : [(R,R,D,E,E,E),(S),(S,E,S,D,E,R,S)], 'thief2' : [(S),(R,E,S,S,S,D,R,E,E,R,E,D,E)]}

注意，在片段列表(片段在小偷之间交替)和长度列表(为了识别片段)中，顺序很重要，但在裁剪列表或字典中则不是这样。编辑:格雷格·马丁( Greg )指出，这些都不是有效的输出，因为公平的分割可以在两次切割中获得。

测试用例

[1,2,1,2,1,3,1,3,3,2,2,3] -> [[1,2,1],[2,1,3,1],[3,3,2],[2,3]]
[1,1,1,1,2,2,3,3,3,3,3,3] -> [[1,1],[1,1,2],[2,3,3,3],[3,3,3]]
[1,1,1,1,1,1,1,1,1,1,1,1] -> [[1,1,1,1,1,1],[1,1,1,1,1,1]]
[1,1,1,1,2,3,4,2,3,4,2,2] -> [[1,1],[1,1,2,3,4,2],[3,4,2,2]]

Notes

1. 标准漏洞是禁止的。
2. 这是密码-高尔夫；最短的答案(以字节为单位)获胜。

Answer 1

布氏对数，13字节

~c.ġ₂z₁Ċcᵐoᵛ∧

在网上试试！

注意: metapredicate ᵛ比这个挑战新。

解释

~c.ġ₂z₁Ċcᵐoᵛ∧  Input is a list, say L = [1,2,2,2,1,2,3,3]
~c.            Output is a partition of the input: [[1,2,2],[2,1,2],[3],[3]]
  .ġ₂          Split the output into chunks of length 2: [[[1,2,2],[2,1,2]],[[3],[3]]]
     z₁        Zip (transpose) the chunks: [[[1,2,2],[3]],[[2,1,2],[3]]]
       Ċ       This is a 2-element list (forbid the trivial partition).
        cᵐ     Concatenate both: [[1,2,2,3],[2,1,2,3]]
          oᵛ   If you sort both lists, they are equal.
            ∧  Don't unify with the output.

分区是按块数量的递增顺序枚举的，因此结果将尽可能少块。

Answer 2

Mathematica，118个字节

差点打败果冻..。只差1次;)

SelectFirst[l_±c_:=Append[-#±Most@c,#2]&@@l~TakeDrop~Last@c;l_±{}:={l};i=#;(i±#)&/@Range@#2~Subsets~#3,Tr[Tr/@#]==0&]&

采用三个参数的纯函数:项链，作为诸如{A, A, A, A, B, C, D, B, C, D, B, B}之类的标记的列表；项链的长度；以及不同的宝石次数。它返回表单{{A, A}, {-A, -A, -B, -C, -D, -B}, {C, D, B, B}}中的子列表列表，其中没有负号的标记传递给一个小偷，带有负号的标记传递给另一个小偷。(虽然这是冗余信息，但是算法会导致这种表示，而删除负号将花费几个字节。)

首先，我们必须实现一个函数，该函数接受一个列表和一组n裁剪位置，并返回通过在这些n裁剪位置上剪切输入列表而获得的n+1子列表；二进制infix操作符±用于此目的，并通过l_±c_:=Append[-#±Most@c,#2]&@@l~TakeDrop~Last@c;l_±{}:={l};递归定义。由于Append后面的负号，结果是子列表交替地做和不将负号附加到每个标记上。

然后使用Range@#2~Subsets~#3生成长度最多为珠宝类型数的所有可能的裁剪位置集，并使用i=#;(i±#)&/@依次将±运算符(输入珠宝列表)应用于每个切割位置集。

最后，SelectFirst[...,Tr[Tr/@#]==0&]&挑选出第一个得到的项链部门，这是公平的。它是通过将所有子列表中的所有元素加起来来做到这一点的。Mathematica非常明智，可以以明显的方式取消每个标记的正负副本。

Answer 3

05AB1E，14 字节数

.œ¨ʒ2ôζε˜{}Ë}¤

在网上试试或验证所有测试用例.

解释：

.œ                # All partitions of the (implicit) input
                  #  i.e. [2,3,2,1,3,1]
                  #   → [[[2],[3],[2],[1],[3],[1]],[[2],[3],[2],[1],[3,1]],
                  #      ...,[[2,3,2,1,3,1]]]
  ¨               # Remove the last one
   ʒ        }     # Filter this list by:
    2ô            # Split it into parts of 2
                  #  i.e. [[2,3],[2],[1],[3,1]] → [[[2,3],[2]],[[1],[3,1]]]
                  #  i.e. [[2,3,2],[1,3],[1]] → [[[2,3,2],[1,3]],[[1]]]
      ζ           # Swap rows and columns (using space as filler if necessary)
                  #  i.e. [[[2,3],[2]],[[1],[3,1]]] → [[[2,3],[1]],[[2],[3,1]]]
                  #  i.e. [[[2,3,2],[1,3]],[[1]]] → [[[2,3,2],[1]],[[1,3]," "]]
       ε  }       # Map each inner list to:
        ˜         # Flatten the list
                  #  i.e. [[2,3],[1]] → [2,3,1]
                  #  i.e. [[1,3]," "] → [1,3," "]
         {        # Sort the list
                  #  i.e. [2,3,1] → [1,2,3]
                  #  i.e. [1,3," "] → [1,3," "]
           Ë      # Check if both sorted lists are equal
                  # (if not, remove them from the partitions)
             ¤    # After filtering, take the last one as result (and output implicitly)
                  #  i.e. [[[2],[3,2],[1,3],[1]],[[2,3],[2],[1],[3,1]]]
                  #   → [[2,3],[2],[1],[3,1]]