初始组上具有重复字符的组合

发布于 2024-08-03 23:53:15 字数 515 浏览 4 评论 0原文

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

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

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

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

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

我们可以构建多少个不同的 4 位数字？我知道答案是3360，只是不知道如何实现。

重要提示：在这种情况下，“1123”或“1213”等数字应该是有效的组合，但“1113”不是，因为初始组中只有两个。

此外，对于组

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

有应为 2190 4 位数字。关于如何计算这些答案有什么想法吗？

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

原文

I know that if I have the following group of numbers

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

I can have 5040 different 4-digit numbers, using 10! / (10 - 4)!

But if I repeat one number on the initial group, like

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

How many different 4-digit numbers can we build ? I know the answer is 3360, just don't know how to implement it.

Important: In this case, numbers like "1123" or "1213" should be valid combinations, but not "1113", as there are only two ones on the initial group.

Also, for the group

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

There should be 2190 4-digit numbers. Any ideas on how to calculate these answers ?

This is not homework, I'll get this numbers from a specific hardware and depending on the number of combinations, will return some data.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

橘和柠 2024-08-10 23:53:15

{ 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 }

现在我们考虑这里有几种组合。我们可以有零个 1、一个 1 或两个 1。在第一种情况下，有

(8 choose 4) * 4!

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

(8 choose 3) * 4!

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

(8 choose 2) * 4! / 2!

可能的组合。最后一个需要解释。有八个可能的非 1 数字可供选择，我们选择两个。剩下的两个数字是 1（假设我们的 4 串包含两个 1）。我们可以将这四位数字按任何顺序排列，但是 1 是可以互换的，因此我们除以 1 的可能排序数量（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 }

对于再次有几种组合。我们可以有零个 1 和零个 2、一个 1 和零个 2、两个 1 和零个 2、两个 1 和一个 2、两个 1 和两个 2、零个 1 和一个 2、零个 1 和两个 2、一个 1 和两个 2 ，以及一个 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.

这是解决此类问题的一种相当简单的方法。还有其他一些（例如，包含/排除）更复杂，但当前如果您是第一次看到此类问题，那么这种方法是最容易理解的。

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

Here you are choosing four numbers from ten and they can be any order. Thus the solution is

(10 choose 4) * 4! = 5040.

Now we consider the case of

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

There are a few combinations here. We can have zero 1s, one 1 or two 1s. In the first case there are

(8 choose 4) * 4!

possible combinations. In the second case there are

(8 choose 3) * 4!

possible combinations. In the third case there are

(8 choose 2) * 4! / 2!

possible combinations. This last one requires explanation. There are eight possible non 1 digits to choose from and we are choosing two. The two remaining digits are 1s (by assumption that we are in the case where are our 4-string contains two 1s). We can put these four digits in any order however the 1s are interchangeable so we divide by the number of possible orderings of the 1s (2!).

Thus the answer is

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

For the case of

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

there are again a few combinations. We can have zero 1s and zero 2s, one 1 and zero 2s, two 1s and zero 2s, two 1s and one 2, two 1s and two 2s, zero 1s and one 2, zero 1s and two 2s, one 1 and two 2s, and one 1 and one 2. These can be worked out as above and the final answer is

(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.

This a fairly simplistic approach to problems of this sort. There are others (for example, inclusion/exclusion) that are more sophisticated but the current approach is the easiest to understand if you're seeing problems of this sort for the first time.

回复收藏 0 原文

离线来电— 2024-08-10 23:53:15

您可能需要参考这个出色的组合学实现。

回复收藏 0 原文

夏末的微笑 2024-08-10 23:53:15

这将非常容易，无需重复。。。因为

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

由于您只有 9 个不同的选择（而不是原始问题中的 10 个），所以答案应该是 9！ /（9 - 4）！

（顺便说一下，如果允许重复，实际上可以有更多不同的 4 位数字，即 4456。那么答案就是 9^4 个 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 个 1，或 3 组重复项）。请注意，如果集合中没有任何数字不在 Choices_picked 中（即，您有一个唯一的数字重复 10 次），它也会爆炸。

编辑 3：关于使用此算法对大型集合进行了多少次函数调用，我使用以下函数调用进行了测试，为每个对 cnt_unique 的非平凡（count_left >= 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

因此，对于 100元素集每个数字 1-50 有 2 个条目，共有 1276 个调用。而且执行速度相当快； time.time() 的一个周期为 15 毫秒，因此它的执行时间通常小于 15 毫秒。

This would be pretty easy without duplication . . . for

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

Since you only have 9 distinct choices (as opposed to the 10 in the original problem), the answer should be 9! / (9 - 4)!

( By the way, you can actually have more different 4-digit numbers if you allow repetition, i.e. 4456. Then the answer would just be 9^4 4-digit numbers. )

Similarly, {1, 1, 2, 2, 3, 4, 5, 6, 7, 8 } has 8 distinct choices, so the answer should be 8! / (8 - 4)! by your original math.

Edit and actual answer: Maybe you meant that if the 1 is duplicated in your set, you can use two 1's in the answer?

Edit 2: Working, tested python module provided

In that case, you might try calculating the distinct number of possibilities, and then adding the results with duplicates, as the following python code suggests):

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)

OK, I've verified by hand that algorithm works for all of your cases presented above. I'm fairly confident it works in more general cases, but I don't have time at the moment to do any additional test cases (for instance, if there were 3 1's, or 3 groups of duplicates). Note it would also blow up if there were no numbers in set which were not in choices_picked (ie you have one unique number duplicated 10 times).

Edit 3: Regarding how many function calls are made with this algorithm for large sets, I tested with the following function call, incrementing a variable once for each non-trivial (count_left >= 0) call to cnt_unique:

>>> 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

So, for a 100 element set with 2 entries for each number 1-50, there were 1276 calls. And it executes quite fast; one tick with time.time() is 15 ms, so it executes in typically less than 15 ms.

回复收藏 0 原文