阵列分区最小差异

我需要根据 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 }

用 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 长度的二进制向量来完成这项工作。例：

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

暗示/应返回 4 个分区：

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

您还可以对另一个 15 长度的布尔向量进行分区：

(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│
└─────┴─────────┴─────┴───────┘

您可以计算每个分区中的 1 之和。上面的那个将返回：

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

要解决您的问题，您必须生成所有可能的分区向量。这比说起来容易。您只需要这两者之间的所有分区向量：

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(之间的所有数字，将每个数字转换为 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 Number满足指定的条件，而其余的在某些测试中失败。纯属巧合，他们是512，这对我们编码人员来说是一个特殊的数字。假设您现在在名为 Result 的变量中有 512 个可接受的数字。现在，您需要通过解析每个结果中的分区数(= 二进制表示中的分区数(对其进行排序。为此，再次将 Result 中的每个数字转换为基数 2，然后对每个数字中的 1 数进行计数和求和，并按该总和升序排序。最小的总和将是 6，它只出现一次 - 这是这个答案顶部提到的分区。

它的值是 25126，其 2 基数是

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

您提供的输入包含多个解决方案。大概在15个左右(A1-A2，A35-A36，D4-C7是改变解决方案的东西(。由于当我问你想要哪个解决方案时你没有回答，所以我写了这段代码，它将为这个问题提供一个(最简单的("解决方案"=(

static string[][] Solve(string[] input)
{
    List<string> myList = new List<string>(input);
    List<string[]> groups = new List<string[]>();
    while (myList.Count > 0)
    {
        string currentStr = myList[0];
        int currentNum = int.Parse(currentStr.Substring(1));
        List<string> lessThan4 = new List<string>();
        lessThan4.Add(currentStr);
        for (int i = 1; i < myList.Count; i++)
        {
            if (Math.Abs(currentNum - int.Parse(myList[i].Substring(1))) < 4)
            {
                // Add it to the list only if there's not the same letter in there
                if (!lessThan4.Where(a => a.Contains(myList[i].Substring(0, 1))).Any())
                {
                    lessThan4.Add(myList[i]);
                }
            }
        }
        lessThan4.Sort();
        groups.Add(lessThan4.ToArray());
        myList = myList.Except(lessThan4).ToList();
    }
    return groups.ToArray();
}

您可以使用以下内容对其进行测试：

string[] input = new string[] { "A2", "B3", "D4", "C7", "B12", "A12", "C14", "D15", "C22", "A23", "B25", "A35", "A36", "D37" };
Solve(input);

在这种情况下，Solve(( 的输出将是：

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

重要提示：此代码假定输入中的字符串是唯一的。

相关内容

最新更新

热门标签：