按照与原始数组的距离顺序排列所有可能数组的算法

Question

给出一个数组的数组。我想生成通过从输入中的第一个数组中选取第一个元素、第二个数组中的第二个元素等等形成的所有数组。

这些数组出现的顺序很重要。第一个数组应由输入中所有数组的第一个元素组成。下一个数组应使得距第一个数组的绝对距离之和应尽可能最小。生成的第三个数组应该具有与第一个数组的第二小的绝对距离之和，依此类推。

作为示例，请考虑以下输入。

[array([11,  9, 13,  7, 15,  6, 16,  4, 18,  2, 20,  0, 22]),
 array([4, 3, 5, 2, 6, 1, 7, 0, 8]),
 array([ 9,  7, 11,  6, 12,  5, 13,  4, 14,  2, 16,  0, 18])]

第一个数组应该是[11,4,9]（绝对差之和为0）。第二个数组应为 [11,3,9]（绝对差之和为 1）。第三个数组应该是 [9,4,9] 或 [11,4,7]（绝对差之和为 2），依此类推。

实现此目的的一种方法是通过简单的回溯生成所有可能的组合，然后按距第一个数组的绝对距离对它们进行排序。但这在记忆方面会非常低效。我不需要存储所有数组，只需要迭代它们。

简单的回溯方法将按以下顺序探索数组：第一优先级是将第一个元素保留为 11，第二优先级是将第二个元素保留为 4，依此类推。

---

编辑：为了计算两个数组 [a1, b1, c1] 和 [a2, b2, c2] 的绝对差之和，我们这样做：

d = |a1-b1| + |a2-b2| + |a3-b3|.

因此，如果第一个数组是 [11,4,9]，第二个数组是 [9,3,7]，那么绝对差是：

d = |11-9| + |4-3| + |9-7| = 5.

---

编辑：这是现实世界问题的一小部分，涉及将数据中心分成两组进行 A/B 测试。细节太长，稍后写一篇论文分享。请放心，这不是“学校作业”。

Answer 1

首先，按照与第一个元素的绝对差的顺序对输入数组进行排序。

在此转换之后，如果将每个输出表示为元组

(i,j,k)

，则第一个输出为

(0,0,0)

，之后的每个输出都可以通过获取一些前面的输出并递增

i

、

j

或

k

减一。

要按顺序获得输出：

1. 将

   (0,0,0)

   放入按距离排序的优先级队列中，并放入一个会记住您已添加到队列中的元组的集合中
2. 当优先级队列不为空时：
   1. 取出一个元素并记录输出
   2. 通过递增

      i

      、

      j

      和

      k

      生成 3 个新元组。
   3. 对于每个不超出输入数组边界且不存在于集合中的元素，将其添加到集合和优先级队列中。