Alle Möglichkeiten, n-Anzahl aus Elementen aus einem Array zu wählen, ausgeben?

[DerSophist]

Also, wenn mein Titel noch etwas unverständlich ist: Ich würde gerne mithilfe einer Methode den Binomialkoeffizienten veranschaulichen. Hierbei speichert man alle Werte in ein Array, die möglich sind z.B. "rot", "grün" und "blau". Nun soll die Methode alle Möglichkeiten berechnen, wie man 2 Elemente aus diesem Array auswählen kann. (Also müsste sie am Ende ausgeben: rot,grün ; rot,blau ; grün, blau).
Die Methode muss jedoch variabel sein, was die Länge des Arrays angeht und wie viele Elemente man aus diesem Array auswählen möchte.

Meine Überlegung: Ich denke dies ist mithilfe von Rekursion umzusetzen. Also, dass ich eine for-schleife mache, in der ich die Methode wieder aufrufe und immer eine beliebige Farbe aus dem ersten Array speichere. Aber ich habe meinerseits Rekursion in Java auch noch nicht komplett verstanden, weshalb meine Umsetzungen bis jetzt immer fehlgeschlagen sind. Ich freue mich über jede Hilfe (muss jetzt nicht zwangsläufig als Code erfolgen, freue mich auch über Tipps)

 

[Flown]

Ist es mit Zurücklegen oder ohne?

 

[Xyz1]

Das Thema hatten wir eigentlich hier schon einmal:

Alle Zeichenkombinationen eines Strings iterativ herausfinden

Hallo zusammen, ich habe für ein Projekt eine Methode erstellt, die einen String erhält und alle möglichen Zeichenkombinationen in einer ArrayList zurückgibt (also bei String "abc": abc acb bac bca cab cba). Ich habe das rekursiv gelöst und hier stellt sich mein Problem, nämlich der enorme...

www.java-forum.org

So geht es iterativ

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

/**
 * Hello world!
 */
public class App {
	public static ArrayList<ArrayList<String>> per(String... s) {
		ArrayList<ArrayList<String>> list = new ArrayList<ArrayList<String>>();
		list.add(new ArrayList<String>(Arrays.asList(s)));
		int i = 1;
		int[] j = new int[s.length];
		while (i < s.length) {
			if (j[i] < i) {
				int k = ((i % 2) == 0) ? 0 : j[i]; // siehe StackOverflow

				// swapping
				String b = s[i];
				s[i] = s[k];
				s[k] = b;
				list.add(new ArrayList<String>(Arrays.asList(s)));

				j[i]++;
				i = 1;
			} else {
				j[i] = 0;
				i++;
			}
		}
		return list;
	}

	public static void main(String[] args) {
		ArrayList<ArrayList<String>> list = per("Rot", "Grün", "Blau");
		for (ArrayList<String> l : list) {
			System.out.println(l);
		}
	}
}

 

[DerSophist]

Ist es mit Zurücklegen oder ohne?

Ohne Zurücklegen

 

[DerSophist]

Das Thema hatten wir eigentlich hier schon einmal:

Alle Zeichenkombinationen eines Strings iterativ herausfinden

Hallo zusammen, ich habe für ein Projekt eine Methode erstellt, die einen String erhält und alle möglichen Zeichenkombinationen in einer ArrayList zurückgibt (also bei String "abc": abc acb bac bca cab cba). Ich habe das rekursiv gelöst und hier stellt sich mein Problem, nämlich der enorme...

www.java-forum.org

So geht es iterativ

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

/**
* Hello world!
*/
public class App {
    public static ArrayList<ArrayList<String>> per(String... s) {
        ArrayList<ArrayList<String>> list = new ArrayList<ArrayList<String>>();
        list.add(new ArrayList<String>(Arrays.asList(s)));
        int i = 1;
        int[] j = new int[s.length];
        while (i < s.length) {
            if (j[i] < i) {
                int k = ((i % 2) == 0) ? 0 : j[i]; // siehe StackOverflow

                // swapping
                String b = s[i];
                s[i] = s[k];
                s[k] = b;
                list.add(new ArrayList<String>(Arrays.asList(s)));

                j[i]++;
                i = 1;
            } else {
                j[i] = 0;
                i++;
            }
        }
        return list;
    }

    public static void main(String[] args) {
        ArrayList<ArrayList<String>> list = per("Rot", "Grün", "Blau");
        for (ArrayList<String> l : list) {
            System.out.println(l);
        }
    }
}

Aber diese Methode gibt einfach alle Permutationen des Array aus. Ich will wissen, wie ich aus einem Array mit 3 Elementen alle Möglichkeiten zwei Elemente auszuwählen ausgeben kann, Der Output bei meinem Beispiel müsste irgendwie so sein:
[rot, grün]
[rot, blau]
[grün, blau]
Die Reihenfolge ist völlig irrelevant...

 

[mihe7]

Spielen wir mal Lotto: Du hast eine Menge von n Kugeln. Bei der Ziehung der ersten Kugel hast Du n Möglichkeiten (1. Zieung). Für jede dieser n Möglichkeiten könntest Du eine weitere Kugel ziehen. Dabei stehen aber nur noch n-1 Kugeln zur Verfügung (2. Ziehung). Für jede dieser n-1 Kugeln könntest Du eine weitere Kugel ziehen, dabei stehen aber nur noch n-2 Kugeln zur Verfügung (3. Ziehung) usw. Das kannst Du so lange machen, bis ausreichend Kugeln gezogen wurden oder keine Kugeln mehr zur Verfügung stehen (den Fall lassen wir mal weg).

Es gibt also mehrere Ziehungen und für jede Ziehung eine Menge an Kugeln, die behandelt werden muss. Ausgabe erfolgt, wenn die letzte Ziehung erfolgt ist.


Schema:

public void koeff(Object[] elems, Object[] draw, int n) {
    Object[] result = kopieMitReserve(draw);
    for (Object e : elems) {
        result[draw.length] = e;
        if (result.length < n) {
            koeff(remove(elems, e), result, n);
        } else {
            ausgabe(result);
        }
    }
}

private Object[] kopieMitReserve(Object[] inp) {
    Object[] result = new Object[inp.length+1];
    System.arraycopy(inp, 0, result, 0, inp.length);
    return result;
}

Die remove-Methode gibt ein neues Array mit allen Elementen aus elems außer e zurück.

 

[Xyz1]

Ich will wissen, wie ich aus einem Array mit 3 Elementen alle Möglichkeiten zwei Elemente auszuwählen ausgeben kann

Das hast Du anfangs nicht geschrieben.

 

[DerSophist]

Spielen wir mal Lotto: Du hast eine Menge von n Kugeln. Bei der Ziehung der ersten Kugel hast Du n Möglichkeiten (1. Zieung). Für jede dieser n Möglichkeiten könntest Du eine weitere Kugel ziehen. Dabei stehen aber nur noch n-1 Kugeln zur Verfügung (2. Ziehung). Für jede dieser n-1 Kugeln könntest Du eine weitere Kugel ziehen, dabei stehen aber nur noch n-2 Kugeln zur Verfügung (3. Ziehung) usw. Das kannst Du so lange machen, bis ausreichend Kugeln gezogen wurden oder keine Kugeln mehr zur Verfügung stehen (den Fall lassen wir mal weg).

Es gibt also mehrere Ziehungen und für jede Ziehung eine Menge an Kugeln, die behandelt werden muss. Ausgabe erfolgt, wenn die letzte Ziehung erfolgt ist.


Schema:

public void koeff(Object[] elems, Object[] draw, int n) {
    Object[] result = kopieMitReserve(draw);
    for (Object e : elems) {
        result[draw.length] = e;
        if (result.length < n) {
            koeff(remove(elems, e), result, n);
        } else {
            ausgabe(result);
        }
    }
}

private Object[] kopieMitReserve(Object[] inp) {
    Object[] result = new Object[inp.length+1];
    System.arraycopy(inp, 0, result, 0, inp.length);
    return result;
}

Die remove-Methode gibt ein neues Array mit allen Elementen aus elems außer e zurück.

Wofür genau ist bei den Parametern int n da?

 

[Xyz1]

Wofür genau ist bei den Parametern int n da

Länge der Permutationen

 

[DerSophist]

Das hast Du anfangs nicht geschrieben.

Wenn in der Frage etwas mit Binomialkoeffizient steht, sollte ersichtlich sein können, dass es sich nicht um Permutationen handelt.... aber egal, tut mir leid, wenn ich mich missverständlich ausgedrückt habe...

 

[mihe7]

Wofür genau ist bei den Parametern int n da?

Gesamtzahl der Ziehungen.

 

[Xyz1]

aber egal, tut mir leid, wenn ich mich missverständlich ausgedrückt habe

Na dann ist es doch easy going und stellt nicht wirklich ein Problem dar:

import java.util.ArrayList;
import java.util.List;

/**
 * Hello world!
 */
public class App {
	public static ArrayList<ArrayList<String>> per(int n, String... s) {
		ArrayList<ArrayList<String>> list = new ArrayList<ArrayList<String>>();
		for (int i = 0; i < s.length; i++) {
			for (int j = i + 1; j < s.length; j++) {
				// if (i != j) {
				list.add(new ArrayList<String>(List.of(s[i], s[j])));
				// }
			}
		}
		return list;
	}

	public static void main(String[] args) {
		ArrayList<ArrayList<String>> list = per(2, "Rot", "Grün", "Blau", "Schwarz");
		for (ArrayList<String> l : list) {
			System.out.println(l);
		}
	}
}

 

[Xyz1]

Bearbeitung, aus irgendeinem Grund war mein Compiler noch auf 1.5 eingestellt, deswegen diese ewig langen diamonds.

 

[DerSophist]

Gesamtzahl der Ziehungen.

Spielen wir mal Lotto: Du hast eine Menge von n Kugeln. Bei der Ziehung der ersten Kugel hast Du n Möglichkeiten (1. Zieung). Für jede dieser n Möglichkeiten könntest Du eine weitere Kugel ziehen. Dabei stehen aber nur noch n-1 Kugeln zur Verfügung (2. Ziehung). Für jede dieser n-1 Kugeln könntest Du eine weitere Kugel ziehen, dabei stehen aber nur noch n-2 Kugeln zur Verfügung (3. Ziehung) usw. Das kannst Du so lange machen, bis ausreichend Kugeln gezogen wurden oder keine Kugeln mehr zur Verfügung stehen (den Fall lassen wir mal weg).

Es gibt also mehrere Ziehungen und für jede Ziehung eine Menge an Kugeln, die behandelt werden muss. Ausgabe erfolgt, wenn die letzte Ziehung erfolgt ist.


Schema:

public void koeff(Object[] elems, Object[] draw, int n) {
    Object[] result = kopieMitReserve(draw);
    for (Object e : elems) {
        result[draw.length] = e;
        if (result.length < n) {
            koeff(remove(elems, e), result, n);
        } else {
            ausgabe(result);
        }
    }
}

private Object[] kopieMitReserve(Object[] inp) {
    Object[] result = new Object[inp.length+1];
    System.arraycopy(inp, 0, result, 0, inp.length);
    return result;
}

Die remove-Methode gibt ein neues Array mit allen Elementen aus elems außer e zurück.

Könntest du vielleicht mal ein Beispiel dafür machen, wie man die Methode benutzt. Also Parameter eingeben und dann die Ausgabe erklären?

 

[Xyz1]

Könntest du vielleicht mal ein Beispiel dafür machen, wie man die Methode benutzt

Kannst Du das nicht selber? Das ist trivial.

 

[httpdigest]

Hier ist ein Beispiel, wenn `n` (in deinem Fall = 2) variabel sein soll:

import static java.util.Collections.emptyList;
import static java.util.stream.Collectors.toList;
import static java.util.stream.IntStream.range;
import static java.util.stream.Stream.of;
import static java.util.stream.Stream.concat;
import java.util.*;
import java.util.stream.Stream;
public class Sets {
  public static <T> Stream<List<T>> permutationsOfSizeN(int n, T... elements) {
    return permutationsOfSizeN(n, 0, emptyList(), elements);
  }
  private static <T> Stream<List<T>> permutationsOfSizeN(int n, int i, List<T> acc, T... elements) {
    return n > 0
        ? range(i, elements.length).boxed().flatMap(k -> 
            permutationsOfSizeN(n - 1, k + 1, 
                concat(acc.stream(), of(elements[k])).
                collect(toList()), elements))
        : Stream.of(acc);
  }
  /*
   * Beispiel:
   */
  public static void main(String[] args) {
    permutationsOfSizeN(1, "Rot", "Grün", "Blau", "Braun").forEach(System.out::println);
  }
}

Hat Spaß gemacht, das zu bauen.

 

[DerSophist]

Hier ist ein Beispiel, wenn `n` (in deinem Fall = 2) variabel sein soll:

import static java.util.Collections.emptyList;
import static java.util.stream.Collectors.toList;
import static java.util.stream.IntStream.range;
import static java.util.stream.Stream.of;
import static java.util.stream.Stream.concat;
import java.util.*;
import java.util.stream.Stream;
public class Sets {
  public static <T> Stream<List<T>> permutationsOfSizeN(int n, T... elements) {
    return permutationsOfSizeN(n, 0, emptyList(), elements);
  }
  private static <T> Stream<List<T>> permutationsOfSizeN(int n, int i, List<T> acc, T... elements) {
    return n > 0
        ? range(i, elements.length).boxed().flatMap(k ->
            permutationsOfSizeN(n - 1, k + 1,
                concat(acc.stream(), of(elements[k])).
                collect(toList()), elements))
        : Stream.of(acc);
  }
  /*
   * Beispiel:
   */
  public static void main(String[] args) {
    permutationsOfSizeN(1, "Rot", "Grün", "Blau", "Braun").forEach(System.out::println);
  }
}

Hat Spaß gemacht, das zu bauen.

Wenn ich das ausführe kommt der Error:
Error98, 60) java: incompatible types: bad type in conditional expression
inference variable R has incompatible bounds
equality constraints: com.sun.tools.javac.util.List<T>
lower bounds: com.sun.tools.javac.util.List<java.lang.Object>

 

[httpdigest]

lower bounds: com.sun.tools.javac.util.List<java.lang.Object>

Du bindest irgendwo in deinem Programm eine falsche List ein.
Guck mal in den import Statements ganz oben in der .java Datei.

 

[DerSophist]

Du bindest irgendwo in deinem Programm eine falsche List ein.
Guck mal in den import Statements ganz oben in der .java Datei.

Danke... es funktioniert super! Das was ich wollte ...jetzt muss ich es nur noch komplett verstehen...

 

[httpdigest]

Von der Idee her ist es das, was @Tobias-nrw in #12 gepostet hat. Du hast ineinander verschachtelte Schleifen, und jede Schleife pickt sich das aktuelle Element heraus. Tiefere Schleifen picken sich dann nur noch den Rest rechts daneben heraus.
Nur die variable Schleifentiefe wird durch Rekursion abgebildet. Du kannst das auch ganz leicht mit echten for-Schleifen schreiben.

 

[Xyz1]

Du bindest irgendwo in deinem Programm eine falsche List ein.
Guck mal in den import Statements ganz oben in der .java Datei.

Ja und ich weiß auch welche, die von awt, weil vermutlich sein Compiler genau wie bei mir noch auf 1.5 eingestellt war.

 

[DerSophist]

Von der Idee her ist es das, was @Tobias-nrw in #12 gepostet hat. Du hast ineinander verschachtelte Schleifen, und jede Schleife pickt sich das aktuelle Element heraus. Tiefere Schleifen picken sich dann nur noch den Rest rechts daneben heraus.
Nur die variable Schleifentiefe wird durch Rekursion abgebildet. Du kannst das auch ganz leicht mit echten for-Schleifen schreiben.

Ok so in der Art war auch meine Grundidee... eine Frage noch: Wo muss ich was im Code verändern, damit die Methoden jetzt als Parameter eine Liste haben und man nicht immer die ganzen Farben eingeben muss?

 

[httpdigest]

Wo muss ich was im Code verändern, damit die Methoden jetzt als Parameter eine Liste haben und man nicht immer die ganzen Farben eingeben muss?

import static java.util.Collections.emptyList;
import static java.util.stream.Collectors.toList;
import static java.util.stream.IntStream.range;
import static java.util.stream.Stream.of;
import static java.util.stream.Stream.concat;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Stream;
public class Sets {
  public static <T> Stream<List<T>> permutationsOfSizeN(int n, List<T> elements) {
    return permutationsOfSizeN(n, 0, emptyList(), elements);
  }
  private static <T> Stream<List<T>> permutationsOfSizeN(int n, int i, List<T> acc, List<T> elements) {
    return n > 0
        ? range(i, elements.size()).boxed().flatMap(k -> 
            permutationsOfSizeN(n - 1, k + 1, 
                concat(acc.stream(), of(elements.get(k))).
                collect(toList()), elements))
        : Stream.of(acc);
  }
  /*
   * Beispiel:
   */
  public static void main(String[] args) {
    permutationsOfSizeN(2, Arrays.asList("Rot", "Grün", "Blau", "Braun"))
      .forEach(System.out::println);
  }
}

 

[Xyz1]

Hm vielleicht noch eine Anregung in den Raum, ich würd das nicht (prozedural-)rekursiv-funktional schreiben wollen ,sondern (prozedural-)rekursiv-iterativ, einfach, weil es dann lesbarer wäre...

import java.util.ArrayList;

/**
 * Hello world!
 */
public class App {
	public static ArrayList<ArrayList<String>> per(int i, int n, ArrayList<String> l, ArrayList<ArrayList<String>> acc,
			String... s) {
		if (n <= 0) {
			acc.add(new ArrayList<String>(l));
		} else {
			for (int j = i; j < s.length; j++) {
				l.add(s[j]);
				per(j + 1, n - 1, l, acc, s);
				l.remove(l.size() - 1);
			}
		}
		return acc;
	}

	public static void main(String[] args) {
		ArrayList<ArrayList<String>> list = per(0, 2, new ArrayList<String>(), new ArrayList<ArrayList<String>>(),
				"Rot", "Grün", "Blau", "Schwarz");
		for (ArrayList<String> l : list) {
			System.out.println(l);
		}
	}
}

Nicht wundern, bei 0, 3, würd es z. B. so sein:

[Rot, Grün, Blau]
[Rot, Grün, Schwarz]
[Rot, Blau, Schwarz]
[Grün, Blau, Schwarz]