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

DerSophist

Mitglied
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)
 
Das Thema hatten wir eigentlich hier schon einmal:

So geht es iterativ
Java:
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);
		}
	}
}
 
Das Thema hatten wir eigentlich hier schon einmal:

So geht es iterativ
Java:
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...
 
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:
Java:
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.
 
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:
Java:
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?
 
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:
Java:
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);
		}
	}
}
 
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:
Java:
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?
 
Hier ist ein Beispiel, wenn `n` (in deinem Fall = 2) variabel sein soll:
Java:
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.
 
Hier ist ein Beispiel, wenn `n` (in deinem Fall = 2) variabel sein soll:
Java:
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:
Error🙁98, 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>
 
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.
 
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?
 
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?
Java:
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);
  }
}
 
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...
Java:
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:
Code:
[Rot, Grün, Blau]
[Rot, Grün, Schwarz]
[Rot, Blau, Schwarz]
[Grün, Blau, Schwarz]
 

Neue Themen


Zurück
Oben