Das i. Element einer "Kombination mit Wiederholung" finden

09/08/2008 - 10:58 von Ralf M. | Report spam
Hallo allerseits,

wie kann man das i. Element einer "Kombination mit Wiederholung" ermitteln?
Beispiel: Cw(n=4,k=5) = n_über_k (n+k-1, k) = 56 .
Es sind also insg. bV Elemente möglich.
Das z.B. 41. Element (hier 0-basierend) dieser Menge wàre { 1 1 2 2 2 }.
Gibt es eine allgemeingültige Methode um das i. Element
so einer Menge möglichst effizient zu ermitteln?

Schön wàre es wenn es auch die zugehörige Inverse-Funktion gàbe,
also von einem gegebenen Element der Menge die zugehörige
Elementnummer (d.h. den Index i) zu ermitteln. Für das obige Bespiel also
gehört zum Element { 1 1 2 2 2 } der Index 41 (hier 0-basierend).

(Die Basis kann auch ruhig 1-basierend sein; kein Problem.)

S.a.
http://de.wikipedia.org/wiki/Kombination_(Verbindung)
http://de.wikipedia.org/wiki/Kombinatorik
 

Lesen sie die antworten

#1 Wolfgang Thumser
10/08/2008 - 17:02 | Warnen spam
Hallo Ralf,

wie kann man das i. Element einer "Kombination mit Wiederholung" ermitteln?
Beispiel: Cw(n=4,k=5) = n_über_k (n+k-1, k) = 56 .



wegen dieser trivialen Identifikation Cw(n,k) = C(n+k-1, k) geht es eigentlich
nur um die effektive Ermittlung der i-ten k-elementigen Teilmenge einer
(n+k-1)-elementigen Menge in der lexikographischen Ordnung. Dieses Problem
hatten wir vor langer Zeit unter Message-ID:
diskutiert.

Gruss Wolfgang

Ähnliche fragen