java - N个有序元素的组合-6ren

java - N个有序元素的组合

转载作者：可可西里更新时间：2023-11-01 15:06:26

我有一组 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);
        }
    }


}

最佳答案

经过 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);
        }
    }


}

关于java - N个有序元素的组合，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22071804/

文章推荐： c++ - 有效地等待线程池中的所有任务完成

文章推荐： http - HTTP/2 是无状态协议(protocol)吗？

文章推荐： c++ - std::tuple 参数中的类型顺序有什么影响吗？

文章推荐： http - (弱)ETags 和 Last-Modified

c - `#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n`在这里做什么？
我看到以下宏 here . static const char LogTable256[256] = { #define LT(n) n, n, n, n, n, n, n, n, n, n, n,
ruby - 另一个与 "diff.*\n.*\n.*\n.*\n.*\n "相同的正则表达式
这个问题不太可能帮助任何 future 的访问者；它只与一个小的地理区域、一个特定的时间点或一个非常狭窄的情况有关，这些情况并不普遍适用于互联网的全局受众。为了帮助使这个问题更广泛地适用，visit
algorithm - n+n/2+n/3+...+n/n 之和的公式
所以我得到了这个算法我需要计算它的时间复杂度这样的 for i=1 to n do k=i while (k<=n) do FLIP(A[k]) k
algorithm - N 次幂 n i-e n^n 是否是多项式？ n^2 和 n^n 之间是否存在多项式差异？
n 的 n 次方(即 n^n)是多项式吗？ T(n) = 2T(n/2) + n^n 可以用master方法求解吗？最佳答案它不仅不是多项式，而且比阶乘还差。 O(n^n) 支配 O(n!)。同样
java - 从 Unicode 字符中删除变音符号 (ń ǹ ň ñ ṅ ņ ṇ ṋ ṉ ̈ ɲ ƞ ᶇ ɳ ȵ)
我正在研究一种算法，它可以在带有变音符号的字符(tilde、circumflex、caret、umlaut、caron)及其“简单”字符之间进行映射。例如: ń ǹ ň ñ ṅ ņ ṇ
fibonacci - 如何使用运算符(或其他东西)编写 N N N .... N？
嗯..我从昨天开始学习APL。我正在观看 YouTube 视频，从基础开始学习各种符号，我正在使用 NARS2000。我想要的是打印斐波那契数列。我知道有好几种代码，但是因为我没有研究过高深的东西，
math - 求解递推关系 T(n) = √n T(√n) + n
已关闭。这个问题是 off-topic 。目前不接受答案。想要改进这个问题吗？ Update the question所以它是on-topic用于堆栈溢出。已关闭12 年前。 Improve th
python - 从 N*N*N 到 N 的双射函数
谁能帮我从 N * N * N → N 中找到一个双射数学函数，它接受三个参数 x、y 和 z 并返回数字 n？我想知道函数 f 及其反函数 f'，如果我有 n，我将能够通过应用 f'(n) 来
regex - 如何在同一等式中搜索/替换所有 "n("-> "n*("和 ")n"-> ")*n"？
场景: 用户可以在字符串格式的方程式中输入任意数量的括号对。但是，我需要检查以确保所有括号 ( 或 ) 都有一个相邻的乘数符号 *。因此 3( 应该是 3*( 和 )3 应该是 )*3。我需要将所有
java - 为什么 n+++n 有效而 n++++n 无效？
在 Java 中，表达式: n+++n 似乎评估为等同于: n++ + n 尽管 +n 是一个有效的一元运算符，其优先级高于 n + n 中的算术 + 运算符。因此编译器似乎假设运算符不能是一元运算符
c - n = 0 和 n = n - n 之间的区别
当我阅读 this 问题我记得有人曾经告诉我(很多年前)，从汇编程序的角度来看，这两个操作非常不同: n = 0; n = n - n; 这是真的吗？如果是，为什么会这样？编辑: 正如一些回复所指出
javascript - ^\n\n\n 的含义
我正在尝试在reveal.js 中加载外部markdown 文件，该文件已编写为遵守数据分隔符语法: You can write your content as a separate file and
javascript - 使用 JavaScript，如何按照这些参数/规则生成随机 11 个字符字符串？ (L,L,L,L/N,L/N,N,N,N,N,N,N)
我试图弄清楚如何使用 Javascript 生成一个随机 11 个字符串，该字符串需要特定的字母/数字序列，以及位置。 ----------------------------------------
algorithm - 使用主方法求解 T(n) = 2T(n/2) + n/log n 和 T(n) = 4T(n/2) + n/log n 之间的区别
我最近偶然发现了一个资源，其中 2T(n/2) + n/log n 类型的递归被 MM 宣布为无法解决。直到今天，当另一种资源被证明是矛盾的(在某种意义上)时，我才接受它作为引理。根据资源(下面
python - 用十进制数 64165 位的 `n ** n` 计算 `n`(n 乘以 n)需要多长时间？
关闭。此题需要details or clarity 。目前不接受答案。想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题. 已关闭 8 年前。 Improve th
algorithm - O(n) + O(n log n) 是否等于 O(n log n)？
我完成的一个代码遵循这个模式: for (i = 0; i < N; i++){ // O(N) //do some processing... } sort(array, array + N
algorithm - 是否有可能证明 f(n) + g(n) = theta(n^2) for f(n) = theta(n^2) & g(n) = O(n^2)
有没有办法证明 f(n) + g(n) = theta(n^2) 还是不可能？假设 f(n) = theta(n^2) & g(n) = O(n^2) 我尝试了以下方法:f(n) = O(n^2) &
python - 仅当另一个 n*n 的值具有特定值时才显示 n*n 矩阵的值 (Python)
所以我目前正在尝试计算我拥有的一些数据的 Pearson R 和 p 值。这是通过以下代码完成的: import numpy as np from scipy.stats import pearson
postgresql - 如何从 n.n.n.n 格式的 ltree 中选择并在每个级别按数字排序？
ltree 列的默认排序为文本。示例:我的表 id、parentid 和 wbs 中有 3 列。 ltree 列 - wbs 将 1.1.12, 1.1.1, 1.1.2 存储在不同的行中。按 wbs
python - 为什么 while(n) n = n>>1 循环不以负数 n 终止
我的目标是编写一个程序来计算在 python 中表示数字所需的位数，如果我选择 number = -1 或任何负数，程序不会终止，这是我的代码: number = -1 cnt = 0 while(n

可可西里

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

java - N个有序元素的组合