java - N个有序元素的组合

Question

我有一组 K 个元素，我需要创建一个 N 个有序元素的组合。
例如，如果 K=1 并且我有 {X1, emptyset} 和 n = 2 那么我有一个有序的对，我需要这样做:

示例 1:

 ({},{})  
 ({X1},{}), ({},{X1})  
 ({X1},{X1})  

请注意，我需要按以下顺序获取元素:首先是节点为 0 的元素作为两对之和，其次是节点为 1 的元素，ecc

我的想法是制作初始集的部分集，一次添加一个元素，但我失去了理智。有什么建议么？我需要在 Java 中执行此操作。

编辑 1:换句话说，我需要创建一个 Hasse 图: http://en.wikipedia.org/wiki/Hasse_diagram

其中每个节点都是部分集合的一个元素，偏序函数是对所有子集的包含，如下所示:

例子2:

ni = (S1i,S2i) C nj = (S1j,S2j) 仅当 S1i C S1j AND S21 C s2j

编辑 2:@RONALD:

如果对于集合 S = {1, 2} 和​​ n =2，我有 K=2，我需要这个输出:

 level0: ({}, {})  
 level1: ({1}, {}); ({2}, {}); ({}, {1}); ({}, {2})  
 level2: ({1,2}, {}); ({1}, {1}); ({1}, {2}); ({2}, {1}); ({2}, {2}); ({}, {1,2});   
 [..]

级别之间的顺序很重要，例如:

如果在level1我有

 ({1}, {}); ({2}, {}); ({}, {1}); ({}, {2})  

或

 ({}, {2}); ({}, {1}); ({2}, {}); ({1}, {}); 

是一样的。但重要的是，在第 2 级，我拥有第 2 级的所有超集，并且在示例 2

中解释了超集

编辑 3:
如果我的集合是 S= {x,y,z} 并且每个节点只有一个集合，则结果(从底部开始)是这样的: http://upload.wikimedia.org/wikipedia/commons/e/ea/Hasse_diagram_of_powerset_of_3.svg

如果我有 S={1,2} 并且每次点头设置两个，结果是这样的(感谢 Ronald 提供的图表):
http://www.independit.de/Downloads/hasse.pdf

编辑4:

因为这是一个超指数问题，所以我的想法是:我一次计算一个级别(在有序模式下!)并根据一些规则我修剪一个节点及其所有超集。另一个停止规则可能是在某个级别停止。对于此规则，必须以有序的方式直接计算组合，而不是计算所有组合然后重新排序。

编辑5:

Marco13 的代码工作正常，我做了一些修改:

• 使用函数 PowerSet，因为它有助于仅组合集合 S 的 K 个元素(为此我只需要获取 powerset 的第一个 tot 元素)。

现在算法完成了所有工作，但我需要加快速度。有什么办法可以并行计算吗？这样一种使用Map Reduce(Apache hadoop实现)范式的方式？

package utilis;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class HasseDiagramTest4
{
    public static void main(String[] args)
    {
        int numberOfSetsPerNode = 3;

        List<Integer> set = Arrays.asList(1, 2, 3, 4, 5,6);
        List<Set<Integer>> powerSet = computePowerSet(set);
        powerSet = KPowerSet(powerSet, 3);

        List<List<Set<Integer>>> prunedNodes = 
            new ArrayList<List<Set<Integer>>>();
        List<Set<Integer>> prunedNode = new ArrayList<Set<Integer>>();

        HashSet<Integer> s = new HashSet<Integer>();
        HashSet<Integer> s_vuoto = new HashSet<Integer>();
        s.add(1);
        s.add(2);
        prunedNode.add(s);
        prunedNode.add(s_vuoto);
        prunedNode.add(s);

       prunedNodes.add(prunedNode);

        compute(ordina(powerSet), numberOfSetsPerNode, prunedNodes);
    }

    private static <T> HashMap<Integer, List<Set<T>>> ordina(List<Set<T>> powerSet) {

        HashMap<Integer, List<Set<T>>> hs = new HashMap<Integer, List<Set<T>>>();

        for(Set<T> l: powerSet)
        {
            List<Set<T>> lput = new  ArrayList<Set<T>>();
            if(hs.containsKey(l.size()))
            {
                lput = hs.get(l.size());
                lput.add(l);
                hs.put(l.size(), lput);
            }
            else
            {
                lput.add(l);
                hs.put(l.size(), lput); 
            }

        }

        return hs;
    }

    private static <T> List<Set<T>> KPowerSet(List<Set<T>> powerSet, int k)
    {
        List<Set<T>> result = new ArrayList<Set<T>>();

        for(Set<T>s:powerSet)
        {
            if(s.size() <= k)
            {
                result.add(s);
            }
        }
        return result;
    }

    private static <T> List<Set<T>> computePowerSet(List<T> set)
    {
        List<Set<T>> result = new ArrayList<Set<T>>();
        int numElements = 1 << set.size();
        for (int j=0; j<numElements; j++)
        {
            Set<T> element = new HashSet<T>();
            for (int i = 0; i < set.size(); i++)
            {
                long b = 1 << i;
                if ((j & b) != 0)
                {
                    element.add(set.get(i));
                }
            }
            result.add(element);
        }
        return result;
    }

    private static List<Integer> createList(int numberOfElements)
    {
        List<Integer> list = new ArrayList<Integer>();
        for (int i=0; i<numberOfElements; i++)
        {
            list.add(i+1);
        }
        return list;
    }

    private static <T> void compute(
            HashMap<Integer, List<Set<T>>> powerSet, int numberOfSetsPerNode,
        List<List<Set<T>>> prunedNodes)
    {
        Set<List<Set<T>>> level0 = createLevel0(numberOfSetsPerNode);
        System.out.println("Level 0:");
        print(level0);

        Set<List<Set<T>>> currentLevel = level0;
        int level = 0;
        while (true)
        {
            Set<List<Set<T>>> nextLevel = 
                createNextLevel(currentLevel, powerSet, prunedNodes);
            if (nextLevel.size() == 0)
            {
                break;
            }

            System.out.println("Next level: "+nextLevel.size()+" nodes");
            print(nextLevel);

            currentLevel = nextLevel;
            level++;
        }
    }

    private static <T> Set<List<Set<T>>> createLevel0(int numberOfSetsPerNode)
    {
        Set<List<Set<T>>> level0 = 
            new LinkedHashSet<List<Set<T>>>();
        List<Set<T>> level0element = new ArrayList<Set<T>>();
        for (int i=0; i<numberOfSetsPerNode; i++)
        {
            level0element.add(new LinkedHashSet<T>());
        }
        level0.add(level0element);
        return level0;
    }

    private static <T> List<Set<T>> getNext(Set<T> current, HashMap<Integer, List<Set<T>>> powerSet)
    {
        ArrayList<Set<T>> ritorno = new ArrayList<Set<T>>(); 
        int level = current.size();
        List<Set<T>> listnext = powerSet.get(level+1);

        if(listnext != null)
        {
            for(Set<T> next: listnext)
            {
                if(next.containsAll(current))
                {
                    ritorno.add(next);
                }
            }
        }

        return ritorno;
    }


    private static <T> Set<List<Set<T>>> createNextLevel(
        Set<List<Set<T>>> currentLevel, HashMap<Integer, List<Set<T>>> powerSet,
        List<List<Set<T>>> prunedNodes)
    {
        Set<List<Set<T>>> nextLevel = new LinkedHashSet<List<Set<T>>>();

        //Per ogni nodo del livello corrente
        for (List<Set<T>> currentLevelElement : currentLevel)
        {
            //Per ogni insieme del nodo preso in considerazione
            for (int i=0; i<currentLevelElement.size(); i++)
            {
                List<Set<T>> listOfnext = getNext (currentLevelElement.get(i), powerSet);


                for (Set<T> element : listOfnext)
                {
                    List<Set<T>> nextLevelElement = copy(currentLevelElement);
                    Set<T> next = element;
                    nextLevelElement.remove(i);
                    nextLevelElement.add(i, next);

                    boolean pruned = false;
                    for (List<Set<T>> prunedNode : prunedNodes)
                    {
                        if (isSuccessor(prunedNode, nextLevelElement))
                        {
                            pruned = true;
                        }
                    }
                    if (!pruned)
                    {
                        nextLevel.add(nextLevelElement);
                    }
                    else
                    {
                        System.out.println("Pruned "+nextLevelElement+ " due to "+prunedNodes);
                    }
                }
            }
        }
        return nextLevel;
    }

    private static <T> boolean isSuccessor(
        List<Set<T>> list, List<Set<T>> successor)
    {
        for (int i=0; i<list.size(); i++)
        {
            Set<T> set = list.get(i);
            Set<T> successorSet = successor.get(i);
            //System.out.println("Successor:" + successorSet + "pruned:" + set);
            if (!successorSet.containsAll(set))
            {
                return false;
            }
        }
        return true;
    }

    private static <T> List<Set<T>> copy(List<Set<T>> list)
    {
        List<Set<T>> result = new ArrayList<Set<T>>();
        for (Set<T> element : list)
        {
            result.add(new LinkedHashSet<T>(element));
        }
        return result;
    }

    private static <T> void print(
        Iterable<? extends Collection<? extends Collection<T>>> sequence)
    {
        for (Collection<? extends Collection<T>> collections : sequence)
        {
            System.out.println("    "+collections);
        }
    }


}

Answer 1

经过 4 次编辑和大量讨论后，这个应用程序的目标慢慢变得更加清晰。的确，人们不得不考虑一种适当的形式化，但它最终似乎并不那么困难。

与我的第一个答案 (https://stackoverflow.com/a/22092523) 相比，这个新答案从上一层迭代计算下一层(其核心 createNextLevel 只是 10 行代码)。

在 compute 方法中，“EDIT4”中要求的剪枝可以集成到 while 循环中。

编辑:评论中还有更多请求。整合他们。但这变得荒谬了。 Um den Rest kannst du dich selbst kümmern。

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class HasseDiagramTest2
{
    public static void main(String[] args)
    {
        int numberOfElements = 2;
        int numberOfSetsPerNode = 2;

        List<Integer> list = createList(numberOfElements);

        List<List<Set<Integer>>> prunedNodes = 
            new ArrayList<List<Set<Integer>>>();
        List<Set<Integer>> prunedNode = new ArrayList<Set<Integer>>();
        prunedNode.add(Collections.singleton(1));
        prunedNode.add(Collections.singleton(1));
        prunedNodes.add(prunedNode);

        compute(list, numberOfSetsPerNode, prunedNodes);
    }

    private static List<Integer> createList(int numberOfElements)
    {
        List<Integer> list = new ArrayList<Integer>();
        for (int i=0; i<numberOfElements; i++)
        {
            list.add(i+1);
        }
        return list;
    }

    private static <T> void compute(
        List<T> elements, int numberOfSetsPerNode,
        List<List<Set<T>>> prunedNodes)
    {
        Set<List<Set<T>>> level0 = createLevel0(numberOfSetsPerNode);
        System.out.println("Level 0:");
        print(level0);

        Set<List<Set<T>>> currentLevel = level0;
        int level = 0;
        while (true)
        {
            Set<List<Set<T>>> nextLevel = 
                createNextLevel(currentLevel, elements, prunedNodes);
            if (nextLevel.size() == 0)
            {
                break;
            }

            System.out.println("Next level: "+nextLevel.size()+" nodes");
            print(nextLevel);

            currentLevel = nextLevel;
            level++;
        }
    }

    private static <T> Set<List<Set<T>>> createLevel0(int numberOfSetsPerNode)
    {
        Set<List<Set<T>>> level0 = 
            new LinkedHashSet<List<Set<T>>>();
        List<Set<T>> level0element = new ArrayList<Set<T>>();
        for (int i=0; i<numberOfSetsPerNode; i++)
        {
            level0element.add(new LinkedHashSet<T>());
        }
        level0.add(level0element);
        return level0;
    }

    private static <T> Set<List<Set<T>>> createNextLevel(
        Set<List<Set<T>>> currentLevel, List<T> elements,
        List<List<Set<T>>> prunedNodes)
    {
        Set<List<Set<T>>> nextLevel = new LinkedHashSet<List<Set<T>>>();
        for (List<Set<T>> currentLevelElement : currentLevel)
        {
            for (int i=0; i<currentLevelElement.size(); i++)
            {
                for (T element : elements)
                {
                    List<Set<T>> nextLevelElement = copy(currentLevelElement);
                    Set<T> next = nextLevelElement.get(i);
                    boolean changed = next.add(element);
                    if (!changed)
                    {
                        continue;
                    }
                    boolean pruned = false;
                    for (List<Set<T>> prunedNode : prunedNodes)
                    {
                        if (isSuccessor(prunedNode, nextLevelElement))
                        {
                            pruned = true;
                        }
                    }
                    if (!pruned)
                    {
                        nextLevel.add(nextLevelElement);
                    }
                    else
                    {
//                        System.out.println(
//                            "Pruned "+nextLevelElement+
//                            " due to "+prunedNodes);
                    }
                }
            }
        }
        return nextLevel;
    }

    private static <T> boolean isSuccessor(
        List<Set<T>> list, List<Set<T>> successor)
    {
        for (int i=0; i<list.size(); i++)
        {
            Set<T> set = list.get(i);
            Set<T> successorSet = successor.get(i);
            if (!successorSet.containsAll(set))
            {
                return false;
            }
        }
        return true;
    }

    private static <T> List<Set<T>> copy(List<Set<T>> list)
    {
        List<Set<T>> result = new ArrayList<Set<T>>();
        for (Set<T> element : list)
        {
            result.add(new LinkedHashSet<T>(element));
        }
        return result;
    }

    private static <T> void print(
        Iterable<? extends Collection<? extends Collection<T>>> sequence)
    {
        for (Collection<? extends Collection<T>> collections : sequence)
        {
            System.out.println("    "+collections);
        }
    }


}