标签: combinatorics

给定两个列表,我可以生成这两个列表的笛卡尔积的所有排列的列表:

permute :: [a] -> [a] -> [[a]]
permute xs ys = [ [x, y] | x <- xs, y <- ys ]

Example> permute [1,2] [3,4] == [ [1,3], [1,4], [2,3], [2,4] ]

如何扩展置换,以便不使用两个列表,而是获取列表的列表(长度为n)并返回列表列表(长度为n)

permute :: [[a]] -> [[a]]

Example> permute [ [1,2], [3,4], [5,6] ]
            == [ [1,3,5], [1,3,6], [1,4,5], [1,4,6] ] --etc

我在Hoogle上找不到任何相关的东西..唯一与签名相匹配的功能是transpose,它不会产生所需的输出.

编辑:我认为这个2列表版本基本上是笛卡尔积,但我不能完全实现n-ary笛卡尔积.有什么指针吗？

在标准python库中是否有很好的匈牙利算法实现？

在组合数学中,Langford配对,也称为Langford序列,是2n数字序列1, 1, 2, 2, ..., n,n 的排列,其中两个分开一个单元,两个分开两个单元,更一般地,每个数字的两个副本k是k个单位.

例如:

Langford配对n = 3由序列给出2,3,1,2,1,3.

• 在haskell或中解决这个问题的好方法是什么？C
• 你能建议一个算法来解决它(不想使用蛮力)？

--------------------------编辑----------------------
怎么样我们可以定义数学规则,将@ Rafe的代码放入haskell中

如何计算大n和和的二项式系数模数142857 r.142857有什么特别之处吗？如果问题是模数p在哪里p是素数那么我们可以使用卢卡斯定理但是应该为142857做什么.

假设我们有n投掷k球的垃圾箱.什么是快速(即使用numpy/scipy而不是python代码)方式来生成所有可能的结果作为矩阵？

例如,如果n = 4和k = 3,我们需要以下内容numpy.array:

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

我正在寻找一个java库,它将生成一个集合的所有可能的顺序排列.我能找到的唯一一个库是google代码上的combinatoricslib.我发现很难相信这是唯一能够做到这一点的java库,我很坦率地对此非常惊讶.

JDK中有什么东西,或apache commons math或其他库提供相同的功能吗？

我很高兴使用combinatoricslib,我只是无法相信这是唯一的选择,除了自己编写算法,这当然不是那么困难,但是.isBlankOrNull()和apache commons都没有.

考虑以下数组:

$a = [['x'], ['y', 'z', 'w'], ['m', 'n']];

如何从中生成以下数组:

$output=[
[[x][y][m]],
[[x][z][n]],
[[x][w][m]],
[[x][y][n]],
[[x][z][m]],
[[x][w][n]],
];

我正在寻找比我更有效的代码.(我目前的代码如下所示)

我希望能够索引幂集的元素而不将整个集扩展到内存中(la itertools)

此外,我希望索引是基数排序.所以索引0应该是空集,索引2**n - 1应该是所有元素

到目前为止我发现的大多数文献都涉及产生感应电源.它不会让你只是潜入任何索引.我对此索引编制的动机是为分布式执行分割问题,如果远程计算机可以在任何地方潜入而不在群集中共享迭代器引用,则会很有帮助.

编辑:Blckknght建议我追求的解决方案,如下所示

from scipy.misc import comb

def kcombination_to_index(combination):
    index = 0
    combination = sorted(combination)
    for k, ck in enumerate(combination):
        index += comb(ck, k+1, exact=True)
    return index

def index_to_kcombination(index, k):
    result = []
    for k in reversed(range(1, k+1)):
        n = 0
        while comb(n, k, exact=True) <= index:
            n +=1
        result.append(n-1)
        index -= comb(n-1, k, exact=True)

    return result

class PowerSet:
    def __init__(self, elements):
        self.elements = elements

    def __len__(self):
        return 2 ** len(self.elements)

    def __iter__(self):
        for i in …

我有一个优化问题,我想知道是否有一个聪明的方法来解决它.(这可能已经被广泛研究过,我只是不知道要查找它的名称.)

我有一个(编辑:免费)有限生成的阿贝尔群G,在n发电机上.我还有一组P元素G,每个元素都标有严格正数的成本.所有的生成器都G出现在P,因此总是可以表达G作为元素P或其反转的产物的任何元素.任何此类产品的成本是P其中出现的元素的成本之和,并考虑它们出现的频率.表示身份元素的nullary产品的成本G为零.

考虑到该组的一个元素,我想找到一种方法来找到一个最低成本的产品,用它的元素来表达它P.

将其转换为最短路径问题是没有负面的自行车(在无限图上,但对于任何给定的元素,您只需要在标识元素附近的有限部分).将它转换为整数线性编程问题也很简单.

可能是其中一种翻译是要走的路？或者此问题的其他结构是否导致更容易的方法呢？在我的实际问题5 <= n <= 10和我感兴趣的元素中,从来没有大于+/- 20的任何发生器的多重性.

我在Haskell工作,因此功能方法优先于有状态方法,但有状态方法也可以.

我正在寻找Julia中的(希望内置)函数来计算组合的数量

我显然可以使用阶乘法来实现自己,但我几乎可以肯定有人已经对此感到担忧.