# Alle Möglichen Kombinationen eines Arrays



## Carnivean (18. Nov 2007)

Hi,

ich möchte folgendes programmieren.

Ich habe ein Array mit n Elementen. Nun möchte ich alle Teilmengen ausgeben, sprich die Potenzmenge der Elemente des Arrays bilden.

Beispiel zur Veranschaulichung.

Habe ich im Array die Elemente: {1, 2, 3, 4}
So soll der Algorithmus folgendes urückgeben: { {1}, {2}, {3}, {4}, {1,2},{1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1,2,3},{1,3,4},{2,3,4},{1,2,4} }

Wie kann man sowas realisieren?

Ich hab gedacht ich spalte zuerst das problem auf, indem ich zuerst alle Teilmengen bestimme, die k Elemte haben, dann gibt es dafür n über k Möglichkeiten, nur wie kann ich die bei beliebigen n ausgeben :/.

Bin über jegliche Hilfestellung / Links zu Seiten, woe ein solcher Algorithmus beschrieben ist dankbar.


----------



## JPKI (18. Nov 2007)

Zunächst wäre es sicher hilfreich zu wissen, in welcher Form du die Daten zurückhaben willst (z.B. in einer List, in einem mehrdimensionalen Array, als String, etc...).


----------



## Carnivean (18. Nov 2007)

In irgendeinem Array, oder einer Liste, ist eigentlich egal, ich werd danach eh noch nen bissl mit ihnen rumspielen müssen ^^


----------



## Gast (18. Nov 2007)

Also ein Anfang wäre doch, falls es ein Array sein soll das ergebnisarry mit 2^n zu initiialisieren und bei einer n-Elementigen Menge die ersten n+1 Elemente mit den Einelementigen zu füllen


----------



## Marco13 (19. Nov 2007)

Das ist mal wieder so ein Fall, wo man eigentlich nur _zählt_

{ 1 2 3 }, 3 Elemente

Zählen binär von 0 bis 2^3
000
001
010
011
...
111

Das entspricht dann den Teilmengen 
{}
{3}
{2}
{23}
...
{123}

Dafür gibt's sicher einige sehr geschickte Algorithmen, aber im Prinzip machen sie alle das gleiche....


----------



## louis (19. Nov 2007)

Hi,

kleiner Tip: Potenzmenge auf englisch heisst "power set" 

Damit googeln liefert z.B.


jvalentino.blogspot.com/2007/02/shortcut-to-calculating-power-set-using.html

mfg louis


----------

