计算包含集合所有元素的子集的集合

Question

给定一个包含m 1的集合s（m），计数所有非空子集的集合，以便每个集合的联合生成s（m）。子集的基数也可以是k，其中1＆lt;k＆lt; = m和m最多可将值提取到10^5。

S(M) = {1,1,1,1}, K = 2.
possible collections can be 
{{1,1},{1,1}},
{1},{1},{1,1}},
{{1,1},{1},{1}}

我已经看过一些答案，但我相信它们与我的答案不同。

我还读过Stirling数量的第二类，但我仍在希望将子集的基数条件纳入该公式。

我已经编码了一种可能的递归解决方案，该解决方案不适合M.

的大量值。

请让我知道是否有人需要更多信息。

任何帮助或指导将不胜感激。

问候

ajay

Answer 1

如果我正确地理解了这个问题中的术语，您正在问有多少方法将序列abcdefghij分开，长度为m将单词（例如，abc de fgh ij ...）的长度不超过 k 。（在给出的示例中，答案为五个：A B C D，A B CD，A BC D，AB C D和AB CD。）这是恒星和条形解决的问题的一种偶，因为限制在大小上，

的子集而不是子集。

我没有尝试过封闭形式的解决方案，但是直接的动态编程攻击在O（ m ^2 k ）中起作用。 c _n是第一个 n 字母的可能性数。 c _0 = 1，并且对于所有 n ＆lt; 0。对于 n > 0，我们有 c _n = sum（ i = [1 .. k ]） c _（ n - i ）。只需按顺序计算值，直到您到达 c _m。（当然，将最后一个 k 值保持在用作SIPO Shift寄存器的队列中是足够的。）

请注意，这些值的速度非常快：使用 m = 100和 k = 2，我获得了5.7e20的可能性；将 k 更改为10给出6.1E29。提到的10^5的 m （再次使用 k = 2）给出4.2E20898。因此，我将 m 的额外因素包括在对应于任意推测算术的复杂性中。

Answer 2

该方法应为

Given M and K
Find the max number of divisions(subsets)
Find the min number of divisions(subsets)
Iterate from max to min using i
-Apply DP to find different combinations of sizes of subsets. 
-A permutation of each combination should yield a count for that number of combinations(i). 
-Sum up all the counts.

以下是使用DP的Java实现此逻辑。变量step和toGo分别对应M和K。我尝试使用一些随机数，但很低。

注意：您还需要更新静态数组尺寸 使用m。

的巨大值时

import java.util.Arrays;
public class HelloWorld{

    public static int step = 4;
    public static long[][] dMem = new long[100][100];
     public static void main(String []args){
        int toGo = 30;
        int max = toGo;
        int min = toGo/step;
        long temp = 0;
        long count = 0;
        for(int i = max; i >= min; i--){
            temp = nSteps(i, toGo);
            temp = temp == -1 ? 0 : temp;
            count += temp;
           // System.out.println(count+"n");
        }
        System.out.println("Num of ways = "+count);
     }
     public static long nSteps( int n, int toGo ){
         long steps = 0, temp = 0;
         //System.out.println(" n = "+n+" toGo = "+toGo);
         if( n == toGo ) return 1;
         if( n > toGo || n <= 0 || toGo <= 0) return -1;
         if( dMem[n][toGo] != 0 ) return dMem[n][toGo];
         for( int i = 1; i <= step; i++){
             temp = nSteps( n-1, toGo-i );
             temp = temp == -1 ? 0 : temp;
             steps += temp;
         }
         steps = steps == 0 ? -1 : steps;
         dMem[n][toGo] = steps;
         return steps;
     }
}