Möglichkeiten, unter vernachläßigung der Reihenfolge

[TGM]

Hi, ich bin letztens bei einer optimierungsaufgabe über folgendes Problem gestolpert:
Ich habe eine zahlenmenge mit den Ganzenzahlen von 1 bis n. Nun möchte ich alle möglichen Kombinaionen dieser Zahlen unter vernachläßigung der Reihenfolge und mit 1-n stellen finden. Dabei dürfen die Zahlen in eine Kombination nicht mehrmals auftauchen. Das heißt bei z.B. der Menge 1-4

1
2
3
4
12
 23
  34
1 3
1  4
 2 4
123 
 234
1234

dabei fällt auf, das: jede Zahl gleich oft vorkommt,

und wenn man es umschreibt nach:

1
12
13
14
123 
1234
2
23
24
234
3
34
4

fällt eine deutliche symetrie auf. so weit ist es mir auch schon gelungen die vorkommnise jeder Zahl auszurechnen, aber worum es mir schlußendlich geht, ist das ich aus einer Zahl M und der anzahl stellen N die entsprechende Kombination finde. Beispiel:

M=6
N=3
1     |M1
12    |M2
13    |M3
14    |M4
123   |M5
1234  |M6
2     |M7 
23    |M8
24    |M9
234   |M10
3     |M12
34    |M13
4     |M14

Daher die gesuchte Kombination ist gleich 1234. Weiß jemand, wonach ich da suchen muss, oder kann mir nen Tipp geben wie man das am besten regelt...
greetz
TGM

[asmodis]

Mir scheint, du hast in deinem Beispiel ein paar Kombinationen vergessen (etwa 124). Und was soll M und N sein?

[MamboKurt]

ich weiß nicht, ob es dir aufgefallen ist, aber du hast bei deiner aufzählung drei mengen vergessen:
1. leere menge, je nachdem, ob du sie dabeihaben willst, oder nicht
2. 134
3. 124

man kann die anzahl aller möglichen teilmengen schnell berechnen:
|M| = n => |P(M)| = 2^n
P(M) ist die Potenzmenge, also die menge aller teilmengen.

das mit der 2er-potenz kommt daher, dass ein elemnt entweder vorkommen kann oder nicht.

wenn du konkret alle teilmengen erzeugen willst ergibt sich ein ganz kanonischer weg:
man kann jedes element der potenzmenge mit einer zahl zwischen 0 und 2^n identlifizieren:
man wähle eine reihenfolge:
1 2 3 4
sagt man 1 ":=" 1, 2 ":=" 2 (10_B), 3 ":=" 4 (100_B), 4 ":=" 8 (1000_B)

also kann man sagen: 10 = 1010_B ":=" {4, 2}

siehe hier:
http://www.c-plusplus.net/forum/viewtopic-var-t-is-156391

[TGM]

oh..thx
Greetz