Potenzmenge Ausgabe Java |
hugobex78 unregistriert
|
|
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:28 |
|
|
|
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.
__________________ Syntax Highlighting fürs Board (Link)
|
|
30.04.2016 14:37 |
|
|
hugobex78 unregistriert
|
|
ich muss jedoch ein rekursiven Algorithmus mit einem boolean Arrays erstellen deshalb verwirrt mich dein code ein wenig ;/
|
|
30.04.2016 14:45 |
|
|
hubobex78 unregistriert
|
|
ich weiß nicht wo mein Fehler ist in meinem code, irgendwie klappt das nicht :/
|
|
30.04.2016 15:05 |
|
|
hubobex78
Grünschnabel
Dabei seit: 30.04.2016
Beiträge: 1
|
|
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;
}
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von hubobex78: 30.04.2016 15:31.
|
|
30.04.2016 15:22 |
|
|
|
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);
}
} |
|
__________________ Syntax Highlighting fürs Board (Link)
|
|
30.04.2016 15:29 |
|
|
|