爪哇 - 生成功率设定一个给定的列表 [英] Java - Generate the power-set of a given List

问题描述

我想要生成的所有2 ^ N的集合 - 长度为N的给定列表的1种可能的组合的集合可以为一个组合元件的数量映射到的含有特定的组合的组合的有序列表长度。例如，对于在列表：

I'm trying to generate a collection of all 2^N - 1 possible combinations of a given List of length N. The collection will map the number of elements in a combination to an ordered list of combinations containing combinations of the specific length. For instance, for the List:

[A, B, C, D]

我要生成地图：

I want to generate the map:

{
    1 -> [{A}, {B}, {C}, {D}]
    2 -> [{A, B}, {A, C}, {A, D}, {B, C}, {B, D}, {C, D}]
    3 -> [{A, B, C}, {A, B, D}, {A, C, D}, {B, C, D}]
    4 -> [{A, B, C, D}]
}

生成的数据库应保持原有的秩序（其中 [] 重presents一系列有序的（列表）和 {} 重presents一个未排序组（设置）），并运行作为越快越好。

The generated database should maintain the original order (where [] represents an ordered series (List), and {} represents an un-ordered group (Set)), and run as fast as possible.

我整天疲于应付一些递归code（我知道的实施应该是递归），但无法得到它的底部。

I was struggling with some recursive code all day (I know the implementation should be recursive) but couldn't get to the bottom of it.

时有一个参考，我可以使用/现成实现这样的算法？

Is there a reference I can use / a ready implementation of such algorithm?

更新：

由于previous答案，我想出了下面的实现：

Thanks to previous answers, I came up with the following implementation:

public class OrderedPowerSet<E> {
    private static final int ELEMENT_LIMIT = 12;
    private List<E> inputList;
    public int N;
    private Map<Integer, List<LinkedHashSet<E>>> map = 
            new HashMap<Integer, List<LinkedHashSet<E>>>();

    public OrderedPowerSet(List<E> list) {
        inputList = list;
        N = list.size();
        if (N > ELEMENT_LIMIT) {
            throw new RuntimeException(
                    "List with more then " + ELEMENT_LIMIT + " elements is too long...");
        }
    }

    public List<LinkedHashSet<E>> getPermutationsList(int elementCount) {
        if (elementCount < 1 || elementCount > N) {
            throw new IndexOutOfBoundsException(
                    "Can only generate permutations for a count between 1 to " + N);
        }
        if (map.containsKey(elementCount)) {
            return map.get(elementCount);
        }

        ArrayList<LinkedHashSet<E>> list = new ArrayList<LinkedHashSet<E>>();

        if (elementCount == N) {
            list.add(new LinkedHashSet<E>(inputList));
        } else if (elementCount == 1) {
            for (int i = 0 ; i < N ; i++) {
                LinkedHashSet<E> set = new LinkedHashSet<E>();
                set.add(inputList.get(i));
                list.add(set);
            }
        } else {
            list = new ArrayList<LinkedHashSet<E>>();
            for (int i = 0 ; i <= N - elementCount ; i++) {
                @SuppressWarnings("unchecked")
                ArrayList<E> subList = (ArrayList<E>)((ArrayList<E>)inputList).clone();
                for (int j = i ; j >= 0 ; j--) {
                    subList.remove(j);
                }
                OrderedPowerSet<E> subPowerSet = 
                        new OrderedPowerSet<E>(subList);

                List<LinkedHashSet<E>> pList = 
                        subPowerSet.getPermutationsList(elementCount-1);
                for (LinkedHashSet<E> s : pList) {
                    LinkedHashSet<E> set = new LinkedHashSet<E>();
                    set.add(inputList.get(i));
                    set.addAll(s);
                    list.add(set);
                }               
            }
        }

        map.put(elementCount, list);

        return map.get(elementCount);
    }
}

我会很高兴得到一些反馈的方法来改善这一点。

I would be happy to get some feedback for ways to improve this.

更新2：

我固定在code的几个问题，并对其进行了测试。

I fixed a few issues in the code and tested it.

推荐答案

你要找的是什么本质上是的电源设置的（减去可能是空集）。番石榴实际上具有这样的方法：<一href="http://docs.guava-libraries.google$c$c.com/git/javadoc/com/google/common/collect/Sets.html#powerSet%28java.util.Set%29"><$c$c>Sets.powerSet().您可以查看<一href="https://$c$c.google.com/r/baggiogamp-guava/source/browse/guava/src/com/google/common/collect/Sets.java?r=5560bc10e7472f94e8f50831eb0907a35628e725&spec=svn6923b5fac0feb7005429d0b24be93b91685f9637">source的设置类怎么看，如果你想自己写它的方法来实现;你可能需要修改它返回一个列表，而不是设置，因为要preserve秩序，虽然这种变化应该不会太激烈。一旦你的发电机组，它应该是微不足道的迭代它构建你想要的地图。

What you're looking for is essentially the power set (minus perhaps the empty set). Guava actually has a method for this: Sets.powerSet(). You can view the source of the Sets class to see how the method is implemented if you want to write it yourself; you might need to modify it to return a List instead of a Set since you want to preserve order, although this change should not be too drastic. Once you have the power set, it should be trivial to iterate over it and construct the map you want.

这篇关于爪哇 - 生成功率设定一个给定的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！