4

我想知道是否有一种甜蜜的方式可以在 LINQ 或其他东西中执行此操作，但我试图将字母表中的字母最均匀地分布在 X 部分中，其中 X 是整数 > 0 && <= 26。例如这里可能有一些可能的输出。

  • X = 1 : 26 的 1 个分区
  • X = 2 : 13 的 2 个分区
  • X = 3 : 2 个分区 9 和 1 个分区 8
  • ETC....

最终，我不希望有任何最终没有得到至少一个的分区，我的目标是让它们实现最均匀的分布，即分区大小之间的差异范围尽可能小。

这是我最初尝试的代码：

char[] alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".ToCharArray();
int pieces = (int)Math.Round((double)alphabet.Count() / numberOfParts); 
for (int i = 0; i < numberOfParts.Count; ++i) {
    char[] subset = i == numberOfParts.Count - 1 ? alphabet.Skip(i * pieces).ToArray()
                    : alphabet.Skip(i * pieces).Take(pieces).ToArray();
... // more code following

起初这似乎工作正常，但我在测试中意识到当 X 为 10 时存在问题。基于这个逻辑，我得到 8 组 3 和一组 2，留下第 10 组 0，这不好因为我要进行最均匀的分配。

在这种情况下，10 的最理想分布是 6 组 3 组和 4 组 2 组。关于如何实现这一点的任何想法？

4

5 回答 5

3

通常，实现逻辑的最简单方法是使用模运算符 %。熟悉这个算子；它在有帮助的情况下非常有用。有很多方法可以编写实际代码来分配字母，使用数组或不使用数组等，但这个简短的表达式应该给你一个想法：

"ABCDEFGHIJKLMNOPQRSTUVWXYZ".IndexOf(letter) % partitionCount

该表达式给出了存放大写字母的分区的从零开始的索引。该字符串只是为了方便而显示，但可以是数组或其他表示字母的方式。您可以遍历字母表，使用与上述类似的逻辑来选择存放每个字母的位置。由你决定将逻辑放在哪里：在循环中、方法中等。

模运算没有什么神奇之处。它只是在达到可用数字集的末尾后“环绕”。我们都遇到过的一个简单的上下文是除法。% 运算符本质上只是给出除法余数。现在您了解了 % 运算符在做什么，您可以轻松地编写自己的代码来用任何语言做同样的事情。

把这一切放在一起，你可以编写一个像这样的实用程序、类或扩展方法——注意 % 来计算余数，并且那个简单的整数除法会丢弃它：

/// <summary>
/// Returns partition sized which are as close as possible to equal while using the indicated total size available, with any extra distributed to the front
/// </summary>
/// <param name="totalSize">The total number of elements to partition</param>
/// <param name="partitionCount">The number of partitions to size</param>
/// <param name="remainderAtFront">If true, any remainder will be distributed linearly starting at the beginning; if false, backwards from the end</param>
/// <returns>An int[] containing the partition sizes</returns>
public static int[] GetEqualizedPartitionSizes(int totalSize, int partitionCount, bool remainderAtFront = true)
{
    if (totalSize < 1)
        throw new ArgumentException("Cannot partition a non-positive number (" + totalSize + ")");
    else if (partitionCount < 1)
        throw new ArgumentException("Invalid partition count (" + partitionCount + ")");
    else if (totalSize < partitionCount)
        throw new ArgumentException("Cannot partition " + totalSize + " elements into " + partitionCount + " partitions");

    int[] partitionSizes = new int[partitionCount];
    int basePartitionSize = totalSize / partitionCount;
    int remainder = totalSize % partitionCount;
    int remainderPartitionSize = basePartitionSize + 1;
    int x;

    if (remainderAtFront)
    {
        for (x = 0; x < remainder; x++)
            partitionSizes[x] = remainderPartitionSize;

        for (x = remainder; x < partitionCount; x++)
            partitionSizes[x] = basePartitionSize;
    }
    else
    {
        for (x = 0; x < partitionCount - remainder; x++)
            partitionSizes[x] = basePartitionSize;

        for (x = partitionCount - remainder; x < partitionCount; x++)
            partitionSizes[x] = remainderPartitionSize;
    }

    return partitionSizes;
}
于 2013-05-30T01:30:54.777 回答
2

我觉得实现这一点的最简单方法是对每个字母执行循环分配。循环浏览字母表中的每个字母并添加，然后重复。有一个运行计数来确定您将把物品放入哪个字母，然后当它达到 >26 时，将其重置回 0！

于 2013-05-30T13:13:30.767 回答
1

我现在测试的伪代码算法：

Double count = alphabet.Count()
Double exact = count / numberOfParts
Double last = 0.0
Do Until last >= count
  Double next = last + exact
  ranges.Add alphabet, from:=Round(last), to:=Round(next)
  last = next
Loop

ranges.Add可以忽略空范围:-)

这是该算法的 LinqPad VB.NET 实现。

所以这个的 Linq 版本会是这样的

Double count = alphabet.Count();
Double exact = count / numberOfParts;

var partitions = Enumerable.Range(0, numberOfParts + 1).Select(n => Round((Double)n * exact));

这是使用此 Linq 查询的 LinqPad VB.NET 实现。

于 2013-05-30T02:11:51.760 回答
1

我在一个应用程序中所做的我必须分组分发东西是这样的

var numberOfPartitions = GetNumberOfPartitions();
var numberOfElements = GetNumberOfElements();

while (alphabet.Any())
{
     var elementsInCurrentPartition = Math.Ceil((double)numberOfPartitions / numberOfElements) 

     for (int i = 0; i < elementsInCurrentPartition; i++)
     {
          //fill your partition one element at a time and remove the element from the alphabet
          numberOfElements--;
     }
     numberOfPartitions--;
}

这不会为您提供您期望的确切结果（即 10 个分区的理想结果），但它非常接近。

ps这未经测试:)

于 2013-05-30T01:37:15.597 回答
0

（抱歉格式化，移动）

首先，您需要类似批处理方法的东西：

public static IEnumerable<IEnumerable<T>> Batch<T>(this IEnumerable<T> source, int groupSize)
{
    var tempSource = source.Select(n => n);
    while (tempSource.Any())
    {
        yield return tempSource.Take(groupSize);
        tempSource = tempSource.Skip(groupSize);
    }
}

然后，就这样称呼它：

var result = alphabet.Batch((int)Math.Ceiling(x / 26.0));
于 2013-06-22T12:01:41.623 回答