Intro
在我们系统中有这样的一个需求，我们在订单下单之前会根据一些订单限制来进行订单的拆分来满足下单的条件，原先的拆单方式比较简单，基本上是一半一半的拆，这样的实现比较简单，但是也会造成多拆出来一些订单，那要怎么样能够尽可能的少拆单呢？.
How
购物车中商品的结构如下：
var products = new List<Product>()
{
new Product
{
Id = 1,
Quantity = 2,
Price = 20,
Weight = 1
},
new Product
{
Id = 2,
Quantity = 3,
Price = 30,
Weight = 2
},
};
于是就想着暴力穷举每一种可能性，从最少的不拆单，到最多的每个商品一个订单，找到一种拆单最少又能够满足所有限制的拆分情况，转换为代码就如下面这样：
var productsToSplits = products
.Select(p => Enumerable.Repeat(p.Id, p.Quantity))
.SelectMany(x => x)
.ToArray();
for (var cnt = 1; cnt <= products.Count; i++)
{
foreach(var splits in productsToSplits.Partitions(cnt))
{
if (AllRestrictionsMeet(splits))
{
return splits;
}
}
}
首先将要进行拆分的商品放到一个集合中，这里我们最小的拆分粒度是到每个商品，需求不同可以自行调整
然后从最少的订单数到最多的订单数进行穷举，比如一共 N 个商品，则从拆分成1个订单到拆分成 N 个订单进行穷举，如果是 3 则表示要将 N 个商品分成 3 个订单，也就是将N 个商品分成 3 部分，上面的 Partitions 方法就是将 N 个商品拆成 3 部分的核心实现
Implement
拆分代码实现如下：
public static IEnumerable<T[][]> Partitions<T>(this T[] array, int batch)
{
if (batch <= 0 || array.Length < batch)
{
throw new ArgumentException("Invalid batch size", nameof(batch));
}
if (batch == 1)
{
yield return new[] { array };
}
else if (batch == array.Length)
{
yield return array.Select(x => new[] { x }).ToArray();
}
else
{
var e = array[0];
var m = array[1..];
foreach (var p in Partitions(m, batch - 1))
{
yield return new[]
{
new []{e}
}.Concat(p).ToArray();
}
foreach (var p in Partitions(m, batch))
{
for (var i = 0; i < p.Length; i++)
{
yield return p[..i]
.Concat(new[] { new[] { e }.Concat(p[i]).ToArray() })
.Concat(p[(i + 1)..])
.ToArray();
}
}
}
}
拆分有两个极端的边界情况，一个是拆成一个集合，那么就是所有的元素都在一起，另一种情况就是每个元素拆分成一个集合，每个集合中只有一个元素
对于其他情况分为两种情况进行递归穷举，将 M 个元素的数组拆成 N 个数组
一种是第一个元素始终是一个集合，然后将剩下的元素拆成 N-1 个数组，加上第一个就是 N 个数组了
另外一种情况是将除了第一个元素之外的 N-1 个元素拆成 N 个数组，然后把第一个元素放在这 N 个数组中的一个，这样最后返回的还是 N 个数组
Sample
我们来找几个数据来实验一下，输出的结果是不是正确的
var nums = new[]{ 1,2,3 };
nums.Partitions(2).Dump();
将三个元素分成两批，那结果就应该是从 3 个里选一个或者选两个，有三种情况
[1], [2, 3]
[2], [1, 3]
[3], [1, 2]
想尝试更多数据可以自己来试一下，限于文章篇幅就不举例了
More
实现是基于一个 python 版本改写的，原 python 版本可以参考：https://github.com/more-itertools/more-itertools/blob/master/more_itertools/more.py#L3149
实际应用时，可以先根据限制计算一个最小订单数量，如果最小订单数量是 5 ，则从 5 开始就可以了，因为从 1 到 4 都是不满足条件的，可以减少一些不必要的计算
实现思路仅供参考，C# 的 Index/Range 用起来真香
