本文介绍了用于“巩固”算法的算法包括: N项放入K的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我想知道是否有一种已知的算法可以执行以下操作,还想知道如何在C#中实现它。也许这是已知的问题类型。

I was wondering whether there's a known algorithm for doing the following, and also wondering how it would be implemented in C#. Maybe this is a known type of problem.

示例:

假设我有一个课程

class GoldMine
{
    public int TonsOfGold { get; set; }
}

列表 N = 3 这样的项目

var mines = new List<GoldMine>() {
    new GoldMine() { TonsOfGold = 10 },
    new GoldMine() { TonsOfGold = 12 },
    new GoldMine() { TonsOfGold = 5 }
};

然后将矿山合并为 K = 2 地雷就是合并

Then consolidating the mines into K=2 mines would be the consolidations

{ {Lines[0],Lines[1]}, {Lines[2]} }, // { 22 tons, 5 tons }
{ {Lines[0],Lines[2]}, {Lines[1]} }, // { 15 tons, 12 tons }
{ {Lines[1],Lines[2]}, {Lines[0]} }  // { 17 tons, 10 tons }

并合并为 K = 1 地雷将是单一合并

and consolidating into K=1 mines would be the single consolidation

{ Lines[0],Lines[1],Lines[2] } // { 27 tons }

我感兴趣的是合并过程的算法。

What I'm interested in is the algorithm for the consolidation process.

推荐答案

如果我没记错的话,您要描述的问题是所有k个k-组合的数量

If I'm not mistaken, the problem you're describing is Number of k-combinations for all k

我找到了一个代码段,我相信它可以解决您的用例但我只是不记得我从哪里得到的。它必须来自StackOverflow。如果有人认出了这部分代码,请告诉我,我会确保记入它。

I found a code snippet which I believe addresses your use case but I just can't remember where I got it from. It must have been from StackOverflow. If anyone recognized this particular piece of code, please let me know and I'll make sure to credit it.

所以这是扩展方法:

public static class ListExtensions
{
    public static List<ILookup<int, TItem>> GroupCombinations<TItem>(this List<TItem> items, int count)
    {
        var keys = Enumerable.Range(1, count).ToList();
        var indices = new int[items.Count];
        var maxIndex = items.Count - 1;
        var nextIndex = maxIndex;
        indices[maxIndex] = -1;
        var groups = new List<ILookup<int, TItem>>();

        while (nextIndex >= 0)
        {
            indices[nextIndex]++;

            if (indices[nextIndex] == keys.Count)
            {
                indices[nextIndex] = 0;
                nextIndex--;
                continue;
            }

            nextIndex = maxIndex;

            if (indices.Distinct().Count() != keys.Count)
            {
                continue;
            }

            var group = indices.Select((keyIndex, valueIndex) =>
                                        new
                                        {
                                            Key = keys[keyIndex],
                                            Value = items[valueIndex]
                                        })
                .ToLookup(x => x.Key, x => x.Value);

            groups.Add(group);
        }
        return groups;
    }
}

还有一个打印输出结果的实用工具: / p>

And a little utility method that prints the output:

public void PrintGoldmineCombinations(int count, List<GoldMine> mines)
{
    Debug.WriteLine("count = " + count);
    var groupNumber = 0;
    foreach (var group in mines.GroupCombinations(count))
    {
        groupNumber++;
        Debug.WriteLine("group " + groupNumber);
        foreach (var set in group)
        {
            Debug.WriteLine(set.Key + ": " + set.Sum(m => m.TonsOfGold) + " tons of gold");
        }
    }
}

您会这样使用:

var mines = new List<GoldMine>
{
    new GoldMine {TonsOfGold = 10},
    new GoldMine {TonsOfGold = 12},
    new GoldMine {TonsOfGold = 5}
};

PrintGoldmineCombinations(1, mines);
PrintGoldmineCombinations(2, mines);
PrintGoldmineCombinations(3, mines);

这将产生以下输出:

count = 1
group 1
1: 27 tons of gold
count = 2
group 1
1: 22 tons of gold
2: 5 tons of gold
group 2
1: 15 tons of gold
2: 12 tons of gold
group 3
1: 10 tons of gold
2: 17 tons of gold
group 4
2: 10 tons of gold
1: 17 tons of gold
group 5
2: 15 tons of gold
1: 12 tons of gold
group 6
2: 22 tons of gold
1: 5 tons of gold
count = 3
group 1
1: 10 tons of gold
2: 12 tons of gold
3: 5 tons of gold
group 2
1: 10 tons of gold
3: 12 tons of gold
2: 5 tons of gold
group 3
2: 10 tons of gold
1: 12 tons of gold
3: 5 tons of gold
group 4
2: 10 tons of gold
3: 12 tons of gold
1: 5 tons of gold
group 5
3: 10 tons of gold
1: 12 tons of gold
2: 5 tons of gold
group 6
3: 10 tons of gold
2: 12 tons of gold
1: 5 tons of gold

注意:这并没有考虑集合内容中的重复项,因此我不确定您是否确实希望将这些内容过滤掉。
这是您需要的吗?

Note: this does not take into account duplicates by the contents of the sets and I'm not sure if you actually want those filtered out or not.Is this what you need?

编辑

实际上,查看您的评论似乎不想要重复项,而且还希望包含较低的 k 值,因此这是一个较小的修改,可以删除重复项(以一种非常丑陋的方式,道歉),并为您提供每组 k 的较低值:

Actually, looking at your comment it seems you don't want the duplicates and you also want the lower values of k included, so here is a minor modification that takes out the duplicates (in a really ugly way, I apologize) and gives you the lower values of k per group:

public static List<ILookup<int, TItem>> GroupCombinations<TItem>(this List<TItem> items, int count)
{
    var keys = Enumerable.Range(1, count).ToList();
    var indices = new int[items.Count];
    var maxIndex = items.Count - 1;
    var nextIndex = maxIndex;
    indices[maxIndex] = -1;
    var groups = new List<ILookup<int, TItem>>();

    while (nextIndex >= 0)
    {
        indices[nextIndex]++;

        if (indices[nextIndex] == keys.Count)
        {
            indices[nextIndex] = 0;
            nextIndex--;
            continue;
        }

        nextIndex = maxIndex;

        var group = indices.Select((keyIndex, valueIndex) =>
                                    new
                                    {
                                        Key = keys[keyIndex],
                                        Value = items[valueIndex]
                                    })
            .ToLookup(x => x.Key, x => x.Value);

        if (!groups.Any(existingGroup => group.All(grouping1 => existingGroup.Any(grouping2 => grouping2.Count() == grouping1.Count() && grouping2.All(item => grouping1.Contains(item))))))
        {
            groups.Add(group);
        }
    }
    return groups;
}

对于 k = 2 ,它产生以下输出:

It produces the following output for k = 2:

group 1
1: 27 tons of gold
group 2
1: 22 tons of gold
2: 5 tons of gold
group 3
1: 15 tons of gold
2: 12 tons of gold
group 4
1: 10 tons of gold
2: 17 tons of gold

这篇关于用于“巩固”算法的算法包括: N项放入K的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-20 10:29
查看更多