выберите подмножество размера k, выбрав только одно значение из каждого набора

Question

Учитывая массив из n элементов длины, где каждый элемент обозначает установленный размер, определите количество способов, которыми вы можете выбрать K установленного размера.

условие: вы не можете выбрать более одного элемента из одного набора. Как решить эту проблему (любая программа)

Примеры:

Ввод:

n = 4
k = 3
{1,2,1,1} Each value represents number of elements in each set

Выход: 7

Example : 

{1},{2,3},{4},{5}

{1,2,4}
{1,2,5}
{1,3,4}
{1,3,5}
{1,4,5}
{2,4,5}
{3,4,5}

Код i попробовал, но возвращает 10 значений, которые не соответствуют условию Какую ошибку я здесь сделал? они просто дали длину подмножества вместо фактического подмножества. Поэтому, основываясь на сумме всей длины подмножества, я формирую новый массив

count = 0

def printCombination(arr, n, r):
    global count
    data = [0]*r
    combinationUtil(arr, data, 0,
                    n - 1, 0, r)


def combinationUtil(arr, data, start,
                    end, index, r):
    global count

    if (index == r):

        for j in range(r):
            print(data[j], end=" ")
        print()
        count += 1
        return
    i = start
    while(i <= end and end - i + 1 >= r - index):
        data[index] = arr[i]
        combinationUtil(arr, data, i + 1,
                        end, index + 1, r)
        i += 1

in_val = [1,2,1,1] 
arr = list(range(1,sum(in_val)+1)) r = 3 
n = len(arr) 
printCombination(arr, n, r) 
print(count)

. Можем ли мы решить эту задачу с помощью некоторой формулы с минимальным временем, вместо того, чтобы моделировать каждое подмножество и проходить через него. Пожалуйста, осветите это или дайте мне предложение продолжить.

Answer 1

Предполагая, что все входные наборы не пересекаются, динамический c программный подход позволяет нам вычислить количество таких комбинаций за O(n) время, где n - количество наборов (при условии, что мощность входных наборов ограничена выше постоянной величиной, в противном случае временная сложность равна O(n, max_size), где max_size - мощность множества входных данных с максимальным размером).

import random # testing
from functools import lru_cache # memoization

xs = [{1},{2,3},{4},{5}]
k = 3
sizes = [len(x) for x in xs]
# [1, 2, 1, 1]

# dynamic programming approach
def count_combinations(sizes, k=3):
  @lru_cache(None)
  def f(n, k):
    if (n < k) or (k < 0):
      # no combination possible
      return 0
    elif n == k:
      # return product sizes[:n]
      res = 1
      for x in sizes[:n]:
        res *= x
      return res
    else:
      # recursive memoized call
      # f(n-1, k-1) ways to select k-1 elts from n-1 sets
      # times size of n-1'st set (counting from 0)
      # plus f(n-1, k) ways to select k elts from n-1 sets
      return sizes[n-1] * f(n-1, k-1) + f(n-1, k)
  return f(len(sizes), k)

# assert count_combs(sizes, k=k) == count_combinations(sizes, k)

---

# larger benchmark
n = 25
k = n // 2
xs = [{random.randint(0, n) for i in  range(n)} for _ in range(n)]
sizes = [len(x) for x in xs]

%time count_combs(sizes, k)          # O(n choose k), 8.6 s
%timeit count_combinations(sizes, k) # O(n), 112 µs

Это позволяет избежать рассмотрения всех возможных комбинаций размера k явно, уменьшая сложность от O(n choose k) до O(n).

Answer 2

Определите количество способов выбора размера K.

from itertools import combinations
from functools import reduce

def count_combs(arr, k):
  if k > len(arr):
    return 0  # Not possible
  elif k == len(arr):
    return reduce(lambda a, b: a*b, arr) # multiply values in arr
  else:
    """sum of answer to each sub-set of arr of size k
       subsets of arr of size k are combinations(arr, k)"""
    return sum(count_combs(x, k) for x in combinations(arr, k))

Тест

arr = [1, 2, 1, 1]
print(count_combs(arr, 3))
# Outputs 7

arr = [1, 1, 1, 1]
print(count_combs(arr, 3))
# Outputs 4

arr = [1, 1, 1, 2]
print(count_combs(arr, 2))
# Output 9

Пояснение

Три случая

1. k> len (обр.): Невозможно, поэтому ответ - 0
2. k == len (обр.): Количество возможных способов один элемент за раз из каждого индекса массива, который является произведением значений массива arr.
3. k