list - 从每个列表中最佳选择一个元素

Question

我遇到了一个老问题，你们 Mathematica/StackOverflow 的人可能会喜欢这个问题，对于后人来说，StackOverflow 上的这个问题似乎很有值(value)。

假设您有一个列表列表，并且您想从每个列表中选取一个元素并将它们放入一个新列表中，以便最大化与其下一个邻居相同的元素的数量。
换句话说，对于结果列表 l，最小化 Length@Split[l]。
换句话说，我们希望列表具有最少的相同连续元素的中断。

例如:

pick[{ {1,2,3}, {2,3}, {1}, {1,3,4}, {4,1} }]
 --> {    2,      2,    1,     1,      1   }

(或者 {3,3,1,1,1} 同样好。)

这是一个荒谬的蛮力解决方案:

pick[x_] := argMax[-Length@Split[#]&, Tuples[x]]

其中 argMax 如下所述:
posmax: like argmax but gives the position(s) of the element x for which f[x] is maximal

你能想出更好的办法吗？
传奇的卡尔沃尔为我解决了这个问题，我将在一周内揭示他的解决方案。

Answer 1

不是答案，而是此处提出的方法的比较。我生成了具有可变数量的子集的测试集，这个数字从 5 到 100 不等。每个测试集都是用这个代码生成的

Table[RandomSample[Range[10], RandomInteger[{1, 7}]], {rl}]

与 rl 涉及的子集数。

对于以这种方式生成的每个测试集，我让所有算法都做自己的事情。我用随机顺序运行的算法做了 10 次(使用相同的测试集)，以平衡顺序效应和随机后台进程对我的笔记本电脑的影响。这导致给定数据集的平均时间。对于每个 rl 长度，上述线使用 20 次，从中计算平均值(平均值)和标准偏差。

结果如下(水平子集数和垂直平均 AbsoluteTiming):



看来 Mr.Wizard 是(不太清楚)赢家。恭喜!

更新
根据 Timo 此处的要求，时序是可以从中选择的不同子集元素的数量以及每个子集中元素的最大数量的函数。根据以下代码行为固定数量的子集 (50) 生成数据集:

lst = Table[RandomSample[Range[ch], RandomInteger[{1, ch}]], {50}];

我还将为每个值尝试的数据集数量从 20 增加到 40。



这里有 5 个子集: