将数字列表分组为固定的类似数字集(首选循环移动)

本文关键字：数字循环移动列表 | 更新日期: 2023-09-27 18:03:40

这可能更像是一个数学问题，但它最终会以代码的形式结束，所以这里是…

我有一组任意的数字，需要根据最接近的相似性将其分组为固定数量的组，由用户输入。集合的长度和数字的值都可以改变。

这是一个样本集…

1.2
1.3
0.5
0.7
1.3
1.4
0.7
0.9
1.1
1.3

这些项的顺序必须保持——最终的集合不能被重新排序，但是它可以被移动。例如，最后的数字可以变成第一个数字。这个集合被应用于一个圆，所以任何保持它的圆完整性的东西都是好的。

因此，如果用户要输入4作为所需的组数，我希望输出如下:

在更好的情况下，数字可以移动，以提高他们在组中的相似度。例如，通过将最后两个数字移到开头…

是否有一种算法可以解决这个问题?有什么建议告诉我该怎么做吗?

谢谢!

将数字列表分组为固定的类似数字集(首选循环移动)

您想要完成的是单链接集群的特殊情况，其中您的域是线性和圆形的。而不是距离矩阵，你将有一个距离数组。假设，距离函数是数组中数字之差的绝对值。

这段代码绝不是最简洁、写得最好的c#;但它确实突出了聚类算法的所有重要步骤:

简单距离计算

class Node
{
    public double Value { get; set; }
    public Node NextNode { get; set; }
    public Cluster Cluster { get; set; }
}
class Cluster : List<Node>
{
}
static void Main()
{
    double[] values = new double[]
    {
        1.2,
        1.3,
        0.5,
        0.7,
        1.3,
        1.4,
        0.7,
        0.9,
        1.1,
        1.3,
    };
    List<Node> nodes = new List<Node>();
    foreach (double value in values)
    {
        nodes.Add(new Node { Value = value });
    }
    // Put each node in a cluster by itself
    foreach (Node node in nodes)
    {
        node.Cluster = new Cluster();
        node.Cluster.Add(node);
    }
    // Create the cirular Linked List here
    // could probably use System.Collections in some way
    // but using simple self written classes for clarity
    for (int n = 1; n < nodes.Count; n++)
    {
        nodes[n - 1].NextNode = nodes[n];
    }
    nodes[nodes.Count - 1].NextNode = nodes[0];
    // Create a sorted distance list
    List<Node> sortedNodes = new List<Node>(nodes);
    sortedNodes.Sort((a, b) =>
        {
            var aDistToNext = Math.Abs(a.Value - a.NextNode.Value);
            var bDistToNext = Math.Abs(b.Value - b.NextNode.Value);
            return aDistToNext.CompareTo(bDistToNext);
        });
    // Register each node / cluster to the output list
    List<Cluster> clusters = new List<Cluster>();
    foreach (Node node in nodes)
    {
        clusters.Add(node.Cluster);
    }

    // Merge clusters until the desired number is reached
    int distIdx = 0;
    while (clusters.Count > 4)
    {
        // Obtain the two next closest nodes
        var nodeA = sortedNodes[distIdx];
        var nodeB = nodeA.NextNode;
        // Merge the nodes into a single cluster
        nodeA.Cluster.AddRange(nodeB.Cluster);
        // Remove the unnecessary cluster from output set
        clusters.Remove(nodeB.Cluster);
        nodeB.Cluster = nodeA.Cluster;
        distIdx++;
    }
    // Print the output results
    for (int n = 0; n < clusters.Count; n++)
    {
        Console.WriteLine("{0} =>", n);
        foreach (Node node in clusters[n])
        {
            Console.WriteLine("'t{0}", node.Value);
        }
    }
}

现在请注意，该算法按预期工作;然而，它给出了不同的结果比张贴在原来的问题。这种差异是由于节点间距离相等时的模糊连接。

输出:

高级距离计算

如果你想在连接到之前已经连接到上一个集群的节点之前优先考虑相似距离的节点，你可以修改排序算法，让未连接的节点优先考虑:

sortedNodes.Sort((a, b) =>
    {
        var aDistToNext = Math.Abs(a.Value - a.NextNode.Value);
        var bDistToNext = Math.Abs(b.Value - b.NextNode.Value);
        var result = aDistToNext.CompareTo(bDistToNext);
        if (result != 0)
            return result;
        else
        {
            var aNextDistToNext = Math.Abs(a.NextNode.Value - a.NextNode.NextNode.Value);
            var bNextDistToNext = Math.Abs(b.NextNode.Value - b.NextNode.NextNode.Value);
            return bNextDistToNext.CompareTo(aNextDistToNext);
        }
    });

给出期望的结果: