标签: combinatorics

是否确定现在scipy.misc.comb确实比特别实施更快？

根据一个旧的答案,统计:Python中的组合,这个自制函数比scipy.misc.comb计算组合时更快nCr:

def choose(n, k):
    """
    A fast way to calculate binomial coefficients by Andrew Dalke (contrib).
    """
    if 0 <= k <= n:
        ntok = 1
        ktok = 1
        for t in xrange(1, min(k, n - k) + 1):
            ntok *= n
            ktok *= t
            n -= 1
        return ntok // ktok
    else:
        return 0

但是在我自己的机器上运行一些测试后,使用这个脚本似乎不是这样的:

from scipy.misc import comb
import random, time

def choose(n, k):
    """
    A fast way to …

我想要下面的代码,但"pythonic"风格或使用标准库:

def combinations(a,b):
    for i in a:
        for j in b:
             yield(i,j)

我的朋友们邀请我回家玩秘密圣诞老人的游戏,在那里我们应该抽出很多东西,并为小组中的朋友扮演'圣诞老人'的角色.

所以,我们写下所有的名字并随机选择一个名字.如果我们中的任何一个人最终选择了自己的名字,那么我们会重新洗牌并重新挑选名字(理由是一个人不能成为自己的圣诞老人).

我们有七个人在玩,所以我认为最后的"圣诞老人分配"是(1:7)对自身的排列,有一些限制.

我想邀请各种想法,关于我们如何使用Mathematica特定的或任何编程语言甚至算法来:

• 列出/打印出所有"有效"的圣诞老人分配
• 随着玩"秘密圣诞老人"的朋友数量增加,可扩展性

现在我正在尝试编写一个带有数组和整数n的函数,并给出每个大小为n的组合的列表(所以是int数组的列表).我能够使用n个嵌套循环编写它,但这仅适用于特定大小的子集.我无法弄清楚如何推广它适用于任何大小的组合.我想我需要使用递归？

这是3个元素的所有组合的代码,我需要一个适用于任意数量元素的算法.

import java.util.List;
import java.util.ArrayList;

public class combinatorics{
    public static void main(String[] args) {

        List<int[]> list = new ArrayList<int[]>();
        int[] arr = {1,2,3,4,5};
        combinations3(arr,list);
        listToString(list);
    }

    static void combinations3(int[] arr, List<int[]> list){
        for(int i = 0; i<arr.length-2; i++)
            for(int j = i+1; j<arr.length-1; j++)
                for(int k = j+1; k<arr.length; k++)
                    list.add(new int[]{arr[i],arr[j],arr[k]});
    }

    private static void listToString(List<int[]> list){
        for(int i = 0; i<list.size(); i++){ //iterate through list
            for(int j : list.get(i)){ //iterate through array
                System.out.printf("%d ",j);
            }
        System.out.print("\n");
        } …

干杯,

我知道你可以用下面的公式得到组合的数量(没有重复,顺序并不重要):

// Choose r from n

n! / r!(n - r)!

但是,我不知道如何在C++中实现它,因为例如

n = 52

n! = 8,0658175170943878571660636856404e+67

即使是unsigned __int64(或unsigned long long),这个数字也太大了.是否有一些解决方法来实现公式而没有任何第三方"bigint" - 库？

我想找到一个干净而聪明的方法(在python中)来查找1s和0s x chars long的字符串的所有排列.理想情况下,这将是快速的,不需要做太多的迭代......

因此,对于x = 1我想要:['0','1'] x = 2 ['00','01','10','11']

等等..

现在我有这个,这很慢,似乎不优雅:

    self.nbits = n
    items = []
    for x in xrange(n+1):
        ones = x
        zeros = n-x
        item = []
        for i in xrange(ones):
            item.append(1)
        for i in xrange(zeros):
            item.append(0)
        items.append(item)
    perms = set()
    for item in items:
        for perm in itertools.permutations(item):
            perms.add(perm)
    perms = list(perms)
    perms.sort()
    self.to_bits = {}
    self.to_code = {}
    for x in enumerate(perms):
        self.to_bits[x[0]] = ''.join([str(y) for y in x[1]])
        self.to_code[''.join([str(y) for y in …

我正在寻找一个合理快速的算法来计算OEIS序列A002845的术语.让我在这里重申它的定义.

设^表示取幂运算符.考虑具有n 2的形式2 ^ 2 ^ ... ^ 2的表达式,其中括号以所有可能的方式插入(可能的括号的数量由加泰罗尼亚数字给出).这些表达式中的一些将具有相同的值,例如(2 ^ 2)^ 2 = 2 ^(2 ^ 2).我们感兴趣的是给定n的不同值的数量.

通过直接计算这些表达式,有明显的暴力解决方案,但很明显,即使对于相对较小的n,所需的时间和空间也会迅速超过所有合理的限制.我对这个问题的多项式时间解决方案很感兴趣.

我一直想这样做但每次我开始思考这个问题时都会因为其指数性而引起我的注意.

我希望能够理解和编码的问题解决方案是倒计时数学问题:

给定数字X1到X5的集合计算如何使用数学运算来组合Y.您可以应用乘法,除法,加法和减法.

那怎么1,3,7,6,8,3做348？

答案:(((8 * 7) + 3) -1) *6 = 348.

如何编写可以解决这个问题的算法？在尝试解决这样的问题时你从哪里开始？在设计这样的算法时,您需要考虑哪些重要的考虑因素？

我有值池,我想通过从某些池中挑选来生成所有可能的无序组合.

例如,我想从池0,池0和池1中选择:

>>> pools = [[1, 2, 3], [2, 3, 4], [3, 4, 5]]
>>> part = (0, 0, 1)
>>> list(product(*(pools[i] for i in part)))
[(1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 3, 3), (1, 3, 4), (2, 1, 2), (2, 1, 3), (2, 1, 4), (2, 2, 2), (2, 2, 3), (2, 2, 4), (2, 3, 2), (2, 3, 3), (2, 3, 4), …

给定PHP字符串数组,例如:

['peter', 'paul', 'mary']

如何生成此数组元素的所有可能排列？即:

peter-paul-mary
peter-mary-paul
paul-peter-mary
paul-mary-peter
mary-peter-paul
mary-paul-peter