标签: combinations

我试图在几个数组中找到所有项目的组合.数组的数量是随机的(可以是2,3,4,5 ......).每个数组中的元素数量也是随机的......

例如,我有3个数组:

$arrayA = array('A1','A2','A3');
$arrayB = array('B1','B2','B3');
$arrayC = array('C1','C2');

我想生成一个3 x 3 x 2 = 18种组合的数组:

• A1,B1,C1
• A1,B1,C2
• A1,B2,C1
• A1,B2,C2
• A1,B3,C1
• A1,B3,C2
• A2,B1,C1
• A2,B1,C2 ......

问题是创建一个具有可变数量的源数组的函数...

有n个人编号从.1到n.我必须编写一个代码,用于生成和打印k这些人的所有不同组合n.请解释用于此的算法.

我参加了一个狂欢节,在每个地方,他们用特殊的打孔标记你的节目.打孔器是3x3空间的网格.在每个空间中,有一个针刺穿你的纸张或没有.这让我想知道你可以使用这个工具制作多少种不同的模式.我的第一个想法是:2 ^ 9 = 512,但是所有9个空间都是无针的并不是真正的一拳,所以真的:511.

然后复杂性打击了我.特别是因为工人们在打纸时并不是那么小心,所以这些看起来都很明显:

x..  .x.  ...  etc.
.x.  x..  .x.
...  ...  ..x

问题:如何编写测试以考虑轮换和转换？

到目前为止的勤奋和思想:

• 二元感觉就像这个等式的一个明显的部分
• 找到唯一模式后,将其存储在内存中,以便可以对其进行未来模式测试
• 有4种旋转可能性.
  编辑:我所说的"旋转"是指你可以采取任何形状并将其旋转90度.考虑左上角是点的图案.您可以将其旋转/旋转90度并获得右上角的点.再次这样做,它在右下方.再次,它在左下角.使用纯2 ^ 9计算,这些是4种不同的组合.然而,对于这个问题,这些正是我试图清除的那种重复.
• 对于每次旋转,有25种方法可以使3x3网格重叠:

重叠:

/ = the spaces in the new one to test
\ = the spaces in a verified unique one

1               2               25
/ / / . . . .   . / / / . . .   . . . . . . .
/ / / . . . .   . / …

我有一些代码可以计算排列和组合,我正在努力让它更适合大数字.

我已经找到了一个更好的排列算法,避免了大的中间结果,但我仍然认为我可以做更好的组合.

到目前为止,我已经提出了一个特殊情况来反映nCr的对称性,但我仍然希望找到一种更好的算法来避免调用阶乘(r),这是一个不必要的大中间结果.如果没有这个优化,最后一次doctest尝试计算阶乘(99000)需要太长时间.

任何人都可以建议一种更有效的方法来计算组合？

from math import factorial

def product(iterable):
    prod = 1
    for n in iterable:
        prod *= n
    return prod

def npr(n, r):
    """
    Calculate the number of ordered permutations of r items taken from a
    population of size n.

    >>> npr(3, 2)
    6
    >>> npr(100, 20)
    1303995018204712451095685346159820800000
    """
    assert 0 <= r <= n
    return product(range(n - r + 1, n + 1))

def ncr(n, r):
    """
    Calculate the number of unordered combinations of r items taken …

说我有y不同的值,我想x随机选择它们.这样做的有效算法是什么？我可以打电话给rand() x时间,但如果很大x,表现会很差y.

请注意,此处需要组合:每个值应具有相同的概率,但结果中的顺序并不重要.当然,任何生成排列的算法都是合格的,但我想知道如果没有随机顺序要求,是否可以更有效地做到这一点.

如何有效地生成0和上限N之间的K个非重复整数的列表,涵盖了这种情况的排列.

该R函数expand.grid返回所提供参数的元素之间的所有可能组合.例如

> expand.grid(c("aa", "ab", "cc"), c("aa", "ab", "cc"))
  Var1 Var2
1   aa   aa
2   ab   aa
3   cc   aa
4   aa   ab
5   ab   ab
6   cc   ab
7   aa   cc
8   ab   cc
9   cc   cc

你知道一种直接获得的有效方法(所以没有任何行比较之后expand.grid)只提供所提供的矢量之间的"唯一"组合吗？输出将是

  Var1 Var2
1   aa   aa
2   ab   aa
3   cc   aa
5   ab   ab
6   cc   ab
9   cc   cc

编辑每个元素与自身的组合最终可以从答案中丢弃.我实际上并不需要它在我的程序中,即使(数学上)aa aa将是一个元素Var1和另一个元素之间的一个(常规)唯一组合var2.

解决方案需要从两个向量生成元素对(即每个输入向量中的一个 - 以便它可以应用于多于2个输入)

我试图推断出一种算法,它生成特定大小的所有可能组合,就像一个接受一个字符数组和大小作为参数的函数,并返回一个组合数组.

示例:假设我们有一组字符:设置A = {A,B,C}

a)尺寸2的所有可能组合:(3 ^ 2 = 9)

AA, AB, AC
BA, BB, BC
CA, CB, CC

b)尺寸3的所有可能组合:(3 ^ 3 = 27)

AAA, AAB, AAC,
ABA, ABB, ACC,
CAA, BAA, BAC,
.... ad so on total combinations = 27

请注意,货币对的大小可能大于pouplation的总大小.防爆.如果set包含3个字符,那么我们也可以创建大小为4的组合.

编辑:另请注意,这与排列不同.在排列中我们不能有重复的字符,例如,如果我们使用置换算法,AA就不会出现.在统计中,它被称为抽样.

我的C#程序中有一个整数列表.但是,我只在运行时知道列表中的项目数.

让我们说,为了简单起见,我的列表是{1,2,3}现在我需要生成所有可能的组合,如下所示.{1,2,3} {1,2} {1,3} {2,3} {1} {2} {3}

有人可以帮忙吗？

评估n选择k值的最有效方法是什么？我认为蛮力方式是找到n阶乘/ k阶乘/(nk)阶乘.

更好的策略可能是根据这个递归公式使用dp .有没有其他更好的方法来评估n选择k？

我试图确定有多少种不同的方法可以从序列中删除一组值,保留原始序列的顺序(稳定),并确保从原始序列中只删除1个实例值.例如,如果我有 [1,2,1,3,1,4,4],我想删除[1,4,4]我得到的组合将是:

[1,2,1,3,1,4,4] \ [1,4,4] = [ [2,1,3,1], [1,2,3,1], [1,2,1,3] ]

要么 [1,2,1,3,1,4,4] \ [1,1] = [ [2,3,1,4,4], [1,2,3,4,4], [2,1,3,4,4] ]

我有javascript代码我写的所有数组值的组合没有删除和删除部分似乎应该很容易但我没有看到算法需要多次可能删除多个值.