algorithm - 计算可被 k 整除的 m 元素集的 n 元素子集的算法

Question

假设 {1, 2, 3, ..., m} 是一个集合。我从这个集合中选择了 n 个不同的元素。我可以编写一个算法来计算总和可被 k 整除的此类子集的数量（排序无关紧要）吗？

如果订购很重要，这个问题会容易得多，但事实并非如此，我也不知道如何解决。有人可以帮忙吗？

Answer 1

这可以通过类似于下面概述的方法在时间 O(n·k·m) 和空间 O(n·k) 中完成。让 S 成为你的集合，包含 m 个元素。根据集合和子集的定义，S 的所有元素都是不同的，任何 S 子集的所有元素也是如此。

首先，考虑一个更简单的问题，我们计算具有任意数量元素而不是恰好 n 个元素的 S-子集。令 N(W,r) 为 W 子集 U 的数量，使得 ΣU（U 的元素之和）等于 r mod k。如果 W 是 S 的子集，令 W' 为 W + z，其中 z ∈ S\W；也就是说，z 是 S 中尚未在 W 中的元素。现在 N(W', (r+z)%k) = N(W, (r+z)%k) + N(W, r) 因为 N (W, (r+z)%k) 是不包含 z 且具有 ΣU≡(r+z)%k) 的 W'-子集 U 的数量，N(W, r) 是 W' 的数量- 子集 U 与 ΣU≡(r+z)%k) 确实包含 z。重复这个结构，依次处理 S 的每个元素，直到 W' = S，此时所需的答案是 N(S,0)。时间是O(k·m)，空间是O(k)。

为了使上述过程适应精确的子集大小，将 N(W,r) 更改为 N(W,h,r)，其中 h 是子集大小，并将 N(W',r) 的方程调整为 N(W ',h,r) 以显而易见的方式。时间是O(k·n·m)，空间是O(k·n)。

Answer 2

set -> 所有元素都不同。

创建一个数组来描述每个 numberclass 有多少代表：

ncnt=new int[k]
for x in elements{
  ncnt[x%k]++;
}

动态规划：

int waysToCreate(int input_class,int class_idx, int n){
  int ways=0
  // not using this class:
  if(class_idx+1 < k )
    ways+=waysToCreate(input_class,class_idx+1,n);
  for( int i=1;i < ncnt[class_idx] && i<=n ){
    int new_input_class=(input_class+i*class_idx)%k;
    if(i == n && new_input_class != 0){
      break; // all elements are used, but doesn't congrunent with 0 (mod k)
    }
    int subways=1;
    if(class_idx+1 < k )
      subways=waysToCreate(new_input_class,class_idx+1,n-i)

    ways+=nchoosek(ncnt[class_idx],i) * subways;
  }
  return ways;
}

启用记忆waysToCreate，nchoosek

Answer 3

它可以工作，但速度很慢

 /**
 * List all k  size subset of a given list with n unique elements.
 * n can be bigger than 64. this function will take O(K^N) time, Bad.
 *
 * @param list
 * @param subSetSize
 * @param subSet
 * @param indexFrom
 * @param indexEnd
 */
private static void subSetOf(List<Integer> list, int subSetSize, Set<Integer> subSet, int indexFrom, int indexEnd) {
    if (subSet == null) {
        assert 0 < subSetSize && subSetSize <= list.size();
        subSet = new HashSet(subSetSize);
    }
    if (subSetSize <= 64) {
        // Todo using bitwise trick
    }
    for (int index = indexFrom; index <= indexEnd; index++) {
        subSet.add(list.get(index));
        if (subSet.size() == subSetSize) {
            System.out.println(Arrays.toString(subSet.toArray()));
            // check the sum of this subset is satisfied or not by sum/k
        }
        if (subSet.size() < subSetSize) {
            subSetOf(list, subSetSize, subSet,
                    index + 1,
                    list.size() - (subSetSize - subSet.size()));
        }
        subSet.remove(list.get(index));
    }
}

public static void subSetOf(List<Integer> list,
                            int subSetSize,
                            Set<Integer> subSet) {
    subSetOf(list, subSetSize, subSet, 0, list.size() - subSetSize);
}