Potenzmenge Ausgabe Java

30.04.2016, 14:28

hugobex78

Potenzmenge Ausgabe Java

Meine Frage:
Wie erstellt man einen rekursiven Algorithmus der alle Teilmengen (Potenzmengen) einer Menge ausgibt ?

Meine Ideen:
Hat jemand einen Beispiel für mich, wie man sowas erstellen könnte

30.04.2016, 14:37

Auf diesen Beitrag antworten »

eulerscheZahl

Ein recht einfacher Algorithmus:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:

import java.util.ArrayList;

public class Main
{
	public static void main(String[] args)
	{
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		function(new int[] { 1, 2, 3, 4, 5 }, 0, new ArrayList<Integer>(), result);
		for (ArrayList<Integer> list : result) {
			System.out.println(list.toString());
		}
	}

	public static void function(int[] numbers, int index, ArrayList<Integer> taken, ArrayList<ArrayList<Integer>> result) {
		if (index == numbers.length)
			result.add(taken);
		else {
			function(numbers, index + 1, taken, result); //do not take the current number
			ArrayList<Integer> copy = new ArrayList<>(taken);
			copy.add(numbers[index]);
			function(numbers, index + 1, copy, result); //take it
		}
	}
}

Du könntest auch einfach hochzählen und die Bits als 0 = nicht in der Menge und 1 = in der Menge interpretieren. Das erspart die Rekursion.

30.04.2016, 14:45

Auf diesen Beitrag antworten »

hugobex78

ich muss jedoch ein rekursiven Algorithmus mit einem boolean Arrays erstellen deshalb verwirrt mich dein code ein wenig ;/

30.04.2016, 14:48

Auf diesen Beitrag antworten »

eulerscheZahl

Meinst du sowas?

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

import java.util.Arrays;

public class Main
{
	public static void main(String[] args)
	{
		function(0, new boolean[5]);
	}

	public static void function(int index, boolean[] taken) {
		if (index == taken.length) {
			System.out.println(Arrays.toString(taken));
		}
		else {
			function(index + 1, taken); //do not take the current number
			taken[index] = true;
			function(index + 1, taken); //take it
			taken[index] = false;
		}
	}
}

30.04.2016, 15:05

Auf diesen Beitrag antworten »

hubobex78

ich weiß nicht wo mein Fehler ist in meinem code, irgendwie klappt das nicht :/

30.04.2016, 15:07

Auf diesen Beitrag antworten »

eulerscheZahl

Du könntest mir deinen Code zeigen. Das würde eine bessere Antwort ermöglichen.

30.04.2016, 15:22

Auf diesen Beitrag antworten »

hubobex78

public static void teilmengen(int[] menge, boolean[]enthalten, int k, int n) {
if (menge == enthalten.length) {
System.out.println(Arrays.sort(enthalten));}

else {
teilmengen(menge + 1, enthalten, k, n);
enthalten[menge] = true;
teilmengen(menge + 1, enthalten, k, n);
enthalten[menge] = false;
}

30.04.2016, 15:29

Auf diesen Beitrag antworten »

eulerscheZahl

Deine Datentypen sind teilweise falsch. Außerdem solltest du mit Index 0 beginnen, statt mit 1.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:

public class Main {
	public static void teilmengen(int[] menge, boolean[] enthalten, int k, int n) {
		if (k == enthalten.length) {
			for (int i = 0; i < enthalten.length; i++)
				if (enthalten[i])
					System.out.print(menge[i] + " ");
			System.out.println();
		}
		else {
			teilmengen(menge, enthalten, k + 1, n);
			enthalten[k] = true;
			teilmengen(menge, enthalten, k + 1, n);
			enthalten[k] = false;
		}
	}

	public static void main(String[] args) {
		int[] mengeA = { -1, 1, 2, 3, 4 };
		boolean[] enthaltenA = new boolean[5];
		teilmengen(mengeA, enthaltenA, 0, 4);
	}
}

Neue Frage »

Antworten »

Potenzmenge Ausgabe Java

Verwandte Themen