Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten

Neue Frage »

nils2012 Auf diesen Beitrag antworten »
Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Meine Frage:
Hallo allerseits,

ich bin auf der Suche nach der Formel zur Bestimmung der Anzahl der Permutationen im folgendem Fall:

Ziehen von k Elementen aus einer Menge mit n Elementen,
wobei n_1 Elemente vom Typ1, n_2 Elemente vom Typ2, ... und n_k Elemente vom Typk sind und n = n_1 + n_2 + ... + n_k gilt.

Kann mir irgendeiner weiterhelfen?

Vielen Dank!
Nils

Meine Ideen:
Mein Ansatz ohne Abhängigkeit von k lautet:

P_n = n!/ (n_1!*...*n_k!)

Mein Ansatz in Abhängigkeit von k ist folgender:
P_n = P_n/ (n-k)! <-- Das ist aber falsch, oder?
Mystic Auf diesen Beitrag antworten »
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Zitat:
Original von nils2012
Meine Ideen:
Mein Ansatz ohne Abhängigkeit von k lautet:

P_n = n!/ (n_1!*...*n_k!)

Das wäre die Antwort auf die Frage, wieviele Möglichkeiten es gibt, n Elemente zu ziehen, wenn zwischen Elementen des gleichen Typs nicht unterschieden wird... War hier nur leider nicht gefragt... unglücklich

Zitat:
Original von nils2012
Mein Ansatz in Abhängigkeit von k ist folgender:
P_n = P_n/ (n-k)! <-- Das ist aber falsch, oder?

Das ist überhaupt totaler Unsinn, denn hier kann man ja durch P_n dann kürzen und erhält dann die (jetzt nicht besonders sinnvolle! ) Gleichung

(n-k)!=1

woraus k=n oder k=n-1 folgt...
nils2012 Auf diesen Beitrag antworten »
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Mein Ansatz in Abhängigkeit von k ist folgender:

P_n = (n!/ (n_1!*...*n_k!))/ (n-k)!
Mystic Auf diesen Beitrag antworten »
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Zitat:
Original von nils2012
Mein Ansatz in Abhängigkeit von k ist folgender:

P_n = (n!/ (n_1!*...*n_k!))/ (n-k)!

Damit kann leider auch nichts anfangen... Deine Formel liefert ja für



nicht einmal eine ganze Zahl...

Wieviele Möglichkeiten gibt es denn für die k gezogenen Elemente, was jetzt nur einmal ihren Typ betrifft?
nils2012 Auf diesen Beitrag antworten »
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Ok entschuldige,

habe gerade noch etwas entdeckt.

P_n = (n!/ (n_1!*...*n_j!))/ (n-k)!


Bsp:
n = 5
j = 3 (also 3 verschiedene Typen von Objekten)
n_1 = 1
n_2 = 2
n_3 = 2

k = 2

P_n = 5!/(2!*2!*1!)/(5-2)! = 5

Es müssten aber in diesem Beispiel P_n = 10 sein.
Mystic Auf diesen Beitrag antworten »
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Zitat:
Original von nils2012
Ok entschuldige,

habe gerade noch etwas entdeckt.

P_n = (n!/ (n_1!*...*n_j!))/ (n-k)!


Hm, was genau hast du entdeckt? Dass vielleicht deine Angabe

Zitat:
Original von nils2012
Meine Frage:
Ziehen von k Elementen aus einer Menge mit n Elementen,
wobei n_1 Elemente vom Typ1, n_2 Elemente vom Typ2, ... und n_k Elemente vom Typk sind und n = n_1 + n_2 + ... + n_k gilt.

falsch ist? Denn da kommt kein j darin vor... verwirrt Außerdem funktioniert mein Gegenbeispiel (mit k=j) ja noch immer... unglücklich
 
 
nils2012 Auf diesen Beitrag antworten »
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Ziehen von k Elementen aus einer Menge mit n Elementen,
wobei n_1 Elemente vom Typ1, n_2 Elemente vom Typ2, ... und n_j Elemente vom Typj sind und n = n_1 + n_2 + ... + n_j gilt.

P_n = (n!/ (n_1!*...*n_j!))/ (n-k)!

Bsp:
n = 5
j = 3 (also 3 verschiedene Typen von Objekten)
n_1 = 1
n_2 = 2
n_3 = 2

k = 2

P_n = 5!/(2!*2!*1!)/(5-2)! = 5

Wo liegt der Fehler?

Es müssten aber in diesem Beispiel P_n = 10 sein.
Mystic Auf diesen Beitrag antworten »
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Zitat:
Original von nils2012
Bsp:
n = 5
j = 3 (also 3 verschiedene Typen von Objekten)
n_1 = 1
n_2 = 2
n_3 = 2

k = 2

P_n = 5!/(2!*2!*1!)/(5-2)! = 5

Wo liegt der Fehler?

Es müssten aber in diesem Beispiel P_n = 10 sein.


Ich versteh immer nur Bahnhof... unglücklich

Du hast doch hier 3 Typen, nenen wir sie x, y und z und "langst" zweimal zu, wobei du dich beim Typen x nur einmal "bedienen" darfst... Es geht also hier darum, dass Polynom auszumultiplizieren und alle Ausdrücke abzuzählen (d.h., deren Koeffizienten aufzusummieren), welche den Faktor nicht enthalten... Da komm ich aber nicht auf 10...
nils2012 Auf diesen Beitrag antworten »
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Ok,
ich habe eine Menge n (n=5) in einer Urne besipielsweise und ziehe k (k=2) Mal.
Angenommen ich habe die Elemente A, B und C und im Beispielfall n={A,B,B,C,C} Elemente in der Urne.

Ziehe ich jetzt zwei mal bekomme ich maximal folgende Kombinationen:

P(n) = {AB,AC,BA,BB,BC,CA,CB,CC}

Und genau hierfür suche ich eine allgemeingültige Formel zur Beschreibung der Anzahl möglicher Permutationen.
Mystic Auf diesen Beitrag antworten »
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Zitat:
Original von nils2012
Ok,
ich habe eine Menge n (n=5) in einer Urne besipielsweise und ziehe k (k=2) Mal.
Angenommen ich habe die Elemente A, B und C und im Beispielfall n={A,B,B,C,C} Elemente in der Urne.

Ziehe ich jetzt zwei mal bekomme ich maximal folgende Kombinationen:

P(n) = {AB,AC,BA,BB,BC,CA,CB,CC}

Und genau hierfür suche ich eine allgemeingültige Formel zur Beschreibung der Anzahl möglicher Permutationen.

Hm, warum wiederholst du nochmals, aber mit deinen Worten, was ich oben schon gesagt habe? Wenn man mein Polynom ausmultipliziert, bekommt man doch



wobei hier das Monom "nicht erlaubt" ist... Du musst also dann in das Polynom



nur einsetzen, um für dein Beispiel auf die Anzahl der Möglichkeiten zu kommen...
nils2012 Auf diesen Beitrag antworten »
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
ok, und wie setze ich das zu einer allgemein Formel zusammen und ?
HAL 9000 Auf diesen Beitrag antworten »
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Das scheint unglaublich schwer in einer geschlossenen Formel erfassbar zu sein.


Im Fall, dass nur die Auswahlen ohne Berücksichtigung der Reihenfolge interessieren, d.h. hier etwa

{AB,AC,BB,BC,CC}

findet man noch ein halbwegs brauchbares Siebformel-Ungetüm. Aber hier, mit Berücksichtigung der Reihenfolge ... verwirrt
Mystic Auf diesen Beitrag antworten »
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Zitat:
Original von HAL 9000
Das scheint unglaublich schwer in einer geschlossenen Formel erfassbar zu sein.


Im Fall, dass nur die Auswahlen ohne Berücksichtigung der Reihenfolge interessieren, d.h. hier etwa

{AB,AC,BB,BC,CC}

findet man noch ein halbwegs brauchbares Siebformel-Ungetüm. Aber hier, mit Berücksichtigung der Reihenfolge ... verwirrt

Ja, tatsächlich habe ich nach näherer Betrachtung der Aufgabe auch sofort an dich und deine Vorliebe für die "Siebformel" gedacht... Augenzwinkern

Ich habe allerdings schwer den Verdacht, dass der Threadersteller eine (oder mehrere ) konkrete Aufgaben dieser Art lösen sollte, und glaubte, besonders schlau zu sein, wenn er die Aufgabe gleich allgemein stellt, wodurch sie dann viel zu schwer bzw. unlösbar wird... geschockt
nils2012 Auf diesen Beitrag antworten »
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Ich benötige schon eine allgemeine Aussage, ansonsten hätte ich hier keine Frage formuliert.

Für k = n kann ich ja folgende allgemeine Formel für die Anzahl der Permutaionen definieren:

P(n) = (n_1+n_2+...*n_j)! / n_1! * n_2! * ... * n_j!

Weiterhin müsste ich "nur" noch die Abhängigkeit von k mit in den Nenner hineinbringen.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von nils2012
Weiterhin müsste ich "nur" noch die Abhängigkeit von k mit in den Nenner hineinbringen.

Das stellst du dir so vor, dass das so einfach gehen könnte. Ist es aber nicht. unglücklich
Mystic Auf diesen Beitrag antworten »
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Zitat:
Original von nils2012
Ich benötige schon eine allgemeine Aussage, ansonsten hätte ich hier keine Frage formuliert.

Für k = n kann ich ja folgende allgemeine Formel für die Anzahl der Permutaionen definieren:

P(n) = (n_1+n_2+...*n_j)! / n_1! * n_2! * ... * n_j!

Weiterhin müsste ich "nur" noch die Abhängigkeit von k mit in den Nenner hineinbringen.


"Nur" ist gut, denn der Fall k=n ist ein trivialer Sonderfall, der nichts über die Schwierigkeit des eigentlichen Problems aussagt... Ich bleibe dabei: Es handelt sich dabei um ein von dir selbst gestelltes Problem, im naiven Glauben, dass eine einfache Verallgemeinerung des obigen Spezialfalls leicht möglich sein müsste... "Instanzen" dieses Problems, also mit konkreten Zahlenangaben, sollten jedoch im Gegensatz dazu kein Problem darstellen..

PS: Crossposting ist hier übrigens gar nicht gern gesehen...
HAL 9000 Auf diesen Beitrag antworten »

Nehmen wir den Fall . Da gibt es dann

AB , AC , BA , BC , CA , CB , CC

also genau 7 Varianten. Wie bitte soll die Anzahl 7 bei Division von durch irgendwas Ganzzahliges entstehen? Oder überhaupt bei der Division von durch eine ganze Zahl?

Dieses einfache Beispiel zeigt also schon, dass es absurd ist, an eine Formel derart einfacher Struktur zu glauben.


P.S.: Hier mal noch die angedachte Anzahlformel für den Fall von ungeordneten Auswahlen (d.h. ohne Berücksichtigung der Auswahlreihenfolge):



Das ist als Indikator zu verstehen (=1 wenn die Bedingung erfüllt ist; =0 sonst).



Zitat:
Original von Mystic
PS: Crossposting ist hier übrigens gar nicht gern gesehen...

Soll er es doch versuchen, dann wird er sehen, dass dort auch nur mit Wasser gekocht wird. Augenzwinkern
nils2012 Auf diesen Beitrag antworten »
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Ok ein praktischer Fall wäre:

n = 150
j = 25
k=40

n_1 =2
n_2 =9
n_3 =5
n_4 =4
n_5 =9
n_6 =10
n_7 =8
n_8 =5
n_9 =5
n_10 =4
n_11 =5
n_12 =8
n_13 =10
n_14 =8
n_15 =5
n_16 =2
n_17 = 9
n_18 = 5
n_19 = 2
n_20 = 8
n_21 = 9
n_22 = 4
n_23 = 5
n_24 = 4
n_25 = 5

Da ich das nicht ausrechnen möchte, war ich auf der Suche nach einer Verallgemeinerung.

Es ist schon unglaublich wie schnell hier die Leute ausfallend werden...
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von nils2012
Es ist schon unglaublich wie schnell hier die Leute ausfallend werden...

verwirrt
nils2012 Auf diesen Beitrag antworten »
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Zitat:
Original von Mystic
PS: Crossposting ist hier übrigens gar nicht gern gesehen...


Die Frage hatte ich vor der ersten Antwort hier gestellt in der Hoffnung, dass mir irgendwer weiterhelfen kann.

Zitat:
Original von Mystic
Ich habe allerdings schwer den Verdacht, dass der Threadersteller eine (oder mehrere ) konkrete Aufgaben dieser Art lösen sollte, und glaubte, besonders schlau zu sein, wenn er die Aufgabe gleich allgemein stellt, wodurch sie dann viel zu schwer bzw. unlösbar wird...


Eine einfache Antwort, dass es zu komplex und nicht leicht lösbar ist hätte mir auch gereicht...

Trotzdem danke.
Mystic Auf diesen Beitrag antworten »
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Zitat:
Original von nils2012
Zitat:
Original von Mystic
Ich habe allerdings schwer den Verdacht, dass der Threadersteller eine (oder mehrere ) konkrete Aufgaben dieser Art lösen sollte, und glaubte, besonders schlau zu sein, wenn er die Aufgabe gleich allgemein stellt, wodurch sie dann viel zu schwer bzw. unlösbar wird...


Eine einfache Antwort, dass es zu komplex und nicht leicht lösbar ist hätte mir auch gereicht...

Ich hätte das jetzt noch nicht als "ausfallend" eingestuft, aber wenn das so rüberkam, entschuldige ich mich dafür...

Was dein Beispiel betrifft, ist mir das echt auch zu krass... Aber ich denke, dass ich möglicherweise sowas wie eine Formel gefunden habe, die ich an folgenden einfacheren Beispiel demonstrieren möchte:



Mein Polynom schaut dafür so aus:





und man muss wieder nur einsetzen, um auf die gesuchte Anzahl zu kommen...

Das Ganze kommt mir jetzt fast ein bißchen zu einfach vor, daher hoffe ich, ich habe mich da nirgends "vergaloppiert"... verwirrt
HAL 9000 Auf diesen Beitrag antworten »

Ich hab meine Zweifel, dass das stimmt:

In deinen Polynomen sind ja so siebformelähnliche Strukturen erkennbar:

steht für alle 10er-Tupel ohne Anzahlbeschränkung bei den vier Typen.

Wofür aber steht etwa ?

Meines Erachtens nur für dreimal Element 1 an den ersten drei (oder drei anderen vorab festgelegten (!)) Positionen, und die anderen sieben Positionen sind wieder freigegeben.

Das ist aber nicht ganz das, was wir hier wollen, oder? Wir wollen hier doch mindestens dreimal Element 1, ohne Festlegung der Positionen... verwirrt
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Wofür aber steht etwa ?

Meines Erachtens nur für dreimal Element 1 an den ersten drei (oder drei anderen vorab festgelegten (!)) Positionen, und die anderen sieben Positionen sind wieder freigegeben.

Das ist aber nicht ganz das, was wir hier wollen, oder? Wir wollen hier doch mindestens dreimal Element 1, ohne Festlegung der Positionen... verwirrt

Ja, ist mir eben auch aufgefallen... Da muss natürlich jeweils ein Koeffizient hin, der die Anzahl der Möglichkeiten für die jeweilige Auswahl beschreibt... Das würde also dann





ergeben, wenn ich mich nicht schon wieder geirrt habe... verwirrt
HAL 9000 Auf diesen Beitrag antworten »

Nein, jetzt zählst du wieder einige Tupel mehrfach - es ist m.E. so nicht zu retten.


Nehmen wir mal den Fall von neunmal Element 1 und einmal Element 2.

In deinem Polynom steht dafür der Anteil , es müssten doch aber sein, oder irre ich mich da? Das jetzt mit zu multiplizieren, bringt es auch nicht.


Die Sache ist teuflisch, das hatte ich oben versucht anzudeuten. Teufel


EDIT: M.E. bleibt dir nur, Tippel-Tappel-Tour alle möglichen Anzahlen von Element 1 da einzeln durchzugehen, also



bzw. was sich dann eher lohnen würde



Das wäre also nur die Korrektur zu deinem Term - die Sache wächst zu einem wahren Monstrum.
Mystic Auf diesen Beitrag antworten »

Ja, ich fürchte, ich habe da jetzt wohl selber gemacht, was ich den Fragestellern hier oft vorwerfe, nämlich "aus der Hüfte zu schiessen"... unglücklich

Was du sagst stimmt natürlich, für einen Moment dachte ich, es sei doch nicht ganz so kompliziert... Aber das ist es wirklich, was damit wohl hinlänglich bewiesen ist... Augenzwinkern

Edit: Immerhin sollte die Idee dahinter noch für eine einfache Berechnung mittels eines CAS nutzbar sein... Jedenfalls habe ich den Term

code:
1:
2:
3:
subs(x1=1,x2=1,x3=1,x4=1,rem(rem(rem(rem((x1+x2+x3+x4)^10,x1^3,x1),x2^10,x2),x3^6,x3),x4^5,x4));


in Maple15 eingegeben und es hat daraufhin die Zahl 465387 ausgespuckt...
HAL 9000 Auf diesen Beitrag antworten »

Nochmal zu der Anzahl oben, die kann man nämlich auch so interpretieren: Es gibt insgesamt



-Tupel ganzer Zahlen mit der Eigenschaft für sowie .

Jedem dieser -Tupel entspricht nun eine ungeordnete, sowie geordnete Elementfolgen. D.h., du müsstest über alle dieser -Tupel den Wert summieren, um auf die gewünschte Anzahl zu kommen. Für

Zitat:
Original von nils2012
n = 150
j = 25
k=40

n_1 =2
n_2 =9
n_3 =5
n_4 =4
n_5 =9
n_6 =10
n_7 =8
n_8 =5
n_9 =5
n_10 =4
n_11 =5
n_12 =8
n_13 =10
n_14 =8
n_15 =5
n_16 =2
n_17 =9
n_18 =5
n_19 =2
n_20 =8
n_21 =9
n_22 =4
n_23 =5
n_24 =4
n_25 =5

ist



die Anzahl der Fälle, über die da summiert werden müsste. Auch unter Einbeziehung einiger Symmetrien und daraus folgender Zusammenfassungen bleibt immer noch ein ganz ordentlicher Hammer, das möchte ich meinem PC nicht zumuten, solange hält der (und sicher auch ich) nicht durch. Big Laugh
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
[...]
ist



die Anzahl der Fälle, über die da summiert werden müsste. Auch unter Einbeziehung einiger Symmetrien und daraus folgender Zusammenfassungen bleibt immer noch ein ganz ordentlicher Hammer, das möchte ich meinem PC nicht zumuten, solange hält der (und sicher auch ich) nicht durch. Big Laugh

Ja, allerdings habe ich inzwischen einen anderen Weg für die Berechnung mittels einem CAS gefunden, den ich oben für "mein" Beispiel hineineditiert habe... Wenn diese Ergebnis stimmt (was mittels brute force noch überprüfbar sein sollte), dann ich sehe ich auch für die Originalaufgabe des Threaderstellers eine Chance... Augenzwinkern
HAL 9000 Auf diesen Beitrag antworten »

Diesmal zweifle ich nicht die Formel an, sondern dass das bei dem Datensatz in erträglicher Zeit machbar ist. Augenzwinkern

Zitat:
Original von Mystic
es hat daraufhin die Zahl 465387 ausgespuckt...

Den Wert kann ich mittels MuPAD-Skript

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
s:=0 : k:= 10 :
for k1 from 0 to 2 do
  for k2 from 0 to 9 do
    for k3 from 0 to 5 do
      k4:=k-k1-k2-k3;
      if ((k4>=0) and (k4<=4))
        s:=s+k!/(k1!*k2!*k3!*k4!):
      end_if;
    end_for;
  end_for;
end_for;
s
bestätigen.
nils2012 Auf diesen Beitrag antworten »

Hallo,

vielen Dank für all Eure Mühen. Ich denke, dass ich mit diesen Ansätzen etwas anfangen kann.
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Diesmal zweifle ich nicht die Formel an, sondern dass das bei dem Datensatz in erträglicher Zeit machbar ist. Augenzwinkern

Damit hast du leider recht... Ich habe inzwischen aus dem Maple-Program noch alles rausgeholt, was meiner Meinung nach drinnen war, und es schaut nun so aus

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
comb:=proc(k:=10,b:=[2,9,5,4])     
  local isvalid,k_:=k,r:=1,s,t,v;
  v:=[seq(x[i],i=1..nops(b))];
  s:=add(v_,v_ in v);
  t:=mul(x[i]^b[i],i=1..nops(b));
  isvalid:=proc(t_) divide(t,t_) end;
  while k_>0 do
      if type(k_,odd) then
         r:=expand(r*s);
         r:=add(r_,r_ in select(isvalid,[op(r)]));
      end if;
      s:=expand(s*s);
      s:=add(s_,s_ in select(isvalid,[op(s)]));
      k_:=floor(k_/2);
   end do;
   return subs([seq(x[i]=1,i=1..nops(b))],r) 
end: 

t:=time():comb();time()-t;                              
465387                              
0.016

Im wesentlichen ist es also wieder einmal der "Square and Multiply"-Algorithmus, wobei es nur darum geht, die Potenz



zu bilden und dabei schon zwischendurch immer alle (in Hinblick auf die vorgegebenen Restriktionen) "unzulässigen" Monome zu entfernen... Es liefert dann auch tatsächlich für "mein" Beispiel wieder das korrekte Ergebnis (danke übrigens für dessen Überprüfung! Freude ), stürzt dann aber leider bei der eigentlichen Aufgabe auf meinem PC wegen Speicherüberlaufs ab... unglücklich

Zitat:
Original von nils2012
vielen Dank für all Eure Mühen. Ich denke, dass ich mit diesen Ansätzen etwas anfangen kann.

Ja, ich denke, mehr als diese Lösungsansätze ist da wirklich nicht drinnen, insbesondere keine wirklich befriedigende Formel ... unglücklich

Es ist aber im Prinzip nicht schwer, das für einen konkreten Fall auch wirklich auszurechnen, da bleib ich dabei, aber dein Beispiel ist dafür einfach zu "groß"... Augenzwinkern
HAL 9000 Auf diesen Beitrag antworten »

Dann mal noch die langsame MuPAD-Variante - ich bevorzuge ja eigentlich C/C++, hatte jetzt aber keine Lust, mich um eine BigInteger-Bibliothek zu kümmern:

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:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
k:=20;
_n:=matrix([2,9,5,4,9,10,8]);
j:=linalg::vecdim(_n):
_k:=array(1..j) :
_c:=array(0..j-1) :
_c[0]:=k! :
for i from 1 to j-1 do
  _k[i] := 0 :
  _c[i] := _c[i-1] :
end_for :
si:=-1 :
i:=j :
anzahl:=0 :
while (i>=1) do
  if (i>=j) then
    si:=si+1 :
    _k[j]:=k-si :
    if (_k[j]<=_n[j]) then
      anzahl:=anzahl+_c[j-1]/_k[j]! :
    end_if :
    i:=i-1 :
  else
    _k[i]:=_k[i]+1 :
    si:=si+1 :
    if ((_k[i]>_n[i]) or (si>k)) then
      si:=si-_k[i] :
      i:=i-1 :
    else
      _c[i]:=_c[i-1]/_k[i]! :
      i:=i+1 :
      _k[i]:=-1 :
      si:=si-1 :
    end_if :
  end_if :
end_while :
anzahl;
Ergebnis:

Berechnungsdauer ca. 6 Sekunden, aber das Beispiel ist ja auch etwas größer. Augenzwinkern
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
anzahl;[/code]Ergebnis:

Berechnungsdauer ca. 6 Sekunden, aber das Beispiel ist ja auch etwas größer. Augenzwinkern

Ja, das bekomm ich auch heraus, allerdings erst nach 89.7s... Wenngleich ich mich jetzt nicht vorrangig um Aspekte der Rechengeschwindigkeit gekümmert habe, sondern es mir mehr darum ging, meinen hier skizzierten Lösungsweg möglichst genau umzusetzen, so ist die Performance deines Programms schon recht beeindruckend... Freude
HAL 9000 Auf diesen Beitrag antworten »

Egal ob 6 oder 89 Sekunden - man kann sich jetzt schon vorstellen was passiert, wenn man die Algorithmen auf den vollen 25-dimensionalen Anzahlvektor loslässt. Speicherplatzprobleme hab ich da zwar nicht, aber ... das hatte ich ja oben schon gesagt: Zu wenig Lebenszeit. Big Laugh
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Egal ob 6 oder 89 Sekunden - man kann sich jetzt schon vorstellen was passiert, wenn man die Algorithmen auf den vollen 25-dimensionalen Anzahlvektor loslässt. Speicherplatzprobleme hab ich da zwar nicht, aber ... das hatte ich ja oben schon gesagt: Zu wenig Lebenszeit. Big Laugh

Leider ist - aus meiner Sicht - der Unterschied noch viel dramatischer... Ich habe jetzt dein Programm in den Maple Editor hinüberkopiert und da und dort ein bißchen adaptiert:

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:
25:
26:
27:
28:
29:
30:
31:
32:
combhal:=proc(k:=20,_n:=[2,9,5,4,9,10,8])
   local j:=nops(_n),_k:=Array(1..j),_c:=Array(0..j-1,[k!$j]),
         si:=-1, i:=j, anzahl:=0:
   while i>=1 do
      if i>=j then
        si:=si+1 :
        _k[j]:=k-si :
        if _k[j]<=_n[j] then 
           anzahl:=anzahl+_c[j-1]/_k[j]! 
        end if :
        i:=i-1 :
     else
       _k[i]:=_k[i]+1 :
       si:=si+1 :
       if _k[i]>_n[i] or si>k then
         si:=si-_k[i] :
         i:=i-1 :
       else         
         _c[i]:=_c[i-1]/_k[i]! :
          i:=i+1 :
          _k[i]:=-1 :
          si:=si-1 :
       end if :
     end if :   
  end do :   
  return anzahl 
end: 

t:=time():combhal();time()-t;
                        26124098594851972
                              0.655

Und siehe da, es läuft auf meinem Rechner sogar 10 mal so schnell, d.h., dein Algorithmus ist für dieses Beispiel mehr als 100 mal schneller... verwirrt
HAL 9000 Auf diesen Beitrag antworten »

Wahrscheinlich hat dein Maple deutlich effizientere Routinen bei der Berechnung großer Integerzahlen - na egal. Augenzwinkern


Nachtrag: Die C-Variante unter Nutzung der GMP (Sektion "Integer Functions") schlägt sich mit Berechnungszeit <20 ms erwartungsgemäß gut bei obigem Beispiel.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »