我知道如果我有以下一组数字
{ 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 }
我们可以建立多少个不同的 4 位数字？我知道答案是3360，只是不知道如何实现。
重要提示：在这种情况下，像“1123”或“1213”这样的数字应该是有效的组合，但不是“1113”，因为初始组中只有两个数字。
另外，对于组
{ 1, 1, 2, 2, 3, 4, 5, 6, 7, 8 }
应该有 2190 个 4 位数字。关于如何计算这些答案的任何想法？
这不是家庭作业，我将从特定硬件中获取这些数字，并根据组合的数量返回一些数据。
{ 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.
这是解决此类问题的一种相当简单的方法。还有其他一些（例如，包含/排除）更复杂，但如果您是第一次看到此类问题，当前的方法是最容易理解的。
您可能想要参考这个出色的组合学实现。
如果没有重复，这将非常容易。. . 为了
{ 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 组重复）。请注意，如果 set 中没有未在 selection_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 毫秒。
如果您需要在比您的示例更大的任何集合上执行此操作，请注意中间计算中的溢出。13！已经大到足以溢出 32 位 UINT。只有比这大一些会溢出 64 位。使用 float/double 并没有更好，因为如果没有完全精确，您会得到错误的答案。
在计算阶乘或任何乘法时，您需要使用任意精度整数类或一些包含完整因子列表的自定义数字类，然后进行因子消除以简化除法。
您需要在 2 种情况下解决问题：
案例1：你的4位数字中有0个或1个“1”排列的个数是9！/（9-4）！= 3024
案例 2：你的 4 位数字中有两个“1” 你知道其中两个数字必须是 1，所以有 8*7 种方法来选择剩余的两个数字。并且有 (4! / 2!) 排列两个“1”和另外两个数字的方法。因此，排列的数量是 8*7*(4! / 2!) = 672
看起来答案是 3024+672 = 3696