初始群上重复循环的组合数学

Question

我知道如果我有以下的一组数字

{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

我可以有5040个不同的4位数字，使用10！/(10-4)！

但是如果我在初始组重复一个数字，就像

{ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

我们能建多少个不同的四位数？我知道答案是3360，只是不知道如何实现。

重要:在这种情况下，像"1123“或"1213”这样的数字应该是有效的组合，而不是"1113"，因为在初始组中只有两个。

另外，对于这个团体

{ 1, 1, 2, 2, 3, 4, 5, 6, 7, 8 }

应该有2190个4位数的数字。对如何计算这些答案有什么想法吗？

这不是家庭作业，我将从一个特定的硬件获得这个数字，并根据组合的数量返回一些数据。

Answer 1

{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

在这里，您从十中选择四个数字，它们可以是任何订单。因此，解决办法是

(10 choose 4) * 4! = 5040.

现在我们考虑的是

{ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

这里有几个组合。我们可以有0 1s，1 1或2 1s。在第一种情况下，

(8 choose 4) * 4!

可能的组合。在第二种情况下，

(8 choose 3) * 4!

可能的组合。在第三种情况下

(8 choose 2) * 4! / 2!

可能的组合。最后一个问题需要解释。有八个可能的非1位数字可供选择，我们正在选择两个。剩下的两个数字是1s (假设我们的4字符串包含两个1s)。我们可以把这四个数字按任意顺序排列，但是1s是可互换的，所以我们除以1s (2!)的可能顺序数。

因此，答案是

(8 choose 4) * 4! + (8 choose 3) * 4! + (8 choose 2) * 4! / 2! = 3360.

就.而言

{ 1, 1, 2, 2, 3, 4, 5, 6, 7, 8 }

还有几个组合。我们可以有0 1s和0 2s，1 1和0 2s，2 1s和0 2s，2 1s和1 2 s，0 1s和2 2s，0 1s和1 2，0 1s和2 s，1 1和2 s，1 1和2 s，以及1 1和1 2。

(6 choose 4) * 4!
    + 2 * (6 choose 3) * 4!
    + 2 * (6 choose 2) * 4! / 2!
    + (6 choose 2) * 4!
    + 2 * (6 choose 1) * 4! / 2!
    + (6 choose 0) * 4! / (2! * 2!)
= 2190.

这是一种相当简单化的方法来解决这类问题。还有一些(例如，包容/排斥)更复杂，但是如果您第一次看到这类问题，当前的方法是最容易理解的。

Answer 2

您可能希望引用这个杰出的组合实现。

Answer 3

这将是相当容易的，没有重复。。。为

{ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

由于您只有9个不同的选择(相对于原来问题中的10个)，答案应该是9！/(9-4)！

(顺便说一句，如果你允许重复，即4456，你实际上可以有更多不同的4位数字。那么答案就是9^4位数。)

同样，{1，1，2，2，3，4，5，6，7，8}有8个不同的选择，所以答案应该是8！/(8-4)！根据你最初的数学。

编辑和实际答案：也许您的意思是，如果1在您的集合中被复制，您可以在答案中使用两个1？

编辑2:提供工作，经过测试的python模块

在这种情况下，您可以尝试计算不同数量的可能性，然后按照下面的python代码所建议的那样，使用重复的结果添加结果：

import math

def set_exclude(a, b):
    result = []
    for i in a:
        if not i in b:
            result.append(i)
    return result

def cnt_unique(aset, choices_picked, count_left, count_total):
    # Sanity check
    if count_left < 0:
        return 0
    if count_left == 0:
        return math.factorial(count_total)
    # Do non-duplicate combinations first
    # Set unprocessed = (set without any elements in choices_picked)
    unprocessed = set_exclude(aset, choices_picked)
    temp = len(set(unprocessed))

    # If we have no more valid items to choose from, this is impossible
    if temp >= count_left:
        result = math.factorial(temp) / math.factorial(temp - count_left) / \
                 math.factorial(count_left) * math.factorial(count_total)
    else:
        result = 0

    # Now find duplicate-involving combinations
    for member in set(unprocessed):
        valid = True
        for contest in choices_picked:
            if contest >= member:
                valid = False
                break

        if valid:
            count = unprocessed.count(member)
            new_choices = choices_picked + [ member ]
            for i in range(2, count+1):
                result_temp = cnt_unique(aset, new_choices, \
                  count_left - i, count_total)
                if result_temp != 0:
                    result_temp //= math.factorial(i)
                    result += result_temp
    return result

aset = [ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
result_size = 4
combinations = cnt_unique(aset, [], result_size, result_size)

好的，我已经手工验证了算法适用于以上所有的情况。我很有信心它能在更一般的情况下工作，但是我现在没有时间去做任何额外的测试用例(例如，如果有3组重复的话)。注意，如果集合中没有choices_picked中的数字(即有一个唯一的数字重复了10次)，它也会爆炸。

编辑3:关于使用此算法对大集合执行多少次函数调用，我使用以下函数调用进行了测试，每次对cnt_unique的非平凡( >= 0)调用递增一次变量：

>>> def test():
        b = [0]
        c = time.time()
        result = cnt_unique(range(1,51) + range(1,51), [], 4, 4, b)
        c = time.time() - c
        print("Result: " + str(result))
        print("Time: " + str(c))
        print("Calls: " + str(b[0]))

>>> test()
Result: 6240150
Time: 0.0150001049042
Calls: 1276

因此，对于每一个数字1-50有两个条目的100个元素集，有1276个调用。它执行得相当快；time.time()的一个滴答是15 ms，所以它通常在小于15 ms的时间内执行。