标签: combinatorics

我有一个成本优化请求,我不知道如何有文献.这有点难以解释,所以我提前为问题的长度道歉.

我正在访问的服务器以这种方式工作:

• 对记录(r1,... rn)和字段(f1,... fp)发出请求
• 你只能要求笛卡尔积(r1,...,rp)x(f1,... fp)
• 与此类请求相关的成本(时间和金钱)与请求的大小相关:

T((r1, ..., rn)x(f1, ..., fp) = a + b * n * p

在不失一般性的情况下(仅通过标准化),我们可以假设b=1成本是:

T((r1, ...,rn)x(f1,...fp)) = a + n * p

• 我只需要请求一对子集(r1, f(r1)), ... (rk, f(rk)),一个来自用户的请求.我的程序充当用户和服务器(外部)之间的中间人.我有很多这样的要求(每天数万).

在图形上,我们可以将其视为一个nxp稀疏矩阵,我想用矩形子矩阵覆盖非零值:

   r1 r2 r3 ... rp
   ------      ___
f1 |x  x|      |x|
f2 |x   |      ---
   ------
f3
..    ______
fn    |x  x|
      ------

有:

• 由于成本不变,子矩阵的数量保持合理
• 所有'x'必须位于子矩阵内
• 由于线性成本,所覆盖的总面积不能太大

我将g命名为我的问题的稀疏系数(所需对的数量超过总可能对​​,g = k / (n * p).我知道系数a.

有一些明显的观察:

• 如果a很小,最好的解决方案是独立请求每个(记录,字段)对,总成本为: …

假设我们有一个这样的数字表(我们可以假设它是一个方形表):

20  2   1   3   4
5   1   14  8   9
15  12  17  17  11
16  1   1   15  18
20  13  15  5   11

您的工作是计算n个数字的最大总和,其中n是表中的行数或列数.捕获的每个数字必须来自唯一的行和列.

例如,选择(0,0),(1,1),(2,2),(3,3)和(4,4)处的数字是可以接受的,但是(0,0),(0, 1),(2,2),(3,3)和(4,4)不是因为前两个数字是从同一行拉出的.

对这个问题我的(可笑的)解决方案是迭代遍历行和列的所有可能的排列.这适用于小网格,但当然,随着n变大,它会非常慢.它有O(n!)时间复杂度,如果我没有弄错的话(下面的示例Python代码).

我真的认为这可以在更好的时间内解决,但我没有想出任何足够聪明的东西.

所以我的问题是,应该使用什么算法来解决这个问题？

如果它有帮助,这个问题似乎与背包问题类似 .

import itertools
import re

grid = """20    2   1   3   4
5   1   14  8   9
15  12  17  17  11
16  1   1   15  18
20  13  15  5   11"""
grid = [[int(x) for x in re.split("\s+", line)] for line …

可能重复:
如何在java中从一组大小为n迭代生成k个元素子集？

我想建立自己的扑克手评估员,但我遇到了特定部分的问题.

如果两名牌手获得两张牌,那么将会有48张牌.在Texas Hold'em中,再发出5张可能的社区牌(这称为牌局).我想枚举/循环所有48个选择5个可能的棋盘组合,并计算玩家A获胜的时间和玩家B获胜的时间以及他们的时间.

我不确定如何系统地循环每5张卡组合.有没有人有任何想法？这些卡表示为类卡的数组,但如果它使它更快,我也可以将它们表示为bitset.

我在Java中这样做.

非常感谢

这个操作有名字吗？而且:有一个封闭形式的表达吗？

• 对于给定的n个元素集合,值k在1和n之间,
• 获取k个项目的所有子集(组合)
• 找到每个子集的产品
• 找到所有这些产品的总和

我可以在Python中表达这一点,并且很容易进行计算:

from operator import mul
from itertools import combinations
from functools import reduce
def sum_of_product_of_subsets(list1, k):
    val = 0
    for subset in combinations(list1, k):
        val += reduce(mul, subset)
    return val

我只是在寻找封闭的表单表达式,以便在设置大小变大时避免循环.

请注意,这与此问题不同:产品与所有组合的总和与每个组中的一个元素 - 该问题是关于笛卡尔积的乘积和.我正在寻找大小为k的组合集的乘积和; 我不认为他们是一样的.

要清楚,对于set(a,b,c,d),则:

k = 4 --> a*b*c*d
k = 3 --> b*c*d + a*c*d + a*b*d + a*b*c
k = 2 --> a*b + a*c + a*d + b*c + b*d + c*d
k = 1 --> a + b …

我需要开发一个课程时间表软件,可以有效地分配时间段和房间.这是一个基于课程的例程,而不是基于后期注册.并且有效地意味着课程根据工作人员的时间偏好分配时间段,并且还需要最小化第1年 - 第2年课程重叠,以便第2年学生可以重新学习他们未能通过的课程.(以及3至4年级的学生) .

现在,起初我认为这将是一个容易的问题,但现在看起来不同了.我看过的大多数论文都使用遗传算法/ PSO /模拟退火或这些类型的算法.我仍然无法将问题解释为GA问题.令我困惑的是为什么几乎没有人建议使用DFS或图形着色算法？

如果使用DFS/graph-coloring,有人可以解释这个场景吗？或者为什么不建议或尝试他们.

多集是一个集合,其中所有元素可能不唯一.如何枚举集合元素中的所有可能的排列？

我确信这个问题有一个正式的名称,并且知道这个名字可能会帮助我找到解决方案,但我不知道,并且谷歌的问题一直指向我背包问题,这是不一样的事情.

我想取一些值X并找到将该值拆分为N个整数整数的可能组合.

如果我的措辞令人困惑,这里是X = 4,N = 3的例子

Stack -> 1 | 2 | 3 |
----------------------
#1-----> 4 | 0 | 0 |
----------------------
#2-----> 3 | 1 | 0 |
----------------------
#3-----> 2 | 1 | 1 |
----------------------
#4-----> 2 | 2 | 0 |

复制是可以接受的,因为它易于删除,但理想情况下不会计算.解决问题的算法将是完美的,但即使找出问题的名称也会使研究更容易.谢谢.

例如,房间里有6把椅子,有4个女孩和2个男孩.他们可以坐在这把椅子上,有15种独特的方式6!/(4!*2!)=15.

我的问题是找到有效的方法来计算他们选择坐的可能性的位置.按位置我的意思是:

BBGGGG - possible position #1
BGBGGG - possible position #2
BGGBGG - possible position #3
BGGGBG - possible position #4
BGGGGB - possible position #5
GBBGGG - possible position #6
GBGBGG - possible position #7
GBGGBG - possible position #8
GBGGGB - possible position #9
GGBBGG - possible position #10
GGBGBG - possible position #11
GGBGGB - possible position #12
GGGBBG - possible position #13
GGGBGB - possible position #14
GGGGBB - possible position #15

例如,他们选择位置 …

我有一种非常低效的方法来计算N/2大小为N的数组中的项组合.我所做的是先对数组进行排序,然后循环遍历数组的排列,创建具有一半元素的多重集并将其插入到一套.最后我得到了集合的计数.

long GetCombinations(std::vector<double> nums) {
    long combinations = 0;
    std::sort(nums.begin(), nums.end());
    std::set<std::multiset<double>> super_set;

    do {
        std::multiset<double> multi_set;

        for (unsigned int i = 0; i < nums.size() / 2; ++i)
            multi_set.insert(nums[i]);

        auto el = (super_set.insert(multi_set));

        if (el.second)
            ++combinations;

    } while (std::next_permutation(nums.begin(), nums.end()));

    return combinations;
}

代码有效,但效率很低.对于给定的数组[0.5, 0.5, 1, 1],有3种大小为2的组合:

0.5,0.5
1,1
1,0.5

是否有不同的算法或方法可以提高此代码的速度？

我们需要找出可以形成仅包含 3 个元素（1,2 和 3）的 N 长度数组 (A) 的方法数。

数组的相邻元素如何放置在数组中几乎没有限制：

(A[i], A[i + 1])某种类型的相邻元素对的数量不能超过问题陈述中给出的数量。

example :

1, 2 : 2 (we can have at most 2 adjacent-pairs of value [1, 2] in the array)
1, 3 : 3
2, 1 : 1
2, 3 : 0 (we cannot have any adjacent-pairs of value [2, 3] in entire array)
3, 1 : 4
3, 2 : 3

对于 type 的相邻元素 A[i] == A[i + 1]，它们可以在数组中出现任意次数

1, 1 …