给出一个数组数组作为输入（具有整数元素；例如 [[1,2],[3,4]]）。我想生成通过从输入中的第一个数组中选取第一个元素、第二个数组中的第二个元素等来形成的所有数组。换句话说，对从输入二维数组的笛卡尔积生成的元组进行排序。
对于上面的输入，生成的输出将是：[1,3]、[2,3]、[1,4] 和 [2,4]。
显然，此类生成的数组的总数是有限的。其中每一个都应该只出现一次。
这些数组出现的顺序很重要。第一个数组应由输入中所有数组的第一个元素组成（因此上面的玩具示例中为 [1,3]）。下一个数组应使得距第一个数组的绝对距离之和应尽可能最小。生成的第三个数组应该具有与第一个数组的第二小的绝对距离之和，依此类推。这个“绝对差之和”基本上是阵列之间的曼哈顿距离或出租车距离。
作为另一个示例，请考虑下面的输入。
[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] 或 [11,5,9]（绝对差之和为 1）。第三个数组应该是 [11,3,9] 和 [11,5,9] 中不是第二个的那个。那么 [9,4,9] 或 [11,4,7] 应该是第四个（绝对差之和为 2），依此类推。
实现此目的的一种方法是通过简单的回溯生成所有可能的组合，然后按距第一个数组的绝对距离对它们进行排序。但这在记忆方面会非常低效。我不需要存储所有数组，只需要迭代它们。
简单的回溯方法将按以下顺序探索数组：第一优先级是将第一个元素保留为 11，第二优先级是将第二个元素保留为 4，依此类推。
d = |a1-a2| + |b1-b2| + |c1-c2|.
因此，如果第一个数组是 [11,4,9]，第二个数组是 [9,3,7]，那么绝对差是：
d = |11-9| + |4-3| + |9-7| = 5.
注意这个问题和排序非常相似。正如排序的解释是明确定义的一样，这个问题也是如此，因为它是同一件事。
在此转换之后，如果将每个输出表示为元组
(i,j,k)
，则第一个输出为
(0,0,0)，之后的每个输出都可以通过获取一些前面的输出并递增
i、
j或
k减一。要按顺序获得输出：
(0,0,0)放入按距离排序的优先级队列中，并放入一个会记住您已添加到队列中的元组的集合中
i、
j和
k生成 3 个新元组。