Kombinatorik - Algorithmus gesucht

[muemmel_0811]

****************************************************************
****** Frohes neues Jahr wünsch ich Euch allen hier!! ********
****************************************************************


Ich bin mir nicht sicher, ob ich auf dem Schlauch stehe, oder ob das Problem doch gar nicht so trivial ist und von daher bräuchte ich mal wieder Euren Rat...

Folgende Menge ist gegeben: {A, B} - um es erstmal einfach zu halten.
Aus diesen 2 Buchstaben möchte ich nun folgende Kombinationen erstellen:
- A
- B
- A + B

Sprich: jede Variation darf nur einmal vorkommen und A+B == B+A und somit wäre ein solches Ergebnis doppelt und damit falsch.

Ich weiß, dass Problem mit den 2 Einträgen lässt sich noch von Hand programmieren, aber es soll ja flexibel sein und x Einträge verkraften und mir dann eben automatisch die möglichen Variationen am Ende ausgeben.

Hat da jemand von Euch einen Ansatz für mich, mit dem ich mich beschäftigen und mein Problem lösen kann - gibt's vielleicht sogar eine Funktion in Java, die das kann - Fragen über Fragen und ich würde mich sehr über Eure Tipps freuen

viele Grüße vom muemmel_0811

 

[SlaterB]

du musst die Elemente sortieren,
dann zwei Schleifen ineinander,
eine von Anfang an bis fast zum Ende, die innere vom Nachfolger des akutellen äußeren Elements bis zum Ende und kombinieren

komplizierter wirds, wenn du als Ausgangslage A, B, AB hast
und daraus A, B, AB, AAB, BAB erstellen willst,
aber nicht A, B, AB (als Ursprungselement), AB (als neue Kombination von A + B), AAB, BAB

wenn es solche Überschneidungen von vorhandenen und neu kombinierten Elementen geben kann und diese nicht erlaubt sind,
dann musst du zusätzlich auf doppelte prüfen, z.B. mit einem HashSet,

eine solche Doppelte-Prüfung ist generell der einfache sichere Weg, falls du für alle erzeugten Elemente eine einheitliche Darstellung hast,
dann ginge auch eine ganz einfache nxn-Doppelschleife um alle Elemente mit allen anderen zu kombinieren,
die oben erwähnte Schleife ist aber intelligenter

 

[Illuvatar]

Vorbemerkung: am Besten konvertierst du deine Menge (Set) zuerst mal in eine Liste (List). Das hat den Vorteil, dass jedes Element über einen Index angesprochen werden kann.
(Das Verfahren, das ich gleich beschreibe, würde übrigens äquivalent mit einem SortedSet funktionieren, falls du soetwas schon hast)

Für den eigentlichen Algorithmus wäre das hier mein Tip: mach es rekursiv. Die Funktion um die Potenzmenge (das ist es ja, was du willst) zu berechnen, sieht dann so aus:
- Wenn eine 1-elementige Menge übergeben wurde, ist es trivial.
- Wenn eine n-elementige Menge übergeben wurde, berechne die Potenzmenge der Menge von allen Elementen außer dem ersten. In die Ergebnismenge kommt für jedes Menge in der berechneten Potenzmenge einmal die Menge selbst, und einmal die Menge selbst vereinigt mit dem ersten Element.

 

[Marco13]

EDIT: Mann, das was hier mit "equals" und so steht, ist so peinlich, dass ich es fast gelöscht hätte ...

Wenn es nicht höchst-Zeitkritisch ist, tut's vermutlich schon die schlichte Berechnung der Potenzmenge, wobei die Ergebnisse in eine Set eingefügt werden, und "equals" (und hashCode) für die Ergebnisse eben soo überschrieben ist, dass sie für A+B und B+A als gleich gelten.

In 10 Minuten schnell hingehackt

import java.util.*;

class PowerSetElement
{
    private Object elements[];

    public PowerSetElement(Object ... elements)
    {
        this.elements = elements;
    }


    public int hashCode()
    {
        int result = 0;
        for (Object element : elements)
        {
            result ^= element.hashCode();
        }
        return result;
    }

    public boolean equals(Object object)
    {
        if (object==this) return true;
        if (object==null) return false;
        if (!(object instanceof PowerSetElement))
        {
            return false;
        }
        // Hack:
        PowerSetElement other = (PowerSetElement)object;
        Set<Object> a = new HashSet<Object>(Arrays.asList(this.elements));
        Set<Object> b = new HashSet<Object>(Arrays.asList(other.elements));
        return a.containsAll(b) && b.containsAll(a);
    }


    public String toString()
    {
        String result = "";
        for (int i=0; i<elements.length; i++)
        {
            result += elements[i];
            if (i<elements.length-1)
            {
                result += "+";
            }
        }
        return result;
    }
}

class PowerSetTest
{

    public static void main(String args[])
    {
        System.out.println(computePowerSet("A", "B"));
        System.out.println(computePowerSet("A", "B", "C"));
    }

    public static Set<PowerSetElement> computePowerSet(Object ... input)
    {
        Set<PowerSetElement> result = new HashSet<PowerSetElement>();
        int n = input.length;
        long m = 1L << n;
        for (long i=1; i<m; i++)
        {
            result.add(compute(i, input));
        }
        return result;
    }

    private static PowerSetElement compute(long pattern, Object ... input)
    {
        List<Object> elements = new ArrayList<Object>();
        for (int i=0; i<input.length; i++)
        {
            long b = 1L << i;
            if ((pattern & b) != 0)
            {
                elements.add(input[i]);
            }
        }
        return new PowerSetElement(elements.toArray());
    }

}

Für Eingabemengen mit mehr als 63 Elementen müßte man BigInteger bzw. ein BitSet verwenden...

 

[Illuvatar]

Ich hab meinen Ansatz auch mal in Code umgesetzt. Was besser ist... weiß nicht. Das mit den Bitoperationen ist schon hübsch Meins könnte aber bisschen schneller sein (keine doppelten Elemente) und braucht keine BigIntegers... nur der Stack ist eben irgendwann voll, und die Rekursion gibt auch noch einen gewissen Overhead. Naja:

import java.util.*;

public class Potenzmenge
{
  private static final SortedSet<?> EMPTY_SET = new TreeSet<Object>();

  public static void main(String[] args)
  {
    SortedSet<Integer> testSet = new TreeSet<Integer>();
    testSet.add(1);testSet.add(2);testSet.add(3);testSet.add(4);
    
    Set<SortedSet<Integer>> powerSet = calculatePowerSet (testSet);
    System.out.println(powerSet);
  }

  @SuppressWarnings("unchecked")
  public static <T> Set<SortedSet<T>> calculatePowerSet (SortedSet<T> set)
  {
    Set<SortedSet<T>> ret = new HashSet<SortedSet<T>>(); // wird zurückgegeben
    
    // rekursionsabbruch
    if (set.size() <= 1) {
      ret.add ((SortedSet<T>)EMPTY_SET);
    }
    if (set.size() == 1) {
      ret.add (set);
    }
    
    // rekursion
    if (set.size() > 1) {
      // aufteilen in erstes Element und Restliste
      T firstElement = set.first();
      SortedSet<T> tailSet = new TreeSet<T>(set); // hack - ich kenn keinen wirklich guten anderen Weg dafür
      tailSet.remove(firstElement);
      
      Set<SortedSet<T>> tailPowerSet = calculatePowerSet (tailSet); // rekursion
      
      for (SortedSet<T> subset : tailPowerSet) {
        SortedSet<T> union = new TreeSet<T>(subset); // neues set, das zusätzlich das erste El. von vorhin enthält
        union.add(firstElement);
        
        ret.add (subset);
        ret.add (union);
      }
    }
    
    return ret;
  }
  
}

 

[Marco13]

...

....
      SortedSet<T> tailSet = new TreeSet<T>(set); // hack - ich kenn keinen wirklich guten anderen Weg dafür

Ist das nicht http://java.sun.com/j2se/1.4.2/docs/api/java/util/TreeSet.html#tailSet(java.lang.Object) !? ???:L

 

[Illuvatar]

Nein, das dachte ich auch erst, aber:

Returns a view of the portion of this set whose elements are greater than or equal to fromElement.

D.h. ich bräuchte das zweite Element dafür...

Edit: Hmm... grad mal mit 20 Elementen probiert... mittlerweile bei 1,05GB RAM-Verbrauch - dafür läufts aber auch schon seit 10min
Gut dass ich auf 4GB RAM aufgestockt hab.

 

[Marco13]

Mögen die Spiele beginnen

Die "Einschränkung" auf <=63 Elemente ist keine wirkliche Einschränkung. Selbst wenn bei 63 Elementen jedes Ergebnis nur ein byte belegen würde, käme man mit 4GB nicht weit - dann bräuchte man... *grübel* ... 9 Milliarden GB oder so...

Hab's gerade mal mit 20 Elementen getestet. Auf meiner 2.4 Ghz Kiste hat er innerhalb von ca. 8 Minuten die Lösung gefunden, und dabei nur 130MB belegt .... (bis er die Menge dann mit System.out.println ausgegeben hat, da ist er schlagartig auf 300MB hochgeschnellt um letztendlich einen 22 MB großen String zu bauen :lol: )

Hier nochmal die "optimierte" Version

import java.util.*;

class PowerSetElement
{
    private Object elements[];
    private int hashCode = 0;

    public PowerSetElement(Object ... elements)
    {
        this.elements = elements;
        this.hashCode = computeHashCode();
    }

    public int hashCode()
    {
        return hashCode;
    }


    public int computeHashCode()
    {
        int result = 0;
        for (Object element : elements)
        {
            result ^= element.hashCode();
        }
        return result;
    }

    public boolean equals(Object object)
    {
        if (object==this) return true;
        if (object==null) return false;
        if (!(object instanceof PowerSetElement))
        {
            return false;
        }
        PowerSetElement other = (PowerSetElement)object;
        return equal(this.elements, other.elements);
    }

    private static boolean equal(Object aa[], Object bb[])
    {
        if (aa.length != bb.length)
        {
            return false;
        }
        for (Object b : bb)
        {
            if (!contains(aa, b))
            {
                return false;
            }
        }
        return true;
    }

    private static boolean contains(Object aa[], Object b)
    {
        for (Object a : aa)
        {
            if (a.equals(b))
            {
                return true;
            }
        }
        return false;
    }



    public String toString()
    {
        String result = "";
        for (int i=0; i<elements.length; i++)
        {
            result += elements[i];
            if (i<elements.length-1)
            {
                result += "+";
            }
        }
        return result;
    }
}

class PowerSetTest
{

    public static void main(String args[])
    {
        //System.out.println(computePowerSet("A", "B"));
        System.out.println(computePowerSet(
            "A", "B", "C", "D",
            "E", "F", "G", "H",
            "I", "J", "K", "L",
            "M", "N", "O", "P",
            "Q", "R", "S", "T"
        ));
    }

    public static Set<PowerSetElement> computePowerSet(Object ... input)
    {
        int n = input.length;
        long m = 1L << n;
        Set<PowerSetElement> result = new HashSet<PowerSetElement>((int)m);
        for (long i=1; i<m; i++)
        {
            if (i%1000==0) System.out.println(i+" of "+m);
            result.add(compute(i, input));
        }
        return result;
    }

    private static PowerSetElement compute(long pattern, Object ... input)
    {
        int size = 0;
        for (int i=0; i<input.length; i++)
        {
            long b = 1L << i;
            if ((pattern & b) != 0)
            {
                size++;
            }
        }
        Object elements[] = new Object[size];
        int n =0;
        for (int i=0; i<input.length; i++)
        {
            long b = 1L << i;
            if ((pattern & b) != 0)
            {
                elements[n++] = input[i];
            }
        }
        return new PowerSetElement(elements);
    }

}

 

[muemmel_0811]

Wow - ich bin begeistert - vielen vielen Dank für Eure Hilfe :applaus:

Da meine Java-Kenntnisse grad mal von Tastatur bis Bildschirm reichen, wird es ein bisschen dauern, bis ich Eure Anregungen bzw. Codes umgesetzt/verstanden habe - also nicht böse sein, wenn ich mich die nächsten Tage erstmal aus der Diskussion raus halten werde.

Danke nochmal!!!

Grüße vom muemmel_0811

 

[0x7F800000]

omfg...
sorry jungs: eure vorschläge erschienen mir vieeel zu kompliziert, da habe ich zwei eigene gebastelt: einmal für Set<X>:
[edit] alles suboptimal, lieber gleich den dritten (den allerhässlichsten ) Vorschlag mit dem ganzen reflection-Kram nehmen [/edit]

public static <X> Set<Set<X>> calculatePowerSet(Set<X> set){
		Set<Set<X>> powerSet=new HashSet<Set<X>>(), temp;
		powerSet.add(new HashSet<X>()); // empty set is always contained in power set
		
		for(X x:set){
			temp=new HashSet<Set<X>>();
			for(Set<X> subset:powerSet){
				//copy subset into tempSubset
				Set<X> tempSubset=new HashSet<X>();
				for(X t:subset){
					tempSubset.add(t);
				}
				//add one more element into tempSubset
				tempSubset.add(x);
				//add tempSubset into temp
				temp.add(tempSubset);
			}
			//merge powerSet and temp into next powerSet
			powerSet.addAll(temp);
		}
		return powerSet;
	}

braucht scheißlange zum rechnen, sehet selbst:

Size of the set: 17
Time needed for calculation: 17846 ms
Size of the power set: 131072

und dann habe ich nochmal eine variante für arrays gebastelt, sieht dann so aus:

@SuppressWarnings("unchecked")
	public static <X> X[][] calculatePowerSet(X... s){
		X[][] result=(X[][])new Object[1<<s.length][];
		result[0]=(X[])new Object[0]; //start with empty set
		for(int pow=0; pow<s.length; pow++){
			for(int i=0; i<1<<pow; i++){
				result[i+(1<<pow)]=(X[]) new Object[result[i].length+1];
				System.arraycopy(result[i], 0, result[i+(1<<pow)], 0, result[i].length);
				result[i+(1<<pow)][result[i].length]=s[pow];
			}
		}
		return result;
	}

funktioniert unendlich schneller :toll: , funktioniert aber nicht :bloed:

Size of the array: 17
Time needed for calculation: 48 ms
Size of the power-'array': 131072

Was heißt "funktioniert nicht"? Es liefert "rein optisch" dieselben ergebnisse, aber ich kann diesem drecksverdammten compiler nicht erklären, dass da String[][] rauskommt (weil ja X[][] davorsteht???) es gibt immer Object[][] raus, und kotzt mich dann noch an, wenn ich das wieder nach String[][] casten will, obwohl das alles Strings sind. ICH RAFFS NICHT :cry: :cry: :cry:
Kann mir bitte endlich mal am beispiel dieser Konkreten Methode erklären, wie ich aus diesen verfluchten Generics endlich mal ein bisschen generizität rausprügeln kann? :x (Oder soll ich dafür schon wieder einen Thread mehr aufmachen? :cry: )

Hier nochmal der gesamte compilierbare beispiel mit allen tests und ausgaben:

package sets;

import java.util.*;

public class SetMath {
	
	/**
	 * calculates power set for a finite set
	 * @param <X>			Any Class
	 * @param set			Set S of Instances of X
	 * @return				Power Set of the set S 
	 */
	public static <X> Set<Set<X>> calculatePowerSet(Set<X> set){
		Set<Set<X>> powerSet=new HashSet<Set<X>>(), temp;
		powerSet.add(new HashSet<X>()); // empty set is always contained in power set
		
		for(X x:set){
			temp=new HashSet<Set<X>>();
			for(Set<X> subset:powerSet){
				//copy subset into tempSubset
				Set<X> tempSubset=new HashSet<X>();
				for(X t:subset){
					tempSubset.add(t);
				}
				//add one more element into tempSubset
				tempSubset.add(x);
				//add tempSubset into temp
				temp.add(tempSubset);
			}
			//merge powerSet and temp into next powerSet
			powerSet.addAll(temp);
		}
		return powerSet;
	}
	
	@SuppressWarnings("unchecked")
	public static <X> X[][] calculatePowerSet(X... s){
		X[][] result=(X[][])new Object[1<<s.length][];
		result[0]=(X[])new Object[0]; //start with empty set
		for(int pow=0; pow<s.length; pow++){
			for(int i=0; i<1<<pow; i++){
				result[i+(1<<pow)]=(X[]) new Object[result[i].length+1];
				System.arraycopy(result[i], 0, result[i+(1<<pow)], 0, result[i].length);
				result[i+(1<<pow)][result[i].length]=s[pow];
			}
		}
		return result;
	}
	
	//kleiner test
	public static void main(String... _){
		
		char N=17;
		
		// TEST FUER DIE SET-VERSION
		Set<String> set=new HashSet<String>();
		for(char c='A'; c<'A'+N; c++) set.add(String.valueOf(c));
		long time;
		System.out.println( "Start of calculation: "+(time=System.currentTimeMillis()));
		System.out.println( "Size of the set: "+set.size());
		Set<Set<String>> powerSet=calculatePowerSet(set);
		System.out.println( "Time needed for calculation: "+(System.currentTimeMillis()-time)+" ms");
		System.out.println( "Size of the power set: "+powerSet.size());
		
		// OPTIONALE AUSGABE DER ERGEBNISSE DER SET-VERSION
		/*
		for(int i=5; i>0; i--){
			System.out.println("You have "+i+" seconds to kill the programm, before the output starts");
			try{
				Thread.sleep(1000);
			}catch(Exception e){}
		}
	
		for(Set<String> s:powerSet){
			System.out.println(s);
		}
		//*/
		
		// TEST FUER DIE ARRAY-VERSIONSet<String> set=new HashSet<String>();
		String[] array=new String[N];
		for(int i=0; i<array.length; i++) array[i]=String.valueOf((char)('A'+i));

		System.out.println( "Start of calculation: "+(time=System.currentTimeMillis()));
		System.out.println( "Size of the array: "+array.length);
		Object[][] powerArray=calculatePowerSet(array);
		System.out.println( "Time needed for calculation: "+(System.currentTimeMillis()-time)+" ms");
		System.out.println( "Size of the power-'array': "+powerArray.length);
		
		//OPTIONALE AUSGABE FUER ARRAY-VERSION
		/*
		System.out.print("[");
		for(Object[] a:powerArray){
			System.out.print(Arrays.toString(a));
		}
		System.out.println("]");
		//*/
	}
}

ich will jetzt nicht muemmel_0811's thread dafür kapern, wenn jemand einen verbesserungsvorschlag zu der array-version hat, dann schreibt bitte pn. Ich suche solange nach derselben frage in älteren threads, bin vor kurzm schon über dieselbe scheiße gestolpert, und musste es am ende aufgeben

 

[0x7F800000]

WHAAAAAAAAAAAAA!!! SIEGESGEHEUL!!!

	@SuppressWarnings("unchecked")
	public static <X> X[][] calculatePowerSet(X... s){
		X[][] result=(X[][])java.lang.reflect.Array.newInstance(s.getClass(), 1<<s.length);
		result[0]=(X[])java.lang.reflect.Array.newInstance(s.getClass().getComponentType(), 0); //start with empty set
		for(int pow=0; pow<s.length; pow++){
			for(int i=0; i<1<<pow; i++){
				result[i+(1<<pow)]=(X[])java.lang.reflect.Array.newInstance(s.getClass().getComponentType(),result[i].length+1);
				System.arraycopy(result[i], 0, result[i+(1<<pow)], 0, result[i].length);
				result[i+(1<<pow)][result[i].length]=s[pow];
			}
		}
		return result;
	}

ich komm mir hier zwar irgendwie so ähnlich vor, als ob ich hier eher mit Assembler herumhantieren würde :shock: , aber immerhin: für 17-Elementige Mengen braucht diese Implementierung nicht mal eine zehntel sekunde, was mindestens 1200 Mal schneller ist, als meine erste Implementierung, und anscheinend auch schneller, als Marco13's umfangreiches Werk
Mit 20 habe ich das nicht probiert: mir geht der Speicher aus. Wenn ihr mir sagt, wo bei eclipse die Schraube für den verfügbaren Speicherplatz ist, dann kann ich euch gerne auch Vergleichsergebnisse für 20-elementige Mengen liefern.

Die Implementierung ist leider extremst hässlich. Ich hasse Generics immer noch. Aber Java hasse ich nicht mehr : für diese bescheuerten Generischen Arrays habe ich jetzt eine übel riechende, aber immerhin einzeilige Lösung gefunden, ich brauche da keine redundante Klassen-Typ-Argumente zu übergeben, ich kann damit jetzt leben. Wobei ich absolut nicht nachvollziehen kann, warum zum teufel dieses tausend mal verdammte

public static <T> T[] myMethod(T[] param){
  ___=new T[12345];
}

nicht einfach automatisch vom compiler in

public static <T> T[] myMethod(T[] param){
  ___=(T[]) java.lang.reflect.Array.newInstance(param.getClass().getComponentType(),12345);
}

umgewandelt wird, warum muss ich das dauernd manuell machen, das ist doch hässlich wie die Pest? ???:L

na gut, egal. so ist es halt nunmal, wenn man irgendwelche tolle features nachträglich ans laufende Motor drankleben will. Es ist hässlich. Aber es ist selten. Und es ist nur eine Zeile. Alles gut. :toll:

 

[0x7F800000]

Aber wisst ihr was leute... Diese ganze geschichte erweckt in mir erneut den Wunsch, so eine art "precompiler" für java zu bauen, der zB. solche monströsen konstrukte durch andere, für mich persönlich wesentlich "intuitivere" ersetzt.
Genau dasselbe mit überladenen operatoren. Da würde ich auch lieber bei BigIntegern lieber "+" hinschreiben, und den precompiler die ganze Schreibarbeit übernehmen lassen.

Für sowas braucht man ja nicht mal irgendwelche tieferen Erkenntnisse aus dem Compilerbau, ich würde eigentlich einfach nur die Syntax für mich geringfügig modifizieren, dann hätte ich ja eine für mich perfekte Sprache, mit minimalen Aufwand

Ich mag ja Java :toll: Aber solche Kleinigkeiten wie dieses abgefahrene reflection-monstrum versetzen mich manchmal einfach nur in Panik.

 

[Landei]

Schaue das Licht! :lol:

 

[Marco13]

Aaaaalso: Wer von euch hat mir das Gras in die Kippen gemischt? :x

Dieses ganze "umfangreiche Werk" mit dem PowerSetElement ist natürlich komplett überflüssig. Ich weiß zwar nicht mehr, wie ich darauf gekommen bin, aber ... es werden die Elemente der Potenzmenge berechnet, und die sind schon eindeutig Man kann sich also das ganze Gemurkse mit dem HashSet und dem PowerSetElement sparen, und raus kommt

import java.util.*;


class PowerSetTest2
{

    public static void main(String args[])
    {
        //System.out.println(computePowerSet("A", "B"));

        long time;
        System.out.println( "Start of calculation: "+(time=System.currentTimeMillis()));
        Object[][] result = computePowerSet(
            "A", "B", "C", "D",
            "E", "F", "G", "H",
            "I", "J", "K", "L",
            "M", "N", "O", "P",
            "Q", "R", "S", "T",
            "U", "V"
        );
        System.out.println( "Time needed for calculation: "+(System.currentTimeMillis()-time)+" ms");
        //System.out.println(result);
    }

    public static Object[][] computePowerSet(Object ... input)
    {
        int n = input.length;
        long m = 1L << n;
        Object[][] result = new Object[(int)m][];
        for (long i=1; i<m; i++)
        {
            //if (i%1000==0) System.out.println(i+" of "+m);
            result[(int)i] = compute(i, input);
        }
        return result;
    }

    private static Object[] compute(long pattern, Object ... input)
    {
        int size = 0;
        for (int i=0; i<input.length; i++)
        {
            long b = 1L << i;
            if ((pattern & b) != 0)
            {
                size++;
            }
        }
        Object elements[] = new Object[size];
        int n =0;
        for (int i=0; i<input.length; i++)
        {
            long b = 1L << i;
            if ((pattern & b) != 0)
            {
                elements[n++] = input[i];
            }
        }
        return elements;
    }

}

@Andrey: Bei deiner Lösung habe ich nicht ganz kapiert, in welcher Reihenfolge und warum und so die Elemente in die Potenzmengenelemente eingefügt werden... In meiner compute-Methode wird das Bimuster der Zahl verwendet, um die einzufügenden Elemente auszuwählen ... Darauf läuft's bei dir wohl auch raus, aber ... wie und warum ... konnt' ich spontan nicht nachvollziehen.... aber ist wohl nicht so wichtig.

 

[0x7F800000]

Aaaaalso: Wer von euch hat mir das Gras in die Kippen gemischt? :x

:lol: :toll:

Bei deiner Lösung habe ich nicht ganz kapiert, in welcher Reihenfolge und warum und so die Elemente in die Potenzmengenelemente eingefügt werden...

Was ich da mache ist recht einfach:
- ich fange mit der leeren menge an
- in jedem schritt k verdoppele ich die bereits vorhandenen mengen, und hänge an die zweite hälfte das k-te element aus der eingabemenge an, was man unter dem ganzen gruseligen reflection-shice gar nicht mehr erkennen kann. Am Beispiel mit der eingabemenge {a,b,c,d} würde die schrittweise berechnung der Potenzmenge etwa so aussehen:

[]

[]
[a]

[]
[a]
[b]
[ab]

[]
[a]
[b]
[ab]
[c]
[ac]
[bc]
[abc]

[]
[a]
[b]
[ab]
[c]
[ac]
[bc]
[abc]
[d]
[ad]
[bd]
[abd]
[cd]
[acd]
[bcd]
[abcd]

und voila, da ist doch schon die ganze Potenzmenge da
Dieses "verdoppeln und bei der Hälfte das k-te Element anfügen" entspricht ja praktisch genau dem markieren des k-ten Bits bei deiner Lösung, aber ich find's so irgendwie direkter.

Und jetzt erzähl mir nicht, dass in deinen Rechner die Lösungen für 27-elementige eingabemengen reinpassen? :shock: das wären doch... öhm... so um die 12 Pointer * 4 byte * 2^27 Arrays...
äääh... so um die 6144 MByte, also mehr als 6 Gigabyte? :shock: Und dabei läuft noch das BS und JRE und eclipse und das alles Frisst nochmal ~1.5 GByte? Was hast du denn da für'n rechner rumstehen, mit 8GB Ram oder was? ???:L
Wo schraub ich denn den Speicherplatz hoch :bahnhof: ... muss ich hier schon wieder rumgoogln ey

 

[Marco13]

Ich hatte mir in deins Debug-Ausgaben eingebaut, und jetzt hast du's nochmal erklärt, und das klang auch logisch und nachvollziehbar, aber trotzdem kann ich das Codestück, und das, was du beschrieben hast, spontan und nur durch Draufschauen irgendwie nicht "matchen" (also, warum das Codestück genau DAS macht). Offenbar kann es sehr unterschiedliche Vorstellungen davon geben, was "direkter" ist :wink: Aber trickreich (effizient und geschickt) ist es auf jeden Fall.

 

[0x7F800000]

aber trotzdem kann ich das Codestück, und das, was du beschrieben hast, spontan und nur durch Draufschauen irgendwie nicht "matchen" (also, warum das Codestück genau DAS macht).

nja, wie gesagt... geht alles komplett im reflection-chaos unter :cry: da verstehe ich selber nicht wo was ist^^
wenn man die vielen potenzierungs-shifts mitbetrachtet, dann sieht man da echt nichts mehr, ich denk mal, dass ich in einer woche auch nicht mehr sagen kann was es ist und was es macht

27

alles klar^^ hab die mächtigkeit einer Teilmenge {A,...,V} des englischn Alphabets auf 27 geschätzt, obwohl es da insgesamt 26 Buchstaben gibt, perfekt :toll:

 

[Marco13]

Ja, war auch ein bißchen spät gestern :roll: ... das
for(int i=0; i<1<<pow; i++){... result[i+(1<<pow)]= ...
hatte mich irgendwie irritiert, aber das ist ja gerade das Hinzufügen der Elemente in der Hälfte, wo sie eben hinzugefügt werden müssen.
BTW: Dieses Erstellen generischer Arrays finde ich auch häßlich - aber wenn man sich dafür Hilfsmethoden bastelt, kann man sowas wie
X[][] result=(X[][])java.lang.reflect.Array.newInstance(s.getClass(), 1<<s.length);
ggf. ändern in
X[][] result=createArray2D(s.getClass(), 1<<s.length);
und den Teil in der inneren Schleife zu sowas wie
result = append(result, s[pow]);

Was mich bei beiden Ansätzen ein bißchen nervt, ist die umständliche Größenbestimmung der Elemente. Bei dir bewirkt das ja ständige Arrayvergrößerungen/Umkopierungen, und bei mir das .... alberne Zählen der gesetzen Bits, um genau solche umkopierungen zu vermeiden... :? Aber wenn man's drauf anlegen würde...

[]
[a]
[b]
[ab]
[c]
[ac]
[bc]
[abc]
[d]
[ad]
[bd]
[abd]
[cd]
[acd]
[bcd]
[abcd]

-> Arraygrößen:

0
1
1
2
1
2
2
3
1
2
2
3
2
3
3
4
...
die http://www.research.att.com/~njas/sequences/A000120 könnte man da ja vermutlich leicht einbauen. (Irgendwie erinnert mich die Berechnungsvorschrift im ersten Kommentar dort frappierend an deinen Algorithmus ... aber ... bei so einem starken Zusammenhang ist das wohl kein Wunder....)

 

[0x7F800000]

Bei dir bewirkt das ja ständige Arrayvergrößerungen/Umkopierungen, und bei mir das .... alberne Zählen der gesetzen Bits, um genau solche umkopierungen zu vermeiden

wieso willst du "umkopierungen vermeiden"? Das ist bei meiner methode doch grad das gute, dass ich große blöcke am Stück per System.arraycopy() umkopieren kann, das ist doch viel schneller, jeweils ein element hinzuzufügen, als jede teilmenge jedes mal komplett vom neuen aufzubauen.

Deine methode ist aber für was ganz anderes sehr schön: das ist nämlich eine explizite bijektion zwischen {1,..,2^n} und der Potenzmenge. D.h. man kann auf jedes Element der Potenzmenge einzeln zugreifen, ohne alle anderen elemente im Speicher vorliegen zu haben. Das ist zwar bei "kleinen" potenzmengen womöglich etwas langsamer, aber bei großen Potenzmengen hat man eh keine wahl: alle elemente passen niemals in den speicher. Aber man will vielleicht trotzdem alle Elemente durchlaufen. Und dazu ist so eine Bijektion schon praktisch
Wozu man alle elemente einer Potenzmenge durchlaufen will, ist wiederum eine andere Frage

 

[0x7F800000]

bwoah, das ist ja witzig^^ Wer will, kann das hier mit meiner ersten Set-Basierten Variante ausprobieren:

    public static void main(String... _){
		Set<?> x=new HashSet<Object>();
		System.out.println(x);
		for(int i=0; i<4; i++){
			x=calculatePowerSet(x);
			System.out.println(x);
		}
	}

und bitte nicht 5 statt 4 reinschreiben, sonst stirbt der Rechner

Da kommt dann sowas witziges raus:

[]
[[]]
[[[]], []]
[[[], [[]]], [[]], [[[]]], []]

Potenz der leeren Menge {} ist eine Menge, die nur die Leere Menge beinhaltet, also {{}}
Potenzmenge der Potenzmenge der Leeren Menge ist dann {{{}},{}}
Potenzmenge davon ist dann { {{{}},{}},{{{}}},{{}},{} }
und der nächste Schritt ist dann das,, was man in der vierten Zeile sieht, voooll witzig
Wächst wie 2^(2^(2^(...2^0))))...), hat also am anfang 0 Elemente, dann
1=2^0
2=2^1
4=2^2
16=2^4
65536=2^16
dann schon irgendwas sehr sehr großes, was sicher in keinen Rechner mehr passt. :lol:

 

[Marco13]

Ja, das war einer der Punkte, bei denen man sich darüber streiten könnte, was "direkter" ist:
- "das aktuelle Element" zur Hälfte aller bisherigen Mengen hinzuzufügen oder
- die n-te Potenzmenge (direkt :wink: ) zu erstellen.

Wegen des Umkopierens ... da hatte ich (doch, immernoch) etwas falsch interpretiert ... hatte das irgendwie so aufgefaßt als würden da bestehende Arrays jedes mal um 1 vergrößert, aber das sind dann ja gleich die neuen. (Manchmal bin ich schon langsam...).

Hab die letzen Stände nochmal in einem Microbenchmark zusammengefasst - aber ich sitz' hier grad an so einer Gurke mit "wenig" RAM, da kann man das nicht so richtig testen...

// Von [url]http://www.java-forum.org/de/posting.php?mode=reply&t=80425[/url]

import java.util.*;

class PowerSetTests
{
    public static void main(String args[])
    {
        //test(3); if (true) return;

        for (int N=15; N<=21; N++)
        {
            long time=0;
            int M = 24-N;

            String[] array=new String[N];
            for(int i=0; i<array.length; i++) array[i]=String.valueOf((char)('A'+i));

            long before = 0;
            long after = 0;
            long noopt = 0;

            before = System.currentTimeMillis();
            for (int i=0; i<M; i++) noopt += computePowerSet((Object[])array).length;
            after = System.currentTimeMillis();
            System.out.println("Marco13 "+N+": "+(after-before)/M);

            before = System.currentTimeMillis();
            for (int i=0; i<M; i++)noopt += calculatePowerSet(array).length;
            after = System.currentTimeMillis();
            System.out.println("Andrey  "+N+": "+(after-before)/M);

            System.out.println(noopt);
        }

    }

    private static void test(int N)
    {
        String[] array=new String[N];
        for(int i=0; i<array.length; i++) array[i]=String.valueOf((char)('A'+i));
        System.out.println("Marco13");
        print(computePowerSet((Object[])array));
        System.out.println("Andrey");
        print(calculatePowerSet((Object[])array));
    }

    private static void print(Object array[][])
    {
        for (int i=0; i<array.length; i++)
        {
            System.out.print("{");
            for (int j=0; j<array[i].length; j++)
            {
                System.out.print(array[i][j]);
            }
            System.out.println("}");
        }
    }



    //--- Marco13
    public static Object[][] computePowerSet(Object ... input)
    {
        int n = input.length;
        long m = 1L << n;
        Object[][] result = new Object[(int)m][];
        for (long i=0; i<m; i++)
        {
            //if (i%1000==0) System.out.println(i+" of "+m);
            result[(int)i] = compute(i, input);
        }
        return result;
    }

    private static int sizeFor(int n)
    {
        int tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
        return ((tmp + (tmp >> 3)) & 030707070707) % 63;
    }

    private static Object[] compute(long pattern, Object ... input)
    {
        int size = sizeFor((int)pattern);
        Object elements[] = new Object[size];
        int n =0;
        for (int i=0; i<input.length; i++)
        {
            long b = 1L << i;
            if ((pattern & b) != 0)
            {
                elements[n++] = input[i];
            }
        }
        return elements;
    }


    //---- Andrey
    @SuppressWarnings("unchecked")
    public static <X> X[][] calculatePowerSet(X... s){
        X[][] result=(X[][])java.lang.reflect.Array.newInstance(s.getClass(), 1<<s.length);
        result[0]=(X[])java.lang.reflect.Array.newInstance(s.getClass().getComponentType(), 0); //start with empty set
        for(int pow=0; pow<s.length; pow++){
            for(int i=0; i<1<<pow; i++){
                result[i+(1<<pow)]=(X[])java.lang.reflect.Array.newInstance(s.getClass().getComponentType(),result[i].length+1);
                System.arraycopy(result[i], 0, result[i+(1<<pow)], 0, result[i].length);
                result[i+(1<<pow)][result[i].length]=s[pow];
            }
        }
        return result;
    }

}

 

[Marco13]

Ach ja, zu deiner witzigen Set-Konstruktion... das erinnerte mich irgendwie an http://de.wikipedia.org/wiki/Natürliche_Zahl#Von_Neumanns_Modell_der_nat.C3.BCrlichen_Zahlen

 

[0x7F800000]

Ach ja, zu deiner witzigen Set-Konstruktion... das erinnerte mich irgendwie an http://de.wikipedia.org/wiki/Natürliche_Zahl#Von_Neumanns_Modell_der_nat.C3.BCrlichen_Zahlen

Naja, da man sich in mathe ja alles letztendlich aus der leeren menge konstruiert, ist das nicht sonderlich verwunderlich. Sieh dir mal die konstruktion der surrealen zahlen an, ist auch witzig, und auch direkt aus der leeren menge heraus

 

[0x7F800000]

Naaa blendend :x
Verdammter reflection-workaround ist nicht nur hässlich sondern auch noch lahm :?

Hab hier eine etwas einfachere benchmark aus deiner gebastelt, mit 3 variationen meines algos...

package sets;

//Von [url]http://www.java-forum.org/de/posting.php?mode=reply&t=80425[/url]

import java.util.*;

class PowerSetTests
{
 public static void main(String args[])
 {
	 Object[] array=new Object[20];
	 for(int i=0; i<array.length; i++) array[i]=""+i;
	 
	 int tries=20;
	 
     long t=System.currentTimeMillis();
     for(int i=0; i<tries; i++) computePowerSet(array);
     System.out.println("Marco13: \t\t\t"+(System.currentTimeMillis()-t));
     
     t=System.currentTimeMillis();
     for(int i=0; i<tries; i++) calculatePowerSet(array);
     System.out.println("Andrey (mit reflection):\t"+(System.currentTimeMillis()-t));
     
     t=System.currentTimeMillis();
     for(int i=0; i<tries; i++) calculatePowerSet2(array);
     System.out.println("Andrey (mit object[][]):\t"+(System.currentTimeMillis()-t));
     
     t=System.currentTimeMillis();
     for(int i=0; i<tries; i++) calculatePowerSet3(array);
     System.out.println("Andrey (reflection optimiert): \t"+(System.currentTimeMillis()-t));
 }

 //--- Marco13
 public static Object[][] computePowerSet(Object ... input)
 {
     int n = input.length;
     long m = 1L << n;
     Object[][] result = new Object[(int)m][];
     for (long i=0; i<m; i++)
     {
         //if (i%1000==0) System.out.println(i+" of "+m);
         result[(int)i] = compute(i, input);
     }
     return result;
 }

 private static int sizeFor(int n)
 {
     int tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
     return ((tmp + (tmp >> 3)) & 030707070707) % 63;
 }

 private static Object[] compute(long pattern, Object ... input)
 {
     int size = sizeFor((int)pattern);
     Object elements[] = new Object[size];
     int n =0;
     for (int i=0; i<input.length; i++)
     {
         long b = 1L << i;
         if ((pattern & b) != 0)
         {
             elements[n++] = input[i];
         }
     }
     return elements;
 }


 //---- Andrey
 @SuppressWarnings("unchecked")
 public static <X> X[][] calculatePowerSet(X... s){
     X[][] result=(X[][])java.lang.reflect.Array.newInstance(s.getClass(), 1<<s.length);
     result[0]=(X[])java.lang.reflect.Array.newInstance(s.getClass().getComponentType(), 0); //start with empty set
     for(int pow=0; pow<s.length; pow++){
         for(int i=0; i<1<<pow; i++){
             result[i+(1<<pow)]=(X[])java.lang.reflect.Array.newInstance(s.getClass().getComponentType(),result[i].length+1);
             System.arraycopy(result[i], 0, result[i+(1<<pow)], 0, result[i].length);
             result[i+(1<<pow)][result[i].length]=s[pow];
         }
     }
     return result;
 }

 @SuppressWarnings("unchecked")
 public static <X> X[][] calculatePowerSet2(X... s){
     X[][] result=(X[][])new Object[1<<s.length][];
     result[0]=(X[])new Object[0]; //start with empty set
     for(int pow=0; pow<s.length; pow++){
        for(int i=0; i<1<<pow; i++){
           result[i+(1<<pow)]=(X[]) new Object[result[i].length+1];
           System.arraycopy(result[i], 0, result[i+(1<<pow)], 0, result[i].length);
           result[i+(1<<pow)][result[i].length]=s[pow];
        }
     }
     return result;
  }
 
 @SuppressWarnings("unchecked")
 public static <X> X[][] calculatePowerSet3(X... s){
	 Class xArrayClass=s.getClass();
	 Class xClass=xArrayClass.getComponentType();
	 int created,newIndex;
     X[][] result=(X[][])java.lang.reflect.Array.newInstance(s.getClass(), 1<<s.length);
     result[0]=(X[])java.lang.reflect.Array.newInstance(xArrayClass, 0); //start with empty set
     for(int pow=0; pow<s.length; pow++){
         created=1<<pow;
    	 for(int i=0; i<created; i++){
    		 newIndex=created+i;
             result[newIndex]=(X[])java.lang.reflect.Array.newInstance(xClass,result[i].length+1);
             System.arraycopy(result[i], 0, result[newIndex], 0, result[i].length);
             result[newIndex][result[i].length]=s[pow];
         }
     }
     return result;
 }
 
}

Deine Lösung läuft irgendwie trotzdem schneller, als meine offizielle (1) und sogar schneller, als die optimierte (3), was ich irgendwie nicht verstehe. Reflection workaround ist einfach nur lahm. Sieht man vor allem beim direkten Vergleich mit der Object-Variante, die so ca. 40% schneller ist (2):

Marco13: 			10982
Andrey (mit reflection):	12809
Andrey (mit object[][]):	7567
Andrey (reflection optimiert): 	11186

Ja, geil... Wenn's so ist, dann sollen die doch am besten gleich willkürliche casts in beliebige datentypen zulassen, wie in C++ o.ä. Da wäre zwar die Typsicherheit zwar dahin, aber es wäre weniger hässlich, und es würde 2x schneller laufen, tolle wurscht :cry:


Wie du siehst ist deine endgültige Lösung zwar schneller, allerdings musst du deine variante wohl oder übel an meiner 2. implementierung messen, weil bei beiden dauernd ClassCastExceptions fliegen:

String[][] ps=(String[][])computePowerSet(new String[]{"A","b","C"});

ooh ne, diese lahmheit mach mich so traurig

 

[Marco13]

Hmja... das ganze ist im Grunde noch das, was ich als erste Antwort gepostet hatte, und das was "schnell hingehackt". Hab jetzt mal testweise generische Arrays eingebaut, und das ist auch 40% langsamer... hätt' ich aber auch nicht gedacht.... 8o Naja OK. In bezug auf die Anzahl der durchzuführenden Operationen ist deine Lösung vermutlich optimal - die "Bijektion" kostet eben Rechenaufwand .... :wink:

 

[muemmel_0811]

Hallo Ihr beiden,

wie gesagt, meine Java-Kenntnisse halten sich echt in Grenzen und bei meiner Suche im www wegen einem ähnlichen Problem bin ich nun über diesen Code gestolpert - und ich bin begeistert , denn der funktioniert auf meinem 512 MB-Hauptspeicher-Kasten mit insgesamt 20 Elementen ohne HeapSpace-Probleme und das ist für meine Bedürfnisse vollkommen ausreichend.

import java.util.ArrayList;
import java.util.Arrays;

public class Powerset {

    public static char[][] powerset(char[] set) {
            if (set == null)
                    return null;

            int setLength = set.length;
            int powersetLength = (int) Math.pow(2, setLength);
            char[][] result = new char[powersetLength][];

            for (int i = 0; i < powersetLength; i++) {

                    String binaryString = Integer.toBinaryString(i);
                    while (binaryString.length() < setLength)
                            binaryString = "0" + binaryString;

                    ArrayList<Character> tempSet = new ArrayList<Character>(setLength);

                    for (int j = 0; j < setLength; j++)
                            if (binaryString.charAt(j) == '1')
                                    tempSet.add(set[j]);

                    char[] tempSet2 = new char[tempSet.size()];
                    int index = 0;
                    for (char c : tempSet)
                            tempSet2[index++] = c;

                    result[i] = tempSet2;
            }

            return result;
    }

    public static void main(String[] args) {

            char[][] pows = powerset(new char[] {'A', 'B', 'C', 'D'});

            for (char[] a : pows)
                    System.out.println(Arrays.toString(a));

    }

}

Aber trotzdem nochmal vielen vielen Dank an Euch beide für Eure Mühe!!! :applaus:

Grüße vom muemmel_0811

 

[Marco13]

Ja, das ist im wesentlichen von der Vorgehensweise her das gleiche wie bei mir - nur werden eben nur char's verwendet, während ich mit Strings (bzw. beliebigen Objekten) hantiert hatte. Vermutlich könnte man das, was du da jetzt gefunden hattest, noch deutlich effizienter machen, aber vielleicht ist das ja nicht so wichtig...

 

[muemmel_0811]

ich bin mal so frei und frag einfach hier in dem Thread weiter

Die eine Hälfte meines Problems hätte ich nun ja, aber da ist noch etwas, was ich noch bräuchte... aber es ist wie immer, ich hab noch nicht mal den Hauch einer Idee, in welche Richtung ich mich bewegen muss

Nehmen wir mal die Menge mit den Elementen {A, B, C, D}; alle Teilmengen sind ja mit obigem Code folgende:

[]
[D]
[code]
[C, D]
[B]
[B, D]
[B, C]
[B, C, D]
[A]
[A, D]
[A, C]
[A, C, D]
[A, B]
[A, B, D]
[A, B, C]
[A, B, C, D]

So, nun würde ich gerne mittels logischer Operatoren bspw. definieren können wollen, dass bspw. !A && !B (will heißen, der Teil hier soll flexibel sein gilt und damit nur noch folgende Teilmengen dem korrekten Ergebnis entsprechen:

[]
[D]
[code]
[C, D]
[B]
[B, D]
[B, C]
[B, C, D]
[A]
[A, D]
[A, C]
[A, C, D]

Mir fehlt, mal abgesehen vom Java-Know-how, schon eine grundlegende Idee, wie ich denn dieses Problem überhaupt lösen könnte
Meine bisherigen Überlegungen gingen in die Richtung, dass ich aus diesen Arrays (die es im Programm nunmal sind), zunächst mal Strings mache, aber wie gehen Strings dann mit den bool'schen Werten zusammen, so dass ich die logischen Ausdrücke bilden kann usw. usw. - Fragen über Fragen und einfach kein Land in Sicht, denn bis ich diese Gedankengänge in Java umgesetzt hab, um zu sehen, ob es überhaupt möglich ist, vergehen Ewigkeiten und ich hab die Lust an der Problemstellung verloren...

Vielleicht jemand da, der mir auf die Sprünge helfen will?

Danke und Grüße vom muemmel_0811

 

[0x7F800000]

sollte wohl not(A and B) heißen, wenn man sich das ergebnis so ansieht, also !(A & B)? ???:L

Ich weiß jetzt nicht was du machen willst, weil du es ja selbst nicht genau sagen kannst. Aber ich kann dir mit ziemlicher sicherheit sagen, dass die ganzen logischen programmiersprachen (von den es anscheinend eh nur eine einzige gibt: Prolog^^) mit den Horn-Klauseln rechnen, das hat sich so als am einfachsten zu handhaben und am schnellsten zu rechnen rausgestellt.

 

[muemmel_0811]

ähm ja, sorry - ich hab das in der letzten Zeit so schreiben müssen...

Aber wie können mir die Horn-Formeln weiterhelfen? Mein Problem ist doch allein schon, was mach ich aus den Arrays, damit ich mit den logischen Operatoren hantieren kann?

 

[Marco13]

Auch auf die Gefahr hin, mich wieder zu blamieren, weil ich das nicht richtig nachvollzogen habe: Vielleicht brauchst du die logischen Ausdrücke garnicht zu bilden, sondern kannst direkt die Ergebnisse verwenden. In dem Beispiel willst du ja z.B. die Elemente entfernen, bei denen A und B enthalten sind. Das sind genau die Elemente der Menge, für die
pattern % 4 == 3
gilt. Aber je nachdem WIE frei konfigurierbar das sein soll, muss man sich natürlich überlegen, wie man diese Kriterien codiert....

 

[muemmel_0811]

Auch auf die Gefahr hin, mich wieder zu blamieren

Du hast Dich doch nicht blamiert - sondern nur versucht, mir zu helfen und das ist das einzige, was zählt!

Wieder zurück zum Problem: na ja, das System soll am Ende schon sehr flexibel sein - es sollen auch Ausdrücke mit mehreren Operanden gehen. Wobei letzteres ja zur Not durch Klammern und Splitten in Einzel-Ausdrücke zerlegt werden kann.

Mir geht es zunächst mal nur um mein grundlegendes Problem, und zwar, dass ich mal wieder gar keine Vorstellung habe, wie das überhaupt gehen kann

Danke und Grüße,
muemmel_0811

 

[Marco13]

Du weißt schon, was es heißt, wenn in einem Arbeitszeugnis sowas steht wie "Er hat sich immer sehr bemüht..." :?

Wie auch immer..., deswegen ja: Das ist IMHO stark davon abhängig, wie man das ganze codiert, und wie es angewendet werden soll. Soll man die Mengen z.B. (grob gesagt) durch Strings beschreiben können, wie
char c[][] = getSetsWith("!(!(A && !B) || (!C || (D && E)))");
? Dann wird man um einen Parser kaum drumrumkommen. Wenn es nur darum geht, festzulegen: Ich will alle Mengen, die bestimmte Elemente (nicht) enthalten, d.h. wenn es eine Methode geben soll
char c[][] = getSetsContainingAll('A', 'B');
oder
char c[][] = getSetsContainingAnyOf('A', 'B');
dann wäre das SEHR viel einfacher.

Interessant wäre dann auch noch die Frage, ob von vornherein nur die ausgewählten Mengen erstellt werden sollen (wo sich dann meine "Bijektion" bezahlt machen würde :wink: ) oder ob aus der gegebenen, vollständigen Menge eine bestimmte Teilmenge ausgewählt werden soll....

 

[muemmel_0811]

irgendwie doppelt - nur den Beitrag darunter beachten

 

[muemmel_0811]

Du weißt schon, was es heißt, wenn in einem Arbeitszeugnis sowas steht wie "Er hat sich immer sehr bemüht..." :?

Ist das etwa eine böswillige Anspielung auf mein nicht vorhandenes Know-how?

Ich kann Dich beruhigen, ich programmiere nur zum Spaß in meiner Freizeit, im Job äußere ich nur Wünsche ggü. meinen SW-Entwicklern und wie die das dann im Einzelnen umsetzen, ist mir egal, solange das Ergebnis und die Performance stimmen :bae:
Der Job ist aber bei mir meist die Haupt-Quelle für irgendwelche Programm-Ideen - ob die Welt das nun braucht oder nicht oder ob es dafür vielleicht schon x kostenfreie oder Bezahl-Lösungen gibt, interessiert mich dabei nicht. Mir geht es dann bei sowas nur darum, dass ich das jetzt irgendwie selbst hinbekommen will und sei es am Ende nur der Unterschied zu einer bereits vorhandenen Lösung, dass ich mir die GUI so gestrickt hab, wie ich sie haben will. Außerdem ist es für mich die einzige Möglichkeit, das bisschen, was man bei mir als Programmier-Können bezeichnen kann, nicht zu verlernen und ggf. sogar noch vieles weiteres dazu zu lernen um vielleicht mal irgendwann besseres zu Stande zu bringen.

Und back to Topic: kannst Du mir den Rest Deines Beitrags bitte für Normal-Sterbliche nochmal näher bringen? Bijektion - ich kann mich gerade mal daran erinnern, dass eine Funktion bijektiv ist, wenn sie injektiv und surjektiv ist - aber um jetzt einen qualitative Antwort auf Deine Frage zu schreiben reicht es grad nicht - muss ja schließlich arbeiten.

Grüße,
muemmel_0811

 

[Marco13]

Nein, das war eine Anspielung auf dein beruhigendes ""Du wolltest ja nur helfen..."" - im allgemeinen (!) versuche ich mich an die Empfehlung aus dem Berühmten Zitat von Dieter Nuhr zu halten... "Wenn man keine Ahnung hat...". Also, wenn ich nicht glaube, was hilfreiches schreiben zu können, schreib' ich i.a. eher nichts.

Bzgl Bijektion und so: Das bezog sich auf den grundsätzlich unterschiedlichen Ansatz von Andrey und mir: Bei Andrey's Ansatz werden alle Elemente der Menge "simultan" aufgebaut. Bei einer Menge mit 3 Elementen hat die Ergebnismenge 8 Elemente. Und damit man das 8. Element bekommt, muss (GROB gesagt) man alle anderen Elemente schon berechnet haben (nicht wirklich "alle", aber andernfalls würde es vmtl. kompliziert werden). Und wie sich gezeigt hat, ist Andreys Methode die schnellste, wenn man ALLE Elemente berechnen will, weil bei der Berechnung des letzten Elements schon auf die Ergebnisse aus den ersten Elementen zurückgeriffen werden kann, und man sich damit arbeit spart.

Bei mir wird (in der "compute"-Methode) das n-te Element der Ergebnismenge erstellt. Ganz "isoliert". Man könnte also sagen
element = compute(7, input);
und würde damit sofort NUR das 8. Element bekommen.

Deswegen könnte die Frage relevant sein: Willst du erst ALLE Elemente erstellen, und daraus dann eine Teilmenge "auswählen", oder sollen von vornherein nur die Elemente berechnet werden, die in deiner Teilmenge liegen sollen.

(Beachte aber, dass diese Frage u.U. stark mit der Frage zusammenhängen könnte, wie du deine "Auswahl" beschreiben willst)