Это было бы довольно легко без дублирования. , , для
{ 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: Что касается количества вызовов функций с помощью этого алгоритма для больших наборов, я проверил следующий вызов функции, увеличивая переменную один раз для каждого нетривиального (count_left> = 0) вызова 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
Таким образом, для набора из 100 элементов с 2 записями для каждого номера 1-50 было 1276 вызовов. И это выполняется довольно быстро; один тик с time.time () равен 15 мс, поэтому он выполняется менее чем за 15 мс.