java - 数组分区最小差异

Question

我需要根据 C#/Java 中的最小差异对数组数据进行分区。

Input: { A1, A2, B3, D4, C7, B12, A12, C14, D15, C22, A23, B25, A35, A36, D37 }

例如

• B3、D4 之间的差异 = |3 - 4| = 1

• A23、B25 之间的差异 = |23 - 25| = 2

• D4、C7 之间的差异 = |4 - 7| = 3

• B12、A12 之间的差异 = |12 - 12| = 0

规则是:

• 对于每个组，字母不能重复

• 对于每个组，它可以包含 1 - 4 个元素

• 元素之间的差异必须是 <= 3

---

Output: { A1 },{ A2, B3, D4, C7 },{ B12, A12, C14, D15 },{ C22, A23, B25 },{ A35 },{ A36, D37 }

Answer 1

在 Dyalog APL 中编码只用了 10 分钟并行数组处理语言，但是写答案花了我2个小时。我根本不会提交任何代码，以免打破问题中的语言限制，但我会尝试使用数据和一些伪代码来阐明下面的原则。

假设论证有固定顺序，则有512种可能的解法，如下:

┌──────────┬─┬─┬──┬──┬───┬───┬──┬──┬──┬──┬─────┐
│Partitions│6│7│8 │9 │10 │11 │12│13│14│15│Total│
├──────────┼─┼─┼──┼──┼───┼───┼──┼──┼──┼──┼─────┤
│Solutions │1│9│36│84│126│126│84│36│9 │1 │512  │
└──────────┴─┴─┴──┴──┴───┴───┴──┴──┴──┴──┴─────┘

最小分区 (6) 的解决方案是:

┌──┬───────────┬───────────────┬───────────┬───┬───────┐
│A1│A2 B3 D4 C7│B12 A12 C14 D15│C22 A23 B25│A35│A36 D37│
└──┴───────────┴───────────────┴───────────┴───┴───────┘

接下来的(有 7 个分区)是:

┌──┬───────────┬───────────────┬───────────────┬───────────┬───┬───────┐
│A1│A2 B3 D4 C7│B12 A12 C14 D15│C22 A23 B25    │A35        │A36│D37    │
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤
│A1│A2 B3 D4 C7│B12 A12 C14 D15│C22 A23        │B25        │A35│A36 D37│
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤
│A1│A2 B3 D4 C7│B12 A12 C14 D15│C22            │A23 B25    │A35│A36 D37│
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤
│A1│A2 B3 D4 C7│B12 A12 C14    │D15            │C22 A23 B25│A35│A36 D37│
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤
│A1│A2 B3 D4 C7│B12 A12        │C14 D15        │C22 A23 B25│A35│A36 D37│
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤
│A1│A2 B3 D4 C7│B12            │A12 C14 D15    │C22 A23 B25│A35│A36 D37│
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤
│A1│A2 B3 D4   │C7             │B12 A12 C14 D15│C22 A23 B25│A35│A36 D37│
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤
│A1│A2 B3      │D4 C7          │B12 A12 C14 D15│C22 A23 B25│A35│A36 D37│
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤
│A1│A2         │B3 D4 C7       │B12 A12 C14 D15│C22 A23 B25│A35│A36 D37│
└──┴───────────┴───────────────┴───────────────┴───────────┴───┴───────┘

最后一个(分为15个分区)自然是:

┌──┬──┬──┬──┬──┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│A1│A2│B3│D4│C7│B12│A12│C14│D15│C22│A23│B25│A35│A36│D37│
└──┴──┴──┴──┴──┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

解决此问题的最好、最安全的方法是使用蛮力并遍历所有可能性。首先，您需要调整使用零和一来指示分区位置的原则。由于参数中有 15 个元素，我们使用 15 长度的二进制 vector 来完成这项工作。示例:

(1 0 0 1 0 0 0 0 1 0 0 1 0 0 0) partition 'stackoverflowex'

暗示/应返回 4 个分区:

┌───┬─────┬───┬────┐
│sta│ckove│rfl│owex│
└───┴─────┴───┴────┘

您还可以划分另一个 15 长度的 boolean vector :

(1 0 0 1 0 0 0 0 1 0 0 1 0 0 0) partition (1 1 0 0 1 1 0 1 0 0 0 1 1 0 0)

应返回:

┌─────┬─────────┬─────┬───────┐
│1 1 0│0 1 1 0 1│0 0 0│1 1 0 0│
└─────┴─────────┴─────┴───────┘

并且您可以计算每个分区中的总和。上面的那个会返回:

┌─┬─┬─┬─┐
│2│3│0│2│
└─┴─┴─┴─┘

要解决您的问题，您必须生成所有可能的分割 vector 。做起来比说起来简单。您只需要这两者之间的所有分区 vector :

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 // This would create 1 single, big partition
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 // This would create 15 small partitions

这些是什么？非常简单，它们是 16384 和 32767 的 2 进制(二进制)表示。您必须简单地遍历 16384 和 32767 之间的所有数字(包括两者)，将每个数字转换为 2 进制，将您的数据，并查看当前分区是否可以接受(= 满足您的标准，例如“对于每个组，字母不能重复”)。转换区间内的所有数字将覆盖所有可能的分区 - 零和一的任何可能组合都在其中。计算只需要几分之一秒。

伪:

// The character part of the argument: 15-length vector of characters:
Chars = "A","A","B","D","C","B","A","C","D","C","A","B","A","A","D" 

// From that, extract the locations of the unique characters:
CharsA = 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0 // Where Chars == A
CharsB = 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0 // Where Chars == B
CharsC = 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0 // Where Chars == C
CharsD = 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1 // Where Chars == D

// The numeric part of the argument: 15-length vector of numbers:
// Btw, is this about lottery... hmmm
Nums = 1, 2, 3, 4, 7, 12, 12, 14, 15, 22, 23, 25, 35, 36, 37

:For Number :In [all numbers between 16384 and 32767]

    Base2 = [2-base of Number] // 20123 would give: 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1

    // Test 1: "For each group, it can contains 1 - 4 elements"
        [using Base2, partition the partition vector Base2 itself;
         bail out if any partition length exceeds 4]

    // Test 2: "Difference between element must be <= 3"
        [using Base2, partition Nums; 
         check differences inside each partition; 
         bail out if bigger than 3 anywhere]

    // Test 3: "For each group, letter cannot be repeated"
        [using Base2, partition CharsA, CharsB, CharsC, CharsD (each in turn);
         count number of ones in each partition;
         bail out if exceeds 1 anywhere (meaning a character occurs more than once)]

    // If we still are here, this partition Number is ACCEPTABLE
    [add Number to a list, or do a parallel boolean marking 1 for Number]

:End

至此，512 个号码满足了指定的条件，而其余号码在某些测试中未通过。纯属巧合，它们是 512，这对我们程序员来说是一个特殊的数字。假设您现在在名为 Result 的变量中有 512 个可接受的数字。现在您需要对其进行排序，方法是解析每个结果中的分区数(= 二进制表示中的分区数)。为此，请再次将结果中的每个数字转换为基数 2，然后对每个数字中的个数进行计数并求和，然后按该和升序排序。最小的总和为 6，并且只出现一次 - 这是此答案顶部提到的分区。

它的值为 25126，它的 2-base 是

1 1 0 0 0 1 0 0 0 1 0 0 1 1 0