标签: combinatorics

我需要@k在给定的一组大小中生成所有大小的组合@n.有人可以查看以下SQL并首先确定以下逻辑是否返回预期结果,第二个是否有更好的方法？

/*CREATE FUNCTION dbo.Factorial ( @x int ) 
RETURNS int 
AS
BEGIN
    DECLARE @value int

    IF @x <= 1
        SET @value = 1
    ELSE
        SET @value = @x * dbo.Factorial( @x - 1 )

    RETURN @value
END
GO*/
SET NOCOUNT ON;
DECLARE @k int = 5, @n int;
DECLARE @set table ( [value] varchar(24) );
DECLARE @com table ( [index] int );

INSERT @set VALUES ('1'),('2'),('3'),('4'),('5'),('6');

SELECT @n = COUNT(*) FROM @set;

DECLARE @combinations int = …

我有一个问题,我必须分析500C5组合(255244687600)的东西.将其分布在10个节点的集群中,每个集群每秒处理大约10 ^ 6个组合,这意味着该作业将在大约7个小时内完成.

我遇到的问题是在10个节点上分配255244687600组合.我想给每个节点提供25524468760,但是我使用的算法只能顺序生成组合,我希望能够传递元素集和一系列组合指标,例如,[0 -10 ^ 7),[10 ^ 7,2.0 10 ^ 7)等,并让节点自己找出组合.

我目前使用的算法来自以下内容:

• http://howardhinnant.github.io/combinations.html

• Stack Overflow问题有效地计算矢量组合

我考虑过使用一个主节点,它枚举每个组合并将工作发送到每个节点.然而,从单个节点迭代组合并来回通信工作所产生的开销是巨大的,并且随后将导致主节点成为瓶颈.

是否有任何良好的组合迭代算法可以实现有效/最佳的分布式枚举？

我刚从同事那里得到了这个有趣的问题.我现在正在尝试,但同时我想我可以在这里分享.

使用Android主屏幕中显示的密码网格,可以使用多少有效密码？最小密码长度:4最大值:9(如果我错了,请纠正我)

我想要洗牌一系列独特的项目,但不要做一个完全随机的洗牌.我需要确保混洗列表中的元素与原始列表中的位置不同.因此,如果原始列表是(A,B,C,D,E),这个结果就可以了:(C,D,B,E,A),但这个不会:( C,E,A, D,B)因为"D"仍然是第四项.该列表最多包含七个项目.极端效率不是一个考虑因素.我认为这对Fisher/Yates的修改可以解决问题,但我不能用数学方法证明:

function shuffle(data) {
    for (var i = 0; i < data.length - 1; i++) {
        var j = i + 1 + Math.floor(Math.random() * (data.length - i - 1));

        var temp = data[j];
        data[j] = data[i];
        data[i] = temp;
    }
}

考虑一个正方形3乘3的非负整数网格.对于每一行i,整数之和设置为r_i.类似地,对于每列j,该列中的整数之和设置为c_j.因此,问题的实例由6非负整数描述.

是否存在一种有效的算法来计算在给定行和列和约束的情况下有多少不同的整数赋值给网格？

很明显,人们可以枚举所有可能的非负整数矩阵,其值最大sum r_i并检查每个矩阵的约束,但这将非常慢.

例

假设行约束1 2 3和列约束3 2 1.可能的整数网格是:

?????????????????????????????????????????????????????????????????????????
?0 0 1?0 0 1?0 0 1?0 1 0?0 1 0?0 1 0?0 1 0?1 0 0?1 0 0?1 0 0?1 0 0?1 0 0?
?0 2 0?1 1 0?2 0 0?0 1 1?1 0 1?1 1 0?2 0 0?0 1 1?0 2 0?1 0 1?1 1 0?2 0 0?
?3 0 0?2 …

考虑长度为n的所有二进制向量的集合S,其中每个包含正好m个; 所以每个载体都有nm零. 我的目标是从S构造一个数量k的向量,使得这些向量尽可能彼此不同.

举一个简单的例子,取n = 4,m = 2和k = 2,那么可能的解是:[1,1,0,0]和[0,0,1,1].

这似乎是编码理论文献中的一个开放性问题(？).

有没有办法(即算法)找到一个次优但好的解决方案？
汉明距离是在这种情况下使用的正确性能指标吗？

一些想法:
在本文中,作者提出了几种算法来找到向量子集,使得成对汉明距离> =某个值 d.
我已经实现了如下随机方法:取一个 SS,它由 S中的任何向量初始化.然后,我考虑 S中的剩余向量.对于这些矢量中的每一个,我检查该矢量相对于 SS中的每个矢量是否至少具有距离 d.如果是,则将其添加到 SS. 通过取最大可能 d,如果 SS的大小> = k,那么我将 SS视为最优解,并且我从 SS中选择 k个向量的任何子集.使用这种方法,我认为导致 SS将取决于初始向量的识别 SS ; 即有多种解决方案(？). 但是如果 SS的大小< k,怎么办？ 从本文提出的算法中,我只理解了随机算法.我对二进制词典搜索(第2.3节)感兴趣,但我不知道如何实现它(？).

Over the holidays, I was gifted a game called "Kanoodle Extreme". The details of the game are somewhat important, but I think I've managed to abstract them away. The 2D variant of the game (which is what I'm focusing on) has a number of pieces that can be flipped/rotated/etc. A given puzzle will give you a certain amount of a hex-grid board to cover, and a certain number of pieces with which to cover it. See the picture below for …

是否有直接的方法来获得nCr的所有组合的有序集合的第N个组合？

示例:我有四个元素:[6,4,2,1].通过一次取三个所有可能的组合将是:[[6,4,2],[6,4,1],[6,2,1],[4,2,1]].

有没有一个算法可以在有序的结果集中给出我的第三个答案,[6,2,1],而不需要列举所有以前的答案？

我想在一组组合中为每个组合预先计算一些值.例如,当从0到12中选择3个数字时,我将为每个数字计算一些值:

>>> for n in choose(range(13), 3):
    print n, foo(n)

(0, 1, 2) 78
(0, 1, 3) 4
(0, 1, 4) 64
(0, 1, 5) 33
(0, 1, 6) 20
(0, 1, 7) 64
(0, 1, 8) 13
(0, 1, 9) 24
(0, 1, 10) 85
(0, 1, 11) 13
etc...

我想将这些值存储在一个数组中,以便给定组合,我可以计算它并获取值.例如:

>>> a = [78, 4, 64, 33]
>>> a[magic((0,1,2))]
78

会magic是什么？

最初我想将它存储为尺寸为13 x 13 x 13的3维矩阵,因此我可以轻松地将其编入索引.虽然这对于13选择3来说是好的,但对于像13选择7这样的东西来说这会有太多的开销.

我不想使用dict,因为最终这个代码将在C中,无论如何数组都会更高效.

更新:我也有类似的问题,但使用重复的组合,所以任何关于如何获得这些的排名的答案将非常感激=).

更新:为了说清楚,我正在努力节省空间.这些组合中的每一个实际上都指向占用大量空间的东西,比方说2千字节.如果我使用13x13x13阵列,那将是4兆字节,其中我只需要572千字节使用(13选3)点.

基本上,给定一个正的非零数字的排序列表,比如{1,4,5},更改列表中的单个数字以最大化可能的不同组合.以上给出了1,4,5,6,9,10,即六种组合.如果我们要改变4到2所以我们有{1,2,5},我们得到1,2,3,5,6,7,8,即7种组合.

我需要找到一个数字x来添加到列表的单个数字,以最大化组合的数量.x应该是最小的abslout值,我们可以加或减.

我通过枚举使用蛮力来完成它,它在指数时间内运行很多次.因此,对于较大的问题,这是不可行的.现在我需要快速完成.

只检查组合数是指数时间吗？我必须找到确切的最佳解决方案.

解决这个问题的关键词是什么？我试图找到一个重复,所以我可以使用动态编程和某种分支和绑定来限制爆炸,但它是没用的.

我已经研究了切割机,子集和其他许多组合优化问题,看看我是否能找到一些想法.但我不明白.简单地验证解决方案是指数时间.