A combination of N ordered elements
I
have a set of K elements and I need to create a combination of N ordered elements.
For example, if K=1 and I have {X1, emptyset} and n = 2 then I have an ordered pair, I need to do this:
Example 1:
({},{})
({X1},{}), ({},{X1})
({X1},{X1})
Note that I need to get the elements in the following order: first the element with node 0 as the sum of the two pairs, followed by the element with node 1, ecc
My idea was to make partial episodes of the initial set, one element at a time, but I lost my mind. Any suggestions? I need to do this in Java.
Edit 1:
In other words, I need to create a Hasse diagram:
http://en.wikipedia.org/wiki/Hasse_diagram
Where each node is an element of a partial set, the partial order function is the inclusion of all subsets, as follows:
Example 2:
ni = (S1i,S2i) C
nj = (S1j,S2j) only if S1i C S1j AND S21 C s2j
Edit 2: @RONALD:
If I have K=2 for the sets S = {1, 2} and n = 2, I need this output:
level0: ({}, {})
level1: ({1}, {}); ({2}, {}); ({}, {1}); ({}, {2})
level2: ({1,2}, {}); ({1}, {1}); ({1}, {2}); ({2}, {1}); ({2}, {2}); ({}, {1,2});
[..]
The order between levels is important, for example:
If at level 1 I have
({1}, {}); ({2}, {}); ({}, {1}); ({}, {2})
or
({}, {2}); ({}, {1}); ({2}, {}); ({1}, {});
It’s the same. But the important thing is that at level 2, I have all the supersets of level 2, and the supersets are explained in Example 2
Edit 3:
If my set is S= {x,y,z} and there is only one set per node, the result (starting from the bottom) looks like this:
http://upload.wikimedia.org/wikipedia/commons/e/ea/Hasse_diagram_of_powerset_of_3.svg
If I have S={1,2} and set two at a time I nod, it turns out like this (thanks to Ronald for the chart):
http://www.independit.de/Downloads/hasse.pdf
Edit 4:
Since this is a hyper-exponential problem, my thoughts are: I calculate one level at a time (in ordered mode!) And according to some rules I prune a node and all its supersets. Another stop rule might be to stop at some level. For this rule, the combinations must be evaluated directly in an ordered manner, rather than counting all combinations and then reordering.
EDIT 5:
The code for Marco13 works fine, I made some changes :
- Use the function PowerSet because it helps to combine only K elements of the collection S (for this I just need to get the first tot element of the powerset).
Now the algorithm does all the work, but I need to speed it up. Is there any way to do parallel computing? Such a way to use the Map Reduce (Apache hadoop implementation) paradigm?
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);
}
}
}
Solution
After 4 edits and a lot of discussion, the goals of this app slowly became clearer. It is true that one has to consider a proper formalization, but it does not seem so difficult in the end.
In contrast to my first answer (https://stackoverflow.com/a/22092523), this new answer iteratively calculates the next layer (its core) from the previous layer createNextLevel is just 10 lines of code).
In the compute method, the pruning required in “EDIT4” can be integrated into the while loop.
EDIT: There are more requests in the comments. Integrate them. But this becomes ridiculous. 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);
}
}
}