如何高效生成总和在指定范围内的所有组合(在所有深度)

2024-05-22

假设您有一组值 (1,1,1,12,12,16)如何生成总和在预定义范围内的所有可能组合(不重复)[min,max]。例如,这里是(所有深度的)范围在13 and 17:

1 12

1 1 12

1 1 1 12

16

1 16

这假设具有相同值的每个项目是无法区分的,因此您不会得到以下三个结果1 12在最终输出中。蛮力是可能的,但在项目数量很大的情况下,所有深度的组合数量都是天文数字。在上面的示例中,所有深度都有 (3 + 1) * (2 + 1) * (1 + 1) = 24 种组合。因此,总组合是任何给定值的项目数 + 1 的乘积。当然,我们可以从逻辑上丢弃大量其部分总和大于最大值的组合(例如,集合16 12已经大于最大值17,因此跳过任何具有16 and 12在他们中)。

我最初认为我可以将输入数组转换为两个数组并像里程表一样递增它们。但我完全陷入了这种提前崩溃的递归算法。有什么建议么?

{
    int uniqueValues = 3;
    int[] maxCounts = new int[uniqueValues];
    int[] values = new int[uniqueValues];

    // easy code to bin the data, just hardcoding for example
    maxCounts[0] = 3;
    values[0] = 1;
    maxCounts[1] = 2;
    values[1] = 12;
    maxCounts[2] = 1;
    values[2] = 16;

    GenerateCombinationsHelper(new List<int[]>(), 13, 17, 0, 0, maxCounts, new int[3], values);
}

private void GenerateCombinationsHelper(List<int[]> results, int min, int max, int currentValue, int index, int[] maxValues, int[] currentCombo, int[] values)
{
    if (index >= maxValues.Length)
    {
        return;
    }

    while (currentCombo[index] < maxValues[index])
    {
        currentValue += values[index];

        if (currentValue> max)
        {                   
            return;
        }

        currentCombo[index]++;

        if (currentValue< min)
        {                    
            GenerateCombinationsHelper(results, min, max, currentValue, index + 1, maxValues, currentCombo, values);
        }
        else
        {
            results.Add((int[])currentCombo.Clone());
        }
    }
}

Edit

整数值仅用于演示。它可以是任何具有某种数值的对象(int, double, float, ETC...)

通常只有少数唯一值(大约 10 个),但总共可能有数千个项目。


将主调用切换为:

GenerateCombinationsHelper2(new List<int[]>(), 13, 17, 0, maxCounts, new int[3], values);

然后添加以下代码:

private void GenerateCombinationsHelper2(List<int[]> results, int min, int max, int index, int[] maxValues, int[] currentCombo, int[] values)
{
    int max_count = Math.Min((int)Math.Ceiling((double)max / values[index]), maxValues[index]);

    for(int count = 0; count <= max_count; count++)
    {
        currentCombo[index] = count;
        if(index < currentCombo.Length - 1)
        {
            GenerateCombinationsHelper2(results, min, max, index + 1, maxValues, currentCombo, values);
        }
        else
        {
            int sum = Sum(currentCombo, values);
            if(sum >= min && sum <= max)
            {
                int[] copy = new int[currentCombo.Length];
                Array.Copy(currentCombo, copy, copy.Length);
                results.Add(copy);
            }
        }
    }
}

private static int Sum(int[] combo, int[] values)
{
    int sum = 0;
    for(int i = 0; i < combo.Length; i++)
    {
        sum += combo[i] * values[i];
    }
    return sum;
}

它返回 5 个有效答案。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

如何高效生成总和在指定范围内的所有组合(在所有深度) 的相关文章

  • BASIC 中的 C 语言中的 PeekInt、PokeInt、Peek、Poke 等效项

    我想知道该命令的等效项是什么Peek and Poke 基本和其他变体 用 C 语言 类似PeekInt PokeInt 整数 涉及内存条的东西 我知道在 C 语言中有很多方法可以做到这一点 我正在尝试将基本程序移植到 C 语言 这只是使用
  • 在 xaml 中编写嵌套类型时出现设计时错误

    我创建了一个用户控件 它接受枚举类型并将该枚举的值分配给该用户控件中的 ComboBox 控件 很简单 我在数据模板中使用此用户控件 当出现嵌套类型时 问题就来了 我使用这个符号来指定 EnumType x Type myNamespace
  • C# 异步等待澄清?

    我读了here http blog stephencleary com 2012 02 async and await html that 等待检查等待的看看它是否有already完全的 如果 可等待已经完成 那么该方法将继续 运行 同步
  • 在一个数据访问层中处理多个连接字符串

    我有一个有趣的困境 我目前有一个数据访问层 它必须与多个域一起使用 并且每个域都有多个数据库存储库 具体取决于所调用的存储过程 目前 我只需使用 SWITCH 语句来确定应用程序正在运行的计算机 并从 Web config 返回适当的连接字
  • 类型中的属性名称必须是唯一的

    我正在使用 Entity Framework 5 并且有以下实体 public class User public Int32 Id get set public String Username get set public virtual
  • std::vector 与 std::stack

    有什么区别std vector and std stack 显然 向量可以删除集合中的项目 尽管比列表慢得多 而堆栈被构建为仅后进先出的集合 然而 堆栈对于最终物品操作是否更快 它是链表还是动态重新分配的数组 我找不到关于堆栈的太多信息 但
  • 如何使从 C# 调用的 C(P/invoke)代码“线程安全”

    我有一些简单的 C 代码 它使用单个全局变量 显然这不是线程安全的 所以当我使用 P invoke 从 C 中的多个线程调用它时 事情就搞砸了 如何为每个线程单独导入此函数 或使其线程安全 我尝试声明变量 declspec thread 但
  • 方程“a + bx = c + dy”的积分解

    在等式中a bx c dy 所有变量都是整数 a b c and d是已知的 我如何找到整体解决方案x and y 如果我的想法是正确的 将会有无限多个解 由最小公倍数分隔b and d 但我只需要一个解决方案 我可以计算其余的 这是一个例
  • 人脸 API DetectAsync 错误

    我想创建一个简单的程序来使用 Microsoft Azure Face API 和 Visual Studio 2015 检测人脸 遵循 https social technet microsoft com wiki contents ar
  • 在 Unity 中实现 Fur with Shells 技术

    我正在尝试在 Unity 中实现皮毛贝壳技术 http developer download nvidia com SDK 10 5 direct3d Source Fur doc FurShellsAndFins pdf Fins 技术被
  • 为什么这个字符串用AesCryptoServiceProvider第二次解密时不相等?

    我在 C VS2012 NET 4 5 中的文本加密和解密方面遇到问题 具体来说 当我加密并随后解密字符串时 输出与输入不同 然而 奇怪的是 如果我复制加密的输出并将其硬编码为字符串文字 解密就会起作用 以下代码示例说明了该问题 我究竟做错
  • x:将 ViewModel 方法绑定到 DataTemplate 内的事件

    我基本上问同样的问题这个人 https stackoverflow com questions 10752448 binding to viewmodels property from a template 但在较新的背景下x Bind V
  • 如何在 Linq to SQL 中使用distinct 和 group by

    我正在尝试将以下 sql 转换为 Linq 2 SQL select groupId count distinct userId from processroundissueinstance group by groupId 这是我的代码
  • C 函数 time() 如何处理秒的小数部分?

    The time 函数将返回自 1970 年以来的秒数 我想知道它如何对返回的秒数进行舍入 例如 对于100 4s 它会返回100还是101 有明确的定义吗 ISO C标准没有说太多 它只说time 回报 该实现对当前日历时间的最佳近似 结
  • 编译时展开 for 循环内的模板参数?

    维基百科 here http en wikipedia org wiki Template metaprogramming Compile time code optimization 给出了 for 循环的编译时展开 我想知道我们是否可以
  • 在 WPF 中使用 ReactiveUI 提供长时间运行命令反馈的正确方法

    我有一个 C WPF NET 4 5 应用程序 用户将用它来打开某些文件 然后 应用程序将经历很多动作 读取文件 通过许多插件和解析器传递它 这些文件可能相当大 gt 100MB 因此这可能需要一段时间 我想让用户了解 UI 中发生的情况
  • 相当于Linux中的导入库

    在 Windows C 中 当您想要链接 DLL 时 您必须提供导入库 但是在 GNU 构建系统中 当您想要链接 so 文件 相当于 dll 时 您就不需要链接 为什么是这样 是否有等效的 Windows 导入库 注意 我不会谈论在 Win
  • C# 中的 IPC 机制 - 用法和最佳实践

    不久前我在 Win32 代码中使用了 IPC 临界区 事件和信号量 NET环境下场景如何 是否有任何教程解释所有可用选项以及何时使用以及为什么 微软最近在IPC方面的东西是Windows 通信基础 http en wikipedia org
  • 当文件流没有新数据时如何防止fgets阻塞

    我有一个popen 执行的函数tail f sometextfile 只要文件流中有数据显然我就可以通过fgets 现在 如果没有新数据来自尾部 fgets 挂起 我试过ferror and feof 无济于事 我怎样才能确定fgets 当
  • 使用 WGL 创建现代 OpenGL 上下文?

    我正在尝试使用 Windows 函数创建 OpenGL 上下文 现代版本 基本上代码就是 创建窗口类 注册班级 创建一个窗口 choose PIXELFORMATDESCRIPTOR并设置它 创建旧版 OpenGL 上下文 使上下文成为当前

随机推荐

  • 在java中查找OSX的版本

    我需要测试 java 中 osx 的版本是否 Try System getProperty os name and or System getProperty os version 它返回字符串 HERE https docs oracle
  • 优化重叠矩形的绘制

    我有很多矩形 有些与其他矩形重叠 每个矩形都有一个绝对 z 顺序和一个colour 每个 矩形 实际上是粒子效果 网格或纹理的轴对齐边界框 并且可能是半透明的 但只要您不尝试剔除其他矩形后面的矩形 就更容易抽象地思考彩色矩形 所以我将在问题
  • 使用他们的 API 创建一个基本的 MailChimp 注册表单

    我是 MailChimp 的新手 需要一些帮助 通过他们的基本时事通讯注册表单 您只需将一些预先打包的 HTML 嵌入到您的页面中即可 然而 这样做的问题是 单击 提交 会重定向到 MailChimp 页面 我不想重定向到 MailChim
  • Android 上 WebRTC 的自定义视频源

    Overview 我想使用自定义视频源通过 WebRTC Android 实现来直播视频 如果我理解正确的话 现有的实现仅支持 Android 手机上的前置和后置摄像头 以下类与此场景相关 Camera1Enumerator java ht
  • 从字符串中提取电子邮件地址

    我有一个像这样的字符串 Francesco Renga lt email protected cdn cgi l email protection gt 我只需要提取电子邮件 即 电子邮件受保护 cdn cgi l email protec
  • 防止更新 ASP.NET MVC 和实体框架中未更改的值

    我正在使用 ASP NET MVC 和实体框架 我有一个 编辑人员 网页 可以在其中编辑人员的字段 然后在回发操作中 我使用以下代码 var person objectCtx Persons Where s gt s Id id First
  • “结构类型防护”与“if”配合使用,但不能用作数组过滤谓词

    我有一个联合类型 Pet在下面的示例中 组合了多个对象类型 每个对象类型都有一个type指示其类型的属性 有时我有一个联合类型的数组 Pet 并且需要 filter 它基于type财产 这本身工作得很好 但为了避免多余的类型声明 我想确保
  • 基于两列对数据框中的行进行求和[重复]

    这个问题在这里已经有答案了 我想添加一列的值 将它们按两列分组 我找到了如何在一列上执行此操作 但无法弄清楚如何在两列上执行此操作 例如 如果我有以下数据框 x c a a b b c c a a b b c c a a b b c c y
  • Spring Batch - 对数据列表中的每个项目重复步骤

    这是一项艰巨的任务 但我确信这并非闻所未闻 我有两个数据集 国家和人口统计数据 国家 地区数据集包含国家 地区名称及其人口统计数据的 ID 人口统计数据集是从乡村到郊区的分层数据集 这两个数据集都是每周从第三方获取的 我需要将人口统计数据分
  • 使用 Retrofit 2 添加标头以请求

    我正在尝试发送带有身份验证标头的请求 但服务器似乎无法识别客户端 我用了this https futurestud io tutorials android basic authentication with retrofit教程 并实现了
  • [重复]

    这个问题在这里已经有答案了 有什么区别List
  • Git 认为我每次进行小更改时都在重写我的一个文件

    我有一个中等大小的 Java 文件 每次我对一个文件 BuildTable java 进行更改时 Git 都会将其报告为巨大的更改 即使只是一两行 BuildTable java 大约有 200 行 本次提交中的更改仅更改了一行 git d
  • Flask-admin 内联建模传递表单参数会抛出 AttributeError

    Flask 开发者们大家好 在 Flask admin 中 我目前尝试在模型视图中实现内联模型编辑 在模型方面 我有一个简单的树结构 表示一组内容页面 每个节点都有多个子节点以及与其关联的多个内容数据模型 模型被命名为ContentNode
  • Android Facebook SDK 和 URL 方法成功形成好友对话框,但无法提交

    我开始认为这是一个错误 请证明我错了 我想以编程方式在 Facebook 上加好友 他们是唯一且肯定是该人在现实生活中认识的人 以下三种解决方案都具有相同的结果 成功的好友对话框 意味着个人资料名称 图片 指示操作的语句 与某人成为好友 以
  • Struts ActionForm 属性应该是什么类型?

    我使用 Struts 1 2 4 继承了这个巨大的遗留 Java Web 应用程序 我有一个关于 ActionForms 的具体问题 其中一些仅具有字符串属性 即使对于数字 其中一些使用看似合适的类型 整数 日期 字符串等 这里的最佳实践是
  • 使用 Docker 时未加载 Keycloak SPI 提供程序和层

    我正在尝试使用一些自定义内容 例如 logback 扩展 设置 docker 映像 因此我有一些 CLI 脚本 如下所示 subsystem logging remove extension org jboss as logging rem
  • 可扩展的宏定义

    灵感来自于评论区 https stackoverflow com questions 23879410 is it possible to extend a function lambda macro in scheme 23879575
  • JMS 规范或各种实现是否支持消息的传递确认?

    假设 Producer 向 JMS 主题 news 发送一条消息 Consumer1 读取了消息 但 Consumer2 离线 因此尚未读取消息 是否有任何内置 规范或实现 方式让生产者收到消费者 1 已读取其消息但消费者 2 尚未读取的通
  • 使用 PyQt 和 matplotlib 在可滚动小部件中显示多个绘图

    由于我没有得到答案this https stackoverflow com questions 12179893 creating a scrollable multiplot with pythons pylab我尝试用 PyQt 解决这
  • 如何高效生成总和在指定范围内的所有组合(在所有深度)

    假设您有一组值 1 1 1 12 12 16 如何生成总和在预定义范围内的所有可能组合 不重复 min max 例如 这里是 所有深度的 范围在13 and 17 1 12 1 1 12 1 1 1 12 16 1 16 这假设具有相同值的