public class WordAmountStream { private Alphabet alpha; int upperWordBorder = 100;//Anzahl der ersten Element einer Menge M die ausgegeben werden public WordAmountStream(ArrayList<String> alphabet){ this.alpha = new Alphabet(alphabet); } /** * Berechnet die Potenzmenge einer Menge M. * @return Potenzmenge */ public ArrayList<ArrayList<String>> getPotency(){ ArrayList<ArrayList<String>> potencyAmount = new ArrayList<ArrayList<String>>(); countPotency(alpha.getAlphabet(),potencyAmount); ArrayList<String> emptyAmount = new ArrayList<String>(); emptyAmount.add(0, " "); potencyAmount.add(0, emptyAmount); return potencyAmount; } private void countPotency(ArrayList<String> alphabet,ArrayList<ArrayList<String>> potencyAmount){ MyStack<ArrayList<String>> stack = new MyStack<ArrayList<String>>(); if(alphabet.isEmpty()){ return; } // fülle den Stack for(String letter : alphabet){ ArrayList<String> tempAmount = new ArrayList<String>(); tempAmount.add(letter); stack.add(tempAmount); } //trage die erste Teilmenge ein potencyAmount.add(stack.getElementAt(0)); while (!stack.isEmpty()){ //hole die erste nicht leere Menge aus dem Stack und füge diese der Potenzmenge hinzu ArrayList<String> firstAmount = stack.pop(); //potencyAmount.add(firstAmount); ArrayList<String> nextSubsetToPush = new ArrayList<String>(); for(int i = 0;i < stack.getSize();i++){ //kombiniere alle Restmengen mit der ersten Menge ArrayList <String> tmpSubset = new ArrayList<String>(firstAmount); tmpSubset.add(stack.getElementAt(i).get(0)); if(i == 0){ nextSubsetToPush = new ArrayList<String>(tmpSubset); } potencyAmount.add(tmpSubset); } //ersetze das nächste Element mit der ersten Kombination stack.pop(); if(!stack.isEmpty()){ stack.push(nextSubsetToPush); } } //lösche das erste zeichen aus dem Alphabet und rufe erneut die Funktion auf if(stack.isEmpty()){ alphabet.remove(0); countPotency(alphabet,potencyAmount); } } /** * Gibt alle Wörter aus A* über dem Alphabet A, bis zur upperBorder, zurück. * Bemerkung: eingegebene Menge A muss geordnet sein * @return Liste der ersten n Elemente */ public ArrayList<String> getWordAmount(int upperBorder){ ArrayList<String> amount = new ArrayList<String>(); amount.add(" "); int count = 0; for (int i = 0; i < alpha.getAlphabet().size(); i++){ String currentLetter = alpha.getLetter(i); amount.add(currentLetter); count++; } for (int i = 1; i < amount.size(); i++){ for (int j = 0; j < alpha.getAlphabet().size(); j++){ String currentLetter = amount.get(i) + alpha.getLetter(j); amount.add(currentLetter); count++; } if(count >= upperWordBorder){ break; } } return amount; } private class Alphabet{ private ArrayList <String> alpha; public Alphabet (ArrayList <String> alpha){ this.alpha = new ArrayList<String>(alpha); } public String getLetter(int index){ if( index < alpha.size() ){ return alpha.get(index); } return null; } public ArrayList<String> getAlphabet(){ return alpha; } } }
MyStack.java
