我刚刚看到这个问题而不知道如何解决它.你可以请我提供算法,C++代码或想法吗？

这是一个非常简单的问题.给定N和K的值,您需要告诉我们二项式系数C(N,K)的值.您可以放心,K <= N且N的最大值为1,000,000,000,000,000.由于该值可能非常大,您需要计算结果模1009.输入

输入的第一行包含测试用例T的数量,最多为1000.下一个T行中的每一行由两个空格分隔的整数N和K组成,其中0 <= K <= N且1 <= N <= 1,000,000,000,000,000 .产量

对于每个测试用例,在新行上打印,二项式系数C(N,K)的模数为1009.

输入:
3
3 1
5 2
10 3

输出:
3
10
120

给定两个排序的数字数组,我们希望找到具有第k个最大可能总和的对.(一对是第一个数组中的一个元素,第二个数组中是一个元素).例如,使用数组

• [2,3,5,8,13]
• [4,8,12,16]

具有最大总和的对是

• 13 + 16 = 29
• 13 + 12 = 25
• 8 + 16 = 24
• 13 + 8 = 21
• 8 + 12 = 20

因此,第四大总和是(13,8).如何找到具有第k个最大可能总和的对？

另外,最快的算法是什么？数组已经排序,大小为M和N.

我已经知道O(Klogk)解决方案,使用此处给出的Max-Heap .

它也是Google最喜欢的采访问题之一,他们需要一个O(k)解决方案.

我还在某处读到存在O(k)解决方案,我无法弄清楚.

有人可以用伪代码解释正确的解决方案.

PS请不要发布此链接作为答案/评论.它不包含答案.

因此,温迪的通告其夹层具有256个组合 - 这意味着有8种成分,你可以有没有(虽然我不知道为什么他们会算,你什么都不包括作为有效的组合,但我离题).

通用方法允许您将每个选择的各种状态相乘,从而允许更复杂的组合.在这种情况下,Wendy的项目只能包含或排除.但是一些三明治可能有两种芥末的选择(但不是两种,以节省成本).

这些都相当简单.你将选项的数量相乘,所以For Wendy's:

2*2*2*2*2*2*2*2 = 256

如果他们将芥末选择多样化,如上所述:

2*2*3*2*2*2*2*2 = 384

走得更远似乎更难.

如果你将芝麻作为一个单独的项目,那么他们需要发髻项目.只有在包含面包的情况下才可以吃芝麻,并且可以没有芝麻的面包,但是如果没有芝麻,你就不能吃芝麻.这可以简化为具有三种状态的单个发髻物品(无,带有种子的发髻,没有发髻)但是有些情况无法完成.

例如,戴尔的计算机配置器不允许某些组合(可能插槽已满,当放入同一系统时项目不兼容等).

• 在处理项目可能发生冲突的更复杂的系统时,有哪些适当的组合方法？
• 什么是好的,通用的方法来存储这些信息,而无需为每个产品/组合/项目编写代码以捕获冲突？
• 有一种简单的方法可以说,"当系统必须处理复杂的冲突组合时,有X种方法来配置系统/三明治"吗？

我花了很长时间寻找这个问题的解决方案.我绘制了大量的交叉阴影三角形,在简单的情况下计算三角形,并搜索某种模式.不幸的是,我碰到了墙.我很确定我的编程/数学技能不符合这个问题的先决条件.

所以我在网上找到了一个解决方案,以便访问论坛.我根本不了解大多数方法,有些看起来太复杂了.

谁能让我理解这个问题？其中一种方法可以在这里找到:http://www.math.uni-bielefeld.de/~sillke/SEQUENCES/grid-triangles(问题C)允许使用单个函数.

他们是如何提出这个解决方案的？在这一点上,我真的只想了解这个有趣问题背后的一些概念.我知道查找解决方案不是欧拉精神的一部分,但我很确定无论如何我都不会解决这个问题.

我期待创建一种特殊类型的组合,其中没有两个集合具有多个交叉元素.让我用一个例子来解释一下:

假设我们有9个字母集,包含A,B,C,D,E,F,G,H和I.

如果您创建三个字母的标准非重复组合,您将拥有9C3集.这些将包含ABC,ABD,BCD等集合.我希望创建最多只有1个常用字母的集合.所以在这个例子中,我们将获得以下集合:

ABC,ADG,AEI,AFH,BEH,BFG,BDI,CFI,CDH,CEG,DEF和GHI - 请注意,如果您选择任意两套,则不超过1个重复字母.

什么是生成这样的集合的好方法？它应该是可扩展的解决方案,以便我可以为一组1000个字母执行此操作,子集大小为4.

任何帮助都非常感谢.

谢谢

我正在寻找一种有效的方法来实现这一目标:

• 你有一个数字列表1 ..... n(通常:1..5或1..7左右 - 相当小,但可能因情况而异)

• 你需要这些数字的所有长度的所有组合,例如只有一个数字({1},{2},...... {n})的所有组合,然后是两个不同数字的所有组合({1,2}, {1,3},{1,4} ..... {n-1,n}),然后是这些数字中的三个的所有组合({1,2,3},{1,2,4})等等

基本上,在组内,顺序是无关紧要的,因此{1,2,3}相当于{1,3,2} - 这只是从该列表获取所有x组数的问题

似乎应该有一个简单的算法 - 但到目前为止我徒劳无功.大多数组合和排列算法似乎a)考虑到顺序(例如123不等于132),并且它们似乎总是在单个字符串或数字上运行....

任何人都有一个伟大的,漂亮的'快速算法？

谢谢!

一位朋友今天问了我一个关于转让问题的问题.我找到了一个非常简单的解决方案,但我觉得它可以变得更简单,更快捷.非常感谢您的帮助.

问题:假设我有N个人,我需要将它们分配到M个建筑物中,每个建筑物都可以容纳K个人.并非所有人都愿意相互生活,所以我有一个N*N细胞矩阵和一个标志着愿意相互生活的人的1.如果一个单元格包含1,则意味着我和J可以共存.显然,矩阵在主对角线周围是对称的.

我的解决方案如下(伪代码):

int[] Match(int[] people, int[][] pairs, int numBuildings, int buildingsSize)
{
    int[] freePeople = findFreePeople(people);
    if(freePeople) = 0 
    {
        return people;
    }

    foreach(int person in freePeople)
    {
        for(int buildingIndex=0 to numBuildings)
        {
            if( CheckIfPersonFitsInBuilding(...) )
            {
                int[] tempPeople = people.Copy();
                tempPeople[person] = buildingIndex;
                int[] result = Match(tempPeople,pairs,numBuildings,buildingsSize);
                if(result != null)
                {
                    return result;
                }
            }
        }
    }
    return null;
}

我只是用递归来涵盖所有可能的安排.我觉得这可以大大优化,我不是在谈论启发式方法,而是一个复杂性较低的解决方案.

1. 是否存在类似于此的正式众所周知的问题？
2. 有更好的算法吗？

我认为这可能与稳定的婚姻问题有关,尽管我不确定.

我有一个带有列表的文件,需要创建一个文件,将每行与另一行进行比较.例如,我的文件有这个:

AAA  
BBB  
CCC  
DDD  
EEE

我希望最终列表看起来像这样:

AAA  BBB  
AAA  CCC  
AAA  DDD  
AAA  EEE  
BBB  CCC  
BBB  DDD  
BBB  EEE  
CCC  DDD  
CCC  EEE  
DDD  EEE

我试图在Perl中这样做,这是第一次,我遇到了一些麻烦.我知道你需要制作一个数组,然后拆分它,但之后我遇到了一些麻烦.

我想为numpy 实现itertools.combinations.根据这个讨论,我有一个适用于一维输入的功能:

def combs(a, r):
    """
    Return successive r-length combinations of elements in the array a.
    Should produce the same output as array(list(combinations(a, r))), but 
    faster.
    """
    a = asarray(a)
    dt = dtype([('', a.dtype)]*r)
    b = fromiter(combinations(a, r), dt)
    return b.view(a.dtype).reshape(-1, r)

并且输出有意义:

In [1]: list(combinations([1,2,3], 2))
Out[1]: [(1, 2), (1, 3), (2, 3)]

In [2]: array(list(combinations([1,2,3], 2)))
Out[2]: 
array([[1, 2],
       [1, 3],
       [2, 3]])

In [3]: combs([1,2,3], 2)
Out[3]: 
array([[1, 2],
       [1, 3],
       [2, 3]]) …

我正在努力有效地解决SPOJ问题64:排列.

设A = [a1,a2,...,an]是整数1,2,...,n的排列.如果ai> aj,则一对索引(i,j),1 <= i <= j <= n,是置换A的反转.我们给出整数n> 0和k> = 0.包含正好k次反转的n元素排列的数量是多少？

例如,恰好1次反转的4元素排列的数量等于3.

为了使给定的示例更容易看到,这里有三个4元素排列,正好有1个反转:

(1, 2, 4, 3)
(1, 3, 2, 4)
(2, 1, 3, 4)

在第一个排列中,4> 3且指数4小于3的指数.这是单个反转.由于置换只有一次反转,因此它是我们试图计算的排列之一.

对于任何给定的n个元素序列,排列的数量是阶乘(n).因此,如果我使用强力n ²方法计算每个排列的反转次数,然后检查它们是否等于k,则该问题的解决方案将具有时间复杂度O(n!*n ²).

以前的研究

这个问题的一个子问题以前问这里在计算器上.给出了使用合并排序的O(n log n)解决方案,其计算单个排列中的反转次数.但是,如果我使用该解决方案来计算每个排列的反转次数,我仍然会得到O(n!*n log n)的时间复杂度,在我看来这仍然很高.

之前在Stack Overflow上也提到了这个确切的问题,但它没有收到任何答案.

如果没有数学公式来解决这个问题(我有点怀疑),那么我也看到人们提示有效的动态编程解决方案是可能的.使用DP或其他方法,我真的想制定一个比O(n!*n log n)更有效的解决方案,但我不确定从哪里开始.

欢迎任何提示,评论或建议.

编辑:我已经用DP方法回答了下面的问题来计算Mahonian数.