我有一组k元素，需要创建一个n个有序元素的组合。
例如，如果k=1，我有{x1，emptyset}和n=2，那么我有一个有序对，我需要这样做：
例1：
({},{})
({X1},{}), ({},{X1})
({X1},{X1})请注意，我需要按以下顺序获取元素：首先是节点为0的元素作为两对的和，其次是节点为1的元素，ecc
我的想法是把初始集合的各个部分组成一个集合，每次添加一个元素，但我已经失去理智了。有什么建议吗？我需要用java来做这个。
编辑1：换句话说，我需要创建一个哈斯图：http://en.wikipedia.org/wiki/hasse_diagram
其中，每个节点是零件集的一个元素，偏序函数是所有子集上的包含，如下所示：
例2：
ni=（s1i，s2i）c nj=（s1j，s2j）仅当s1i c s1j和s21 c s2j
编辑2:@罗纳德：
如果一个集合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});
[..]级别之间的顺序很重要，例如：
如果在一级我有
({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元素的makeall组合有帮助（我只需要获取powerset的第一个tot元素就可以了）。
现在算法可以做所有的，但我需要加快它。有什么方法可以并行计算吗？这样一种使用map reduce（apachehadoop实现）范式的方法？
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);
}
}
}
3条答案
按热度按时间3bygqnnd1#
正如在评论中提到的，我相当肯定，对实际应该做什么的形式化不是不清楚就是明显错误。比较“节点”的标准与示例不匹配。但是，一旦排序标准（以
Comparator)这应该很容易实现。在这里，比较两个“节点”的标准是节点中所有集合的大小之和，这与给出的示例相匹配（尽管它直观上没有意义，因为它不对应于任何真实的子集关系……）
qeeaahzv2#
如果你有一个基本的集合
S = {1, 2}，那么K = 2s的子集集是{{}, {1}, {2}, {1,2}}. 假设n仍然是2。那么你的输出就会是对的？对输出进行排序有点困难，因为结果不是完全有序的。但归根结底还是要数。不是像我最初想的那样，（k+1）元而是更多的（2^k）元。
为了确定一个集合是否是另一个集合的子集，可以使用素数。给原始集合的每个元素分配一个素数。在我的例子中，是2和3。子集集可以通过生成素数的所有乘积来建立。在我的例子中
{1 /* empty set */, 2, 3, 6}. 如果您有两套产品，以您的产品为代表，则很容易测试是否包含：这只是一堆想法，但它们可能会帮助你找到解决办法。当然，素数技巧只适用于原始集合中相对较少的元素，但只要k和n增长，无论如何都会遇到问题(输出中的元素数将是
(2^K)^N = 2^(NK). 如果K == N == 5，你会有2^(5 * 5) = 2^25，约3200万个产出要素。在这里，主要思想仍然有效）。编辑：我写了一个小java程序来展示我的想法。
保存到hasse.java
编译它：
javac Hasse.java运行它：java Hasse > hasse.dot运行点：dot -Tpdf -ohasse.pdf hasse.dot查看：acroread hasse.pdf源代码：wd2eg0qa3#
经过4次编辑和大量讨论，这个应用程序的目标慢慢变得更加清晰。事实上，我们必须考虑一个适当的形式化，但它最终似乎并不那么困难。
与我的第一个答案相比（https://stackoverflow.com/a/22092523 )这个新的迭代计算上一个层次的下一个层次（以及这个层次的核心，
createNextLevel，只有10行代码）。在
compute方法，可以将“edit4”中要求的修剪集成到while循环。编辑：评论中还有更多的请求。整合了它们。但这正变得荒谬。我想休息一下ü默恩。