当前位置： 文江博客话题详情

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

发布于 2024-08-03 23:53:15 字数 515 浏览 2 评论 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.

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

扫码二维码加入Web技术交流群

发布评论

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

评论（5）

橘和柠 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.

回复 原文
离线来电— 2024-08-10 23:53:15

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

You might want to reference this outstanding Combinatorics implementation.

回复 原文
夏末的微笑 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.

回复 原文
聆听风音 2024-08-10 23:53:15

如果您需要在任何大于示例的集合上执行此操作，请注意中间计算中的溢出。 13！已经大到足以溢出 32 位 UINT。只有少数比这个大的数才会溢出 64 位。使用 float/double 也好不了多少，因为你会得到错误的答案而不具有完全的精度。

在计算阶乘或任何乘法时，您需要使用任意精度整数类或一些带有完整因子列表的自定义数字类，然后进行因子消除以简化除法。

If you need to do this on any set larger than your example, watch out for overflows in your intermediate calculations. 13! is already large enough to overflow a 32-bit UINT. Only a few larger than that will overflow 64 bits. Using float/double isn't any better since you'll get the wrong answer without full precision.

You would need to use an arbitrary precision integer class or some custom numeric class that carries the full list of factors when calculating the factorial or any multiplies, then doing factor elimination to simplify the division.

回复 原文
风向决定发型 2024-08-10 23:53:15

您需要分两种情况解决该问题：

情况 1：您的 4 位数字中有零个或一个“1”
排列数是9！ /（9-4）！ = 3024

情况2：您的4位号码中有两个“1”
你知道其中两位必须是 1，所以有 8*7 种方法来选择剩下的两位。有 (4!/2!) 种方法来排列两个“1”和另外两个数字。
因此，排列数为 8*7*(4!/ 2!) = 672

看起来答案是 3024+672 = 3696

You need to break the problem in 2 cases:

Case 1: zero or one "1" in your 4-digit number
Number of permutation is 9! / (9-4)! = 3024

Case 2: two "1"s in your 4-digit number
You know two of the digits must be 1, so there are 8*7 ways to select the remaining two digits. And there are (4! / 2!) ways to arrange the two "1"s and two other digits.
Hence, the number of permutation is 8*7*(4! / 2!) = 672

It looks like the answer is 3024+672 = 3696

回复 原文
~没有更多了~

关于作者

冷…雨湿花

暂无简介

0 文章
0 评论
23 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

qq_FjTq5B

文章 0 评论 0

18273202778

文章 0 评论 0

WordPress小学生

文章 0 评论 0

〃温暖了心ぐ

文章 0 评论 0

迷乱花海

文章 0 评论 0

niuniu

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文