Potenzmenge (Rekursion?)

[Opfer]

Hallo zusammen.

Ich ruecke gleich mal mit dem raus, was ich schaffen moechte: ich moechte aus einer Menge von n Elementen (die zu Anfang eingegeben werden koennen) alle k-elementigen Teilmengen ausgeben (k soll vom Benutzer gewaehlt werden koennen).

Irgendwie muss das wohl mittels Rekursion gehen, aber ich kriegs einfach nicht hin. Es ist nicht so, dass ich etwas code und das dann Fehlermeldungen ausspuckt, sondern so, dass ich keine Ahnung habe, wie ich ansetzen soll.
Das ist das erste Programm, was ich schreibe, ich habe bisher nur ein Javabuch ueberflogen und dort auch einige Beispiele nachvollzogen.

Grundsaetzlich hatte ich mir ueberlegt, die n Werte ueber Argumente einzulesen, danach das k waehlen zu lassen und dann die komplette Potenzmenge zu bestimmen. Die Teilmengen sollten dann in Arrays gespeichert sein. Danach wuerde ich das ganze Filtern, also nur die Felder der Laenge k ausgeben.

Klar gibt es fertige Algorithmen, die die Potenzmenge bestimmen. Aber ich wuerde das gerne von Hand programmieren oder programmiert sehen (falls denn jemand sofort weiss wies geht, koennte er es auch runtertippen ). Dabei sollten die Ansprueche an mein Wissen nicht zu hoch sein:
Ich weiss was Klassen, Methoden und Felder Schleifen und der ganze Kram so ist, aber bei manchen Codes gibts trotzdem Dinge, die ich nicht verstehe.

Also konkretes Problem: Wie fang ich an?
Hab ich z.B. eine Menge
{1,2,3,4} gegeben, so wuerde ich intuitiv so vorgehen:
Einelementige Teilmengen: {1},{2}...
...
Dreielementige Teilmengen: {1,2,3},{1,2,4},{1,3,4}.

Nun duerfen ja innerhalb einer Menge Elemente nicht mehrfach vorkommen, ich muss also, nachdem ein Element gewaehlt wurde, das Array auf die weiteren Wahlmoeglichkeiten einschraenken (z.B. bei der ersten Menge: Erstes Element 1. Dann Wahlmoeglichkeiten zwischen 2,3 und 4.)

Ich koennte (eigentlich koennte ich auch das nicht, aber das waere eine weitere Moeglicjkeit) natuerlich auch ALLE Kombinationen waehlen und dann mit For-Schleifen filtern. Weiss aber nicht, ob das besser ist bzw. scheint mir das nicht elegant zu sein.

Fuer Hilfe waere ich dankbar.

Gruss

 

[Marco13]

Muss es rekursiv sein? Ansonsten ist das ja nur eine http://www.java-forum.org/java-basics-anfaenger-themen/99672-potenzmenge-bedingung.html ...

 

[Opfer]

Den Thread hatte ich gesehn. Aus gewissen Gruenden moechte ich es schon gerne rekursiv haben. Nicht zuletzt, um mich mal mit dem Thema richtig vertraut zu machen. Ist es denn ueberhaupt zu realisieren, so wie ich mir das vorstelle?

 

[Opfer]

Hmm, also bin das noch mal durchgegangen. Ich glaube so richtig sinnvoll kann man das mittels Rekursion nicht wirklich umsetzen.

Gibt es denn eine andere, elementare Moeglichkeit? Meine eigentliche Aufgabe lautet, einen Pseudocode zu dem genannten Problem ("ich moechte aus einer Menge von n Elementen (die zu Anfang eingegeben werden koennen) alle k-elementigen Teilmengen ausgeben (k soll vom Benutzer gewaehlt werden koennen).") anzugeben. Das wollte ich zur Uebung in Java implementieren.

Kann mir jemand einen Tipp geben, wie ein "einfacher" Pseudocode fuer dieses Problem in etwa aussehen koennte?

 

[Final_Striker]

Naja, ich würde es so machen wie du es schon oben beschrieben hast. Erst alle einelementige, dann zweielementigen usw. Mengen raus suchen. Wenn du dann noch die Ergebnisse in einem HashSet speicherst, bekommst du am Ende keine doppelten Mengen. ;-)

 

[Opfer]

Das Problem ist, dass ich keine Ahnung habe, wie ich das als Pseudocode aufschreiben soll. Pseudocode hat ja quasi schon die Art Form, so dass man es nur noch in "Java-Sprache" umwandeln muss.
Die einzige Moeglichkeit, die mir einfaellt, ist eben Rekursion. Ansonsten ginge es mit mindestens k Schleifen, aber k ist ja vorab nicht bekannt.
Habe Loesungen gefunden, aber da wird mit Listen gearbeitet. Ich habe keine Ahnung, was ne Liste ist und habe gerade auch nicht die Zeit, mich da einzulesen.

Wie gesagt, eine elementare Loesung ist angestrebt, auch wenn sie noch so umstaendlich ist.

 

[JohannisderKaeufer]

Versuche erstmal alle Einelementigen Mengen rekursiv auszugeben.

Also erstes Element zurückgeben und dieses Element aus der gegebenen Menge Entfernen.

Nun die Menge in der das erste Element fehlt wieder an die Methode übergeben um die nächste einelementige Menge zu finden.

Wenn das geklappt hat: GUT.

 

[JohannisderKaeufer]

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package rekursion;

import java.util.HashSet;
import java.util.Set;

/**
 *
 * @author JohannisderKaeufer
 */
public class Main {

    public static /*Set<int[]>*/ void potenzMenge(int k,int[] head, int[] ursprungsMenge) {
//        Set<int[]> result = new HashSet();
        if (k == 1) {
            int[] anArray = head.clone();
            anArray[anArray.length-k] = ursprungsMenge[0];
//            result.add(anArray);
            printArray(anArray);

            if (ursprungsMenge.length >1) {
                int[] ursprungsMengeOhneErstesElement = removeFirst(ursprungsMenge);
//                result.addAll(potenzMenge(k, head, ursprungsMengeOhneErstesElement));
                potenzMenge(k, head, ursprungsMengeOhneErstesElement);
            }

        }else{
           int[] anArray = head.clone();
           anArray[anArray.length-k] = ursprungsMenge[0];
//           result.addAll(potenzMenge(k-1, anArray, removeFirst(ursprungsMenge)));
           potenzMenge(k-1, anArray, removeFirst(ursprungsMenge));
           if(k<ursprungsMenge.length){
//           result.addAll(potenzMenge(k, anArray, removeFirst(ursprungsMenge)));
               potenzMenge(k, anArray, removeFirst(ursprungsMenge));
           }
        }



  //      return result;

    }

    public static void printResult(Set<int[]> result){
        for(int[] array:result){
            printArray(array);
        }
    }
    public static void main(String[] args) {
        int[] testArray = {1,2,3,4,5,6,7,8,9,10};

       for(int i = 1;i<=testArray.length;i++){
           System.out.println("===::: alle "+i + "-Elementigen Teilmengen :::===");
//        printResult(potenzMenge(i, new int[i], testArray));
           potenzMenge(i,new int[i],testArray);
          
        }
    }

    private static int[] removeFirst(int[] ursprungsMenge) {
        int[] result = new int[ursprungsMenge.length - 1];
        for (int i = 0; i < result.length; i++) {
            result[i] = ursprungsMenge[i + 1];
        }
        return result;
    }

    private static void printArray(int[] array) {
        System.out.print("[");
            for(int i : array){
                System.out.print(i+" ");
            }
            System.out.println("]");
    }
}

 

[Illuvatar]

Und weil ich grade Lust hatte, noch eine andere Fassung
Das ganze generisch, und mit Listen statt Arrays find ichs besser lesbar.
Viel Spaß damit:

import java.util.*;

public class Powerset
{
  public static void main(String[] args)
  {
    printPowerset(Arrays.asList(new String[]{"a","b","c","d","e","f","g"}), 3);
  }
  
  /**
   * Prints all subsets of the list with k elements.
   * If two or more subsets contain the same elements in a different order, only
   * one of those subsets (that in which the order is like in the original list)
   * is printed.
   */
  public static<T> void printPowerset(List<T> list, int k)
  {
    if (list == null) throw new NullPointerException();
    if (k < 0 || k > list.size()) throw new IllegalArgumentException();
    if (k == 0) return;
    
    List<T> given = new LinkedList<T>(list);
    List<T> chosen = new LinkedList<T>();
    printRec(given, chosen, k, 0);
  }
  
  /**
   * Takes all elements (starting at element l) from given, adds them to chosen
   * and then calls itself.
   * If chosen contains k elements, the list is printed, the function returns
   * and the last element is put back in the given list.
   */
  private static<T> void printRec(List<T> given, List<T> chosen, int k, int l)
  {
    if (chosen.size() == k) {
      System.out.println(chosen);
    } else {
      for (int i = l; i < given.size(); i++) {
        T elem = given.get(i);
        given.remove(elem);
        chosen.add(elem);
        printRec(given, chosen, k, i); // put 0 instead of i and all subsets will
        given.add(i, elem);            // be printed, even if they are permutations
        chosen.remove(elem);
      }
    }
  }
}

 

[Opfer]

Oh Mann, vielen Dank euch beiden. Konnte leider nicht schon eher antworten, hatte noch zu tun. Zumindest den ersten Code konnte ich schon soweit nachvollziehen (bis ich das sauber hinbekommen haette, waeren Stunden vergangen...).
Werde mir noch anschauen, was genau Listen so sind

Ich glaube, dieser Thread wird noch vielen Leuten helfen, die Frage wurde schon oft gestellt, aber die anderen Loesungen, die ich gesehen habe, waren nicht so elementar.

Danke nochmals.