87

的幂集{1, 2, 3}是:

{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}

假设我Set在 Java 中有一个:

Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
Set<Set<Integer>> powerSet = getPowerset(mySet);

如何以尽可能好的复杂性顺序编写函数 getPowerset?(我认为它可能是 O(2^n)。)

4

27 回答 27

102

是的,O(2^n)确实如此,因为您需要生成2^n可能的组合。这是一个使用泛型和集合的工作实现:

public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
    Set<Set<T>> sets = new HashSet<Set<T>>();
    if (originalSet.isEmpty()) {
        sets.add(new HashSet<T>());
        return sets;
    }
    List<T> list = new ArrayList<T>(originalSet);
    T head = list.get(0);
    Set<T> rest = new HashSet<T>(list.subList(1, list.size())); 
    for (Set<T> set : powerSet(rest)) {
        Set<T> newSet = new HashSet<T>();
        newSet.add(head);
        newSet.addAll(set);
        sets.add(newSet);
        sets.add(set);
    }       
    return sets;
}  

并根据您的示例输入进行测试:

 Set<Integer> mySet = new HashSet<Integer>();
 mySet.add(1);
 mySet.add(2);
 mySet.add(3);
 for (Set<Integer> s : SetUtils.powerSet(mySet)) {
     System.out.println(s);
 }
于 2009-11-03T23:40:22.317 回答
31

实际上,我编写的代码可以满足您在 O(1) 中的要求。问题是你接下来打算用 Set做什么。如果你只是要调用size()它,那就是 O(1),但如果你要迭代它,那显然是O(2^n).

contains()会是O(n),等等。

你真的需要这个吗?

编辑:

该代码现在在 Guava 中可用,通过方法公开Sets.powerSet(set)

于 2009-11-04T00:21:09.863 回答
12

这是我使用生成器的解决方案,其优点是,整个电源组永远不会一次存储......因此您可以一个接一个地对其进行迭代,而无需将其存储在内存中。我想这是一个更好的选择......注意复杂性是相同的,O(2 ^ n),但内存需求减少了(假设垃圾收集器的行为!;))

/**
 *
 */
package org.mechaevil.util.Algorithms;

import java.util.BitSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

/**
 * @author st0le
 *
 */
public class PowerSet<E> implements Iterator<Set<E>>,Iterable<Set<E>>{
    private E[] arr = null;
    private BitSet bset = null;

    @SuppressWarnings("unchecked")
    public PowerSet(Set<E> set)
    {
        arr = (E[])set.toArray();
        bset = new BitSet(arr.length + 1);
    }

    @Override
    public boolean hasNext() {
        return !bset.get(arr.length);
    }

    @Override
    public Set<E> next() {
        Set<E> returnSet = new TreeSet<E>();
        for(int i = 0; i < arr.length; i++)
        {
            if(bset.get(i))
                returnSet.add(arr[i]);
        }
        //increment bset
        for(int i = 0; i < bset.size(); i++)
        {
            if(!bset.get(i))
            {
                bset.set(i);
                break;
            }else
                bset.clear(i);
        }

        return returnSet;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Not Supported!");
    }

    @Override
    public Iterator<Set<E>> iterator() {
        return this;
    }

}

要调用它,请使用以下模式:

        Set<Character> set = new TreeSet<Character> ();
        for(int i = 0; i < 5; i++)
            set.add((char) (i + 'A'));

        PowerSet<Character> pset = new PowerSet<Character>(set);
        for(Set<Character> s:pset)
        {
            System.out.println(s);
        }

它来自我的 Project Euler 库... :)

于 2010-06-20T07:17:42.440 回答
10

如果 n < 63,这是一个合理的假设,因为无论如何尝试构造幂集都会耗尽内存(除非使用迭代器实现),这是一种更简洁的方法。二进制操作比Math.pow()掩码的数组快得多,但不知何故 Java 用户害怕它们......

List<T> list = new ArrayList<T>(originalSet);
int n = list.size();

Set<Set<T>> powerSet = new HashSet<Set<T>>();

for( long i = 0; i < (1 << n); i++) {
    Set<T> element = new HashSet<T>();
    for( int j = 0; j < n; j++ )
        if( (i >> j) % 2 == 1 ) element.add(list.get(j));
    powerSet.add(element); 
}

return powerSet;
于 2013-02-11T18:57:10.967 回答
9

是一个准确描述您想要的内容的教程,包括代码。你是对的,复杂度是 O(2^n)。

于 2009-11-03T23:41:42.533 回答
7

我根据@Harry He 的想法提出了另一个解决方案。可能不是最优雅的,但据我了解:

让我们以 SP(S) = {{1},{2},{3}} 的经典简单示例 PowerSet 为例。我们知道得到子集数量的公式是 2^n(7 + 空集)。对于此示例,2^3 = 8 个子集。

为了找到每个子集,我们需要将 0-7 十进制转换为二进制表示,如下面的转换表所示:

转换表

如果我们逐行遍历表,每一行都会产生一个子集,每个子​​集的值将来自启用的位。

Bin Value 部分中的每一列对应于原始输入 Set 中的索引位置。

这是我的代码:

public class PowerSet {

/**
 * @param args
 */
public static void main(String[] args) {
    PowerSet ps = new PowerSet();
    Set<Integer> set = new HashSet<Integer>();
    set.add(1);
    set.add(2);
    set.add(3);
    for (Set<Integer> s : ps.powerSet(set)) {
        System.out.println(s);
    }
}

public Set<Set<Integer>> powerSet(Set<Integer> originalSet) {
    // Original set size e.g. 3
    int size = originalSet.size();
    // Number of subsets 2^n, e.g 2^3 = 8
    int numberOfSubSets = (int) Math.pow(2, size);
    Set<Set<Integer>> sets = new HashSet<Set<Integer>>();
    ArrayList<Integer> originalList = new ArrayList<Integer>(originalSet);
    for (int i = 0; i < numberOfSubSets; i++) {
        // Get binary representation of this index e.g. 010 = 2 for n = 3
        String bin = getPaddedBinString(i, size);
        //Get sub-set
        Set<Integer> set = getSet(bin, originalList));
        sets.add(set);
    }
    return sets;
}

//Gets a sub-set based on the binary representation. E.g. for 010 where n = 3 it will bring a new Set with value 2
private Set<Integer> getSet(String bin, List<Integer> origValues){
    Set<Integer> result = new HashSet<Integer>();
    for(int i = bin.length()-1; i >= 0; i--){
        //Only get sub-sets where bool flag is on
        if(bin.charAt(i) == '1'){
            int val = origValues.get(i);
            result.add(val);
        }
    }
    return result;
}

//Converts an int to Bin and adds left padding to zero's based on size
private String getPaddedBinString(int i, int size) {
    String bin = Integer.toBinaryString(i);
    bin = String.format("%0" + size + "d", Integer.parseInt(bin));
    return bin;
}

}
于 2013-08-16T19:40:02.217 回答
5

如果您使用的是Eclipse Collections(以前称为GS Collections),则可以powerSet()在所有 SetIterables 上使用该方法。

MutableSet<Integer> set = UnifiedSet.newSetWith(1, 2, 3);
System.out.println("powerSet = " + set.powerSet());
// prints: powerSet = [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

注意:我是 Eclipse Collections 的提交者。

于 2013-08-28T21:16:10.007 回答
4

这是一个简单的迭代 O(2^n) 解决方案:

public static Set<Set<Integer>> powerSet(List<Integer> intList){

    Set<Set<Integer>> result = new HashSet();
    result.add(new HashSet());

    for (Integer i : intList){

        Set<Set<Integer>> temp = new HashSet();

        for(Set<Integer> intSet : result){

            intSet = new HashSet(intSet);
            intSet.add(i);                
            temp.add(intSet);
        }
        result.addAll(temp);
    }
    return result;
}
于 2014-10-27T17:14:14.337 回答
4

我一直在寻找一个不像这里发布的那么大的解决方案。这针对 Java 7,因此对于版本 5 和 6 将需要少量粘贴。

Set<Set<Object>> powerSetofNodes(Set<Object> orig) {
    Set<Set<Object>> powerSet = new HashSet<>(),
        runSet = new HashSet<>(),
        thisSet = new HashSet<>();

    while (powerSet.size() < (Math.pow(2, orig.size())-1)) {
        if (powerSet.isEmpty()) {
            for (Object o : orig) {
                Set<Object> s = new TreeSet<>();
                s.add(o);
                runSet.add(s);
                powerSet.add(s);
            }
            continue;
        }
        for (Object o : orig) {
            for (Set<Object> s : runSet) {
                Set<Object> s2 = new TreeSet<>();
                s2.addAll(s);
                s2.add(o);
                powerSet.add(s2);
                thisSet.add(s2);
            }
        }
        runSet.clear();
        runSet.addAll(thisSet);
        thisSet.clear();
    }
    powerSet.add(new TreeSet());
    return powerSet;

这是一些要测试的示例代码:

Set<Object> hs = new HashSet<>();
hs.add(1);
hs.add(2);
hs.add(3);
hs.add(4);
for(Set<Object> s : powerSetofNodes(hs)) {
    System.out.println(Arrays.toString(s.toArray()));
}
于 2011-04-12T15:10:45.397 回答
3

当集合的大小很大时,上述一些解决方案会受到影响,因为它们会创建大量要收集的对象垃圾并需要复制数据。我们怎样才能避免呢?我们可以利用我们知道结果集大小(2^n)的事实,预先分配一个那么大的数组,然后附加到它的末尾,从不复制。

加速比随着 n 快速增长。我将它与上述 João Silva 的解决方案进行了比较。在我的机器上(所有测量值都是近似值),n=13 快 5 倍,n=14 是 7x,n=15 是 12x,n=16 是 25x,n=17 是 75x,n=18 是 140x。因此,垃圾创建/收集和复制在其他看似类似的大 O 解决方案中占据主导地位。

与让它动态增长相比,在开始时预分配数组似乎是一种胜利。当 n=18 时,动态增长需要大约两倍的时间。

public static <T> List<List<T>> powerSet(List<T> originalSet) {
    // result size will be 2^n, where n=size(originalset)
    // good to initialize the array size to avoid dynamic growing
    int resultSize = (int) Math.pow(2, originalSet.size());
    // resultPowerSet is what we will return
    List<List<T>> resultPowerSet = new ArrayList<List<T>>(resultSize);

    // Initialize result with the empty set, which powersets contain by definition
    resultPowerSet.add(new ArrayList<T>(0)); 

    // for every item in the original list
    for (T itemFromOriginalSet : originalSet) {

        // iterate through the existing powerset result
        // loop through subset and append to the resultPowerset as we go
        // must remember size at the beginning, before we append new elements
        int startingResultSize = resultPowerSet.size();
        for (int i=0; i<startingResultSize; i++) {
            // start with an existing element of the powerset
            List<T> oldSubset = resultPowerSet.get(i);

            // create a new element by adding a new item from the original list
            List<T> newSubset = new ArrayList<T>(oldSubset);
            newSubset.add(itemFromOriginalSet);

            // add this element to the result powerset (past startingResultSize)
            resultPowerSet.add(newSubset);
        }
    }
    return resultPowerSet;
}
于 2013-01-24T21:59:59.170 回答
3

以下解决方案是从我的《编码面试:问题、分析和解决方案》一书中借用的:

选择数组中的一些整数组成一个组合。使用了一组位,其中每个位代表数组中的一个整数。如果选择第i 个字符进行组合,则第i位为 1;否则为0。例如,数组[1,2,3]的组合使用三位。如果选择前两个整数1和2组成一个组合[1, 2],则对应的位为{1, 1, 0}。类似地,对应于另一个组合[1, 3]的位是{1, 0, 1}。如果我们能得到所有可能的n位组合,我们就能得到一个长度为n的数组的所有组合。

一个数字由一组位组成。n位的所有可能组合对应于从 1 到 2^ n -1 的数字。因此,1 到 2^ n -1 范围内的每个数字对应于长度为n的数组的组合。例如数字 6 由位 {1,1,0} 组成,因此在数组 [1,2,3] 中选择第一个和第二个字符来生成组合 [1,2]。类似地,具有位 {1, 0, 1} 的数字 5 对应于组合 [1, 3]。

实现此解决方案的 Java 代码如下所示:

public static ArrayList<ArrayList<Integer>> powerSet(int[] numbers) {
    ArrayList<ArrayList<Integer>> combinations = new ArrayList<ArrayList<Integer>>(); 
    BitSet bits = new BitSet(numbers.length);
    do{
        combinations.add(getCombination(numbers, bits));
    }while(increment(bits, numbers.length));

    return combinations;
}

private static boolean increment(BitSet bits, int length) {
    int index = length - 1;

    while(index >= 0 && bits.get(index)) {
        bits.clear(index);
        --index;
    }

    if(index < 0)
        return false;

    bits.set(index);
    return true;
}

private static ArrayList<Integer> getCombination(int[] numbers, BitSet bits){
    ArrayList<Integer> combination = new ArrayList<Integer>();
    for(int i = 0; i < numbers.length; ++i) {
        if(bits.get(i))
            combination.add(numbers[i]);
    }

    return combination;
}

方法增量增加一组位中表示的数字。该算法从最右边的位清除 1 位,直到找到 0 位。然后它将最右边的 0 位设置为 1。例如,为了增加数字 5 的位 {1,0,1},它从右侧清除 1 位并将最右边的 0 位设置为 1。这些位变为{1, 1, 0} 表示数字 6,它是 5 加 1 的结果。

于 2012-12-28T15:05:39.303 回答
3
import java.util.Set;
import com.google.common.collect.*;

Set<Set<Integer>> sets = Sets.powerSet(ImmutableSet.of(1, 2, 3));
于 2016-03-11T17:39:04.637 回答
1

没有递归的一种方法如下:使用二进制掩码并进行所有可能的组合。

public HashSet<HashSet> createPowerSet(Object[] array)
{
    HashSet<HashSet> powerSet=new HashSet();
    boolean[] mask= new boolean[array.length];

    for(int i=0;i<Math.pow(2, array.length);i++)
    {
        HashSet set=new HashSet();
        for(int j=0;j<mask.length;j++)
        {
            if(mask[i])
                set.add(array[j]);
        }
        powerSet.add(set);      

        increaseMask(mask);
    }

    return powerSet;
}

public void increaseMask(boolean[] mask)
{
    boolean carry=false;

    if(mask[0])
        {
            mask[0]=false;
            carry=true;
        }
    else
        mask[0]=true;

    for(int i=1;i<mask.length;i++)
    {
        if(mask[i]==true && carry==true)
        mask[i]=false;
        else if (mask[i]==false && carry==true)
        {
            mask[i]=true;
            carry=false;
        }
        else 
            break;

    }

}
于 2012-01-19T00:38:05.583 回答
1

如果 S 是具有 N 个元素的有限集,则 S 的幂集包含 2^N 个元素。简单枚举幂集元素的时间是 2^N,因此O(2^N)(急切地)构建幂集的时间复杂度的下限也是如此。

简而言之,任何涉及创建幂集的计算都不会针对较大的 N 值进行扩展。没有聪明的算法可以帮助您……除了避免创建幂集的需要!

于 2009-11-04T00:00:48.513 回答
1

This is my recursive solution which can get the power set of any set using Java Generics. Its main idea is to combine the head of the input array with all the possible solutions of the rest of the array as follows.

import java.util.LinkedHashSet;
import java.util.Set;

public class SetUtil {
    private static<T>  Set<Set<T>> combine(T head, Set<Set<T>> set) {
        Set<Set<T>> all = new LinkedHashSet<>();

        for (Set<T> currentSet : set) {
            Set<T> outputSet = new LinkedHashSet<>();

            outputSet.add(head);
            outputSet.addAll(currentSet);

            all.add(outputSet);
        }

        all.addAll(set);        

        return all;
    }

    //Assuming that T[] is an array with no repeated elements ...
    public static<T> Set<Set<T>> powerSet(T[] input) {
        if (input.length == 0) {
            Set <Set<T>>emptySet = new LinkedHashSet<>();

            emptySet.add(new LinkedHashSet<T>());

            return emptySet;
        }

        T head = input[0];
        T[] newInputSet = (T[]) new Object[input.length - 1];

        for (int i = 1; i < input.length; ++i) {
            newInputSet[i - 1] = input[i];
        }

        Set<Set<T>> all = combine(head, powerSet(newInputSet));

        return all;
    }

    public static void main(String[] args) {            
        Set<Set<Integer>> set = SetUtil.powerSet(new Integer[] {1, 2, 3, 4, 5, 6});

        System.out.println(set);
    }
}

This will output:

[[1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5], [1, 2, 3, 4, 6], [1, 2, 3, 4], [1, 2, 3, 5, 6], [1, 2, 3, 5], [1, 2, 3, 6], [1, 2, 3], [1, 2, 4, 5, 6], [1, 2, 4, 5], [1, 2, 4, 6], [1, 2, 4], [1, 2, 5, 6], [1, 2, 5], [1, 2, 6], [1, 2], [1, 3, 4, 5, 6], [1, 3, 4, 5], [1, 3, 4, 6], [1, 3, 4], [1, 3, 5, 6], [1, 3, 5], [1, 3, 6], [1, 3], [1, 4, 5, 6], [1, 4, 5], [1, 4, 6], [1, 4], [1, 5, 6], [1, 5], [1, 6], [1], [2, 3, 4, 5, 6], [2, 3, 4, 5], [2, 3, 4, 6], [2, 3, 4], [2, 3, 5, 6], [2, 3, 5], [2, 3, 6], [2, 3], [2, 4, 5, 6], [2, 4, 5], [2, 4, 6], [2, 4], [2, 5, 6], [2, 5], [2, 6], [2], [3, 4, 5, 6], [3, 4, 5], [3, 4, 6], [3, 4], [3, 5, 6], [3, 5], [3, 6], [3], [4, 5, 6], [4, 5], [4, 6], [4], [5, 6], [5], [6], []]
于 2014-12-31T01:39:18.843 回答
1

算法:

输入:Set[], set_size 1. 获取幂集的大小 powet_set_size = pow(2, set_size) 2 循环计数器从 0 到 pow_set_size (a) 循环 i = 0 到 set_size (i) 如果计数器中的第 i 位是为该子集打印集合中的第 i 个元素 (b) 为子集打印分隔符,即换行符

#include <stdio.h>
#include <math.h>
 
void printPowerSet(char *set, int set_size)
{
    /*set_size of power set of a set with set_size
      n is (2**n -1)*/
    unsigned int pow_set_size = pow(2, set_size);
    int counter, j;
 
    /*Run from counter 000..0 to 111..1*/
    for(counter = 0; counter < pow_set_size; counter++)
    {
      for(j = 0; j < set_size; j++)
       {
          /* Check if jth bit in the counter is set
             If set then pront jth element from set */
          if(counter & (1<<j))
            printf("%c", set[j]);
       }
       printf("\n");
    }
}
 
/*Driver program to test printPowerSet*/
int main()
{
    char set[] = {'a','b','c'};
    printPowerSet(set, 3);
 
    getchar();
    return 0;
}

于 2014-09-22T03:42:29.840 回答
1

这是我使用 lambdas 的方法。

public static <T> Set<Set<T>> powerSet(T[] set) {
      return IntStream
            .range(0, (int) Math.pow(2, set.length))
            .parallel() //performance improvement
            .mapToObj(e -> IntStream.range(0, set.length).filter(i -> (e & (0b1 << i)) != 0).mapToObj(i -> set[i]).collect(Collectors.toSet()))
            .map(Function.identity())
            .collect(Collectors.toSet());
        }

或并行(参见 parallel() 注释):

输入集大小:18

逻辑处理器:8 à 3.4GHz

性能提升:30%

于 2016-08-02T04:59:17.117 回答
1

另一个示例实现:

 public static void main(String args[])
    {
        int[] arr = new int[]{1,2,3,4};
        // Assuming that number of sets are in integer range
        int totalSets = (int)Math.pow(2,arr.length);
        for(int i=0;i<totalSets;i++)
        {
            String binaryRep = Integer.toBinaryString(i);      
            for(int j=0;j<binaryRep.length();j++)
            {
                int index=binaryRep.length()-1-j;
                if(binaryRep.charAt(index)=='1')
                System.out.print(arr[j] +" ");       
            }
            System.out.println();
        }
    }
于 2016-02-01T08:24:18.583 回答
1

t 的子集是可以通过删除 t 的零个或多个元素而得到的任何集合。withoutFirst 子集添加 t 中缺少第一个元素的子集,for 循环将处理添加带有第一个元素的子集。例如,如果 t 包含元素 ["1", "2", "3"],missingFirst 将添加 [[""], ["2"], ["3"], ["2","3 "]] 并且 for 循环会将 "1" 粘贴在这些元素的前面并将其添加到 newSet 中。所以我们最终会得到 [[""], ["1"], ["2"], ["3"], ["1", "2"], ["1", "3"] , ["2","3"], ["1", "2", "3"]]。

public static Set<Set<String>> allSubsets(Set<String> t) {
        Set<Set<String>> powerSet = new TreeSet<>();
        if(t.isEmpty()) {
            powerSet.add(new TreeSet<>());
            return powerSet;
        }
        String first = t.get(0);
        Set<Set<String>> withoutFirst = allSubsets(t.subSet(1, t.size()));
        for (List<String> 1st : withoutFirst) {
            Set<String> newSet = new TreeSet<>();
            newSet.add(first);
            newSet.addAll(lst);
            powerSet.add(newSet);
        }
        powerSet.addAll(withoutFirst);
        return powerSet;
    }
于 2017-11-27T03:30:18.847 回答
0
// input: S
// output: P
// S = [1,2]
// P = [], [1], [2], [1,2]

public static void main(String[] args) {
    String input = args[0];
    String[] S = input.split(",");
    String[] P = getPowerSet(S);
    if (P.length == Math.pow(2, S.length)) {
        for (String s : P) {
            System.out.print("[" + s + "],");
        }
    } else {
        System.out.println("Results are incorrect");
    }
}

private static String[] getPowerSet(String[] s) {
    if (s.length == 1) {
        return new String[] { "", s[0] };
    } else {
        String[] subP1 = getPowerSet(Arrays.copyOfRange(s, 1, s.length));
        String[] subP2 = new String[subP1.length];
        for (int i = 0; i < subP1.length; i++) {
            subP2[i] = s[0] + subP1[i];
        }
        String[] P = new String[subP1.length + subP2.length];
        System.arraycopy(subP1, 0, P, 0, subP1.length);
        System.arraycopy(subP2, 0, P, subP1.length, subP2.length);
        return P;
    }

}
于 2015-07-30T23:03:41.793 回答
0
public class PowerSet {
    public static List<HashSet<Integer>> powerset(int[] a) {
        LinkedList<HashSet<Integer>> sets = new LinkedList<HashSet<Integer>>();
        int n = a.length;
        for (int i = 0; i < 1 << n; i++) {
            HashSet<Integer> set = new HashSet<Integer>();
            for (int j = 0; j < n; j++) {
                if ((1 << j & i) > 0)
                    set.add(a[j]);
            }
            sets.add(set);
        }
        return sets;
    }

    public static void main(String[] args) {
        List<HashSet<Integer>> sets = PowerSet.powerset(new int[]{ 1, 2, 3 });
        for (HashSet<Integer> set : sets) {
            for (int i : set)
                System.out.print(i);
            System.out.println();
        } 
    }
}
于 2016-08-12T14:34:46.703 回答
0

该函数通过递归解决了这个问题,但将名为 powerset 的变量设为全局变量:

static ArrayList<ArrayList<Integer>> powerSet = new ArrayList<>();

public static void getPowerSet(Queue<Integer> a) {
    int n = a.poll();
    if (!a.isEmpty()) {
        getPowerSet(a);
    }
    int s = powerSet.size();
    for (int i = 0; i < s; i++) {
        ArrayList<Integer> ne = new ArrayList<>();
        for (int j = 0; j < powerSet.get(i).size(); j++) {
            ne.add(powerSet.get(i).get(j));
        }
        ne.add(n);
        powerSet.add(ne);
    }
    ArrayList<Integer> p = new ArrayList<>();
    p.add(n);
    powerSet.add(p);
}
于 2021-12-23T20:49:19.953 回答
0

我最近不得不使用这样的东西,但首先需要最小的子列表(有 1 个元素,然后是 2 个元素,...)。我不想包括空的或整个列表。另外,我不需要返回所有子列表的列表,我只需要对每个子列表做一些事情。

想要在没有递归的情况下做到这一点,并提出了以下内容(将“正在做的事情”抽象为功能接口):

@FunctionalInterface interface ListHandler<T> {
    void handle(List<T> list);
}


public static <T> void forAllSubLists(final List<T> list, ListHandler handler) {
    int     ll = list.size();   // Length of original list
    int     ci[] = new int[ll]; // Array for list indices
    List<T> sub = new ArrayList<>(ll);  // The sublist
    List<T> uml = Collections.unmodifiableList(sub);    // For passing to handler

    for (int gl = 1, gm; gl <= ll; gl++) {  // Subgroup length 1 .. n-1
        gm = 0; ci[0] = -1; sub.add(null);  // Some inits, and ensure sublist is at least gl items long

        do {
                ci[gm]++;                       // Get the next item for this member

                if (ci[gm] > ll - gl + gm) {    // Exhausted all possibilities for this position
                        gm--; continue;         // Continue with the next value for the previous member
                }

                sub.set(gm, list.get(ci[gm]));  // Set the corresponding member in the sublist

                if (gm == gl - 1) {             // Ok, a sublist with length gl
                        handler.handle(uml);    // Handle it
                } else {
                        ci[gm + 1] = ci[gm];    // Starting value for next member is this 
                        gm++;                   // Continue with the next member
                }
        } while (gm >= 0);  // Finished cycling through all possibilities
    }   // Next subgroup length
}

通过这种方式,也很容易将其限制为特定长度的子列表。

于 2015-09-14T16:33:41.760 回答
0

另一个解决方案 - 使用 java8+ 流 api 它是惰性且有序的,因此当它与“limit()”一起使用时它会返回正确的子集。

 public long bitRangeMin(int size, int bitCount){
    BitSet bs = new BitSet(size);
    bs.set(0, bitCount);
    return bs.toLongArray()[0];
}

public long bitRangeMax(int size, int bitCount){
    BitSet bs = BitSet.valueOf(new long[]{0});
    bs.set(size - bitCount, size);
    return bs.toLongArray()[0];
}

public <T> Stream<List<T>> powerSet(Collection<T> data)
{
    List<T> list = new LinkedHashSet<>(data).stream().collect(Collectors.toList());
    Stream<BitSet> head = LongStream.of(0).mapToObj( i -> BitSet.valueOf(new long[]{i}));
    Stream<BitSet> tail = IntStream.rangeClosed(1, list.size())
            .boxed()
            .flatMap( v1 -> LongStream.rangeClosed( bitRangeMin(list.size(), v1), bitRangeMax(list.size(), v1))
                    .mapToObj(v2 -> BitSet.valueOf(new long[]{v2}))
                    .filter( bs -> bs.cardinality() == v1));

    return Stream.concat(head, tail)
            .map( bs -> bs
                    .stream()
                    .mapToObj(list::get)
                    .collect(Collectors.toList()));
}

客户端代码是

@Test
public void testPowerSetOfGivenCollection(){
    List<Character> data = new LinkedList<>();
    for(char i = 'a'; i < 'a'+5; i++ ){
        data.add(i);
    }
    powerSet(data)
            .limit(9)
            .forEach(System.out::print);

}

/* 打印:[][a][b][c][d][e][a, b][a, c][b, c] */

于 2017-01-19T13:52:23.673 回答
0

我们可以使用或不使用递归来编写幂集。这是没有递归的尝试:

public List<List<Integer>> getPowerSet(List<Integer> set) {
    List<List<Integer>> powerSet = new ArrayList<List<Integer>>();
    int max = 1 << set.size();
    for(int i=0; i < max; i++) {
        List<Integer> subSet = getSubSet(i, set);
        powerSet.add(subSet);
    }
    return powerSet;
}

private List<Integer> getSubSet(int p, List<Integer> set) {
    List<Integer> subSet = new ArrayList<Integer>();
    int position = 0;
    for(int i=p; i > 0; i >>= 1) {
        if((i & 1) == 1) {
            subSet.add(set.get(position));
        }
        position++;
    }
    return subSet;
}
于 2017-06-02T04:43:53.713 回答
0
package problems;

import java.util.ArrayList;
import java.util.List;

public class SubsetFinderRecursive {
    public static void main(String[] args) {
        //input
        int[] input = new int[3];
        for(int i=0; i<input.length; i++) {
            input[i] = i+1;
        }
        // root node of the tree
        Node root = new Node();

        // insert values into tree
        for(int i=0; i<input.length; i++) {
            insertIntoTree(root, input[i]);
        }

        // print leaf nodes for subsets
        printLeafNodes(root);
    }

    static void printLeafNodes(Node root) {

        if(root == null) {
            return;
        }

        // Its a leaf node
        if(root.left == null && root.right == null) {
            System.out.println(root.values);
            return;
        }

        // if we are not at a leaf node, then explore left and right

        if(root.left !=null) {
            printLeafNodes(root.left);
        }

        if(root.right != null) {
            printLeafNodes(root.right);
        }
    }

    static void insertIntoTree(Node root, int value) {

        // Error handling
        if(root == null) {
            return;
        }

        // if there is a sub tree then go down
        if(root.left !=null && root.right != null) {
            insertIntoTree(root.left, value);
            insertIntoTree(root.right, value);
        }

        // if we are at the leaf node, then we have 2 choices
        // Either exclude or include
        if(root.left == null && root.right == null) {
            // exclude
            root.left = new Node();
            root.left.values.addAll(root.values);
            // include
            root.right = new Node();
            root.right.values.addAll(root.values);
            root.right.values.add(value);
            return;
        }
    }

}

class Node {
    Node left;
    Node right;
    List<Integer> values = new ArrayList<Integer>();
}
于 2020-04-23T20:27:20.017 回答
0

这里是生成一个幂集。这个想法是 first =S[0]和较小的集合是S[1,...n]

计算 smallSet 的所有子集并将它们放入所有子集中。

对于所有子集中的每个子集,克隆它并首先添加到子集中。

ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> set, int index){
    ArrayList<ArrayList<Integer>> allsubsets;
    if(set.size() == index){
        allsubsets = new ArrayList<ArrayList<Integer>>();
        allsubsets.add(new ArrayList<Integer>()); // the empty set 
    }else{
        allsubsets = getSubsets(set, index+1);
        int item = set.get(index);

        ArrayList<ArrayList<Integer>> moresubsets = new ArrayList<ArrayList<Integer>>();

        for(ArrayList<Integer> subset: allsubsets){
            ArrayList<Integer> newsubset = new ArrayList<Integer>();

            newsubset.addAll(subset);
            newsubset.add(item);
            moresubsets.add(newsubset);

        }

        moresubsets.addAll(moresubsets);

    }

    return allsubsets;
}
于 2018-01-16T18:52:59.800 回答