Beliebige Anzahl geschachtelter while-Schleife

WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Partner:

Forum

Option

[Erweitert]

• Diese Seite per Mail weiterempfehlen

Gehe zu:

deepblue

Forum-Newbie


	Beiträge: 2

	Anmeldedatum: 21.12.18

	Wohnort: ---

	Version: 2016

Verfasst am: 21.12.2018, 16:10 Titel: Beliebige Anzahl geschachtelter while-Schleife

Hallo zusammen,

ich habe ein Problem bei der Programmierung einer Funktion, die alle Permutationen von Zahlen (mit Wiederholungen, [0 1] ist für mich nicht gleich [1 0]) erzeugt, die eine bestimmte Bedingung erfüllen. Konkret geht es darum, dass ich z.B. alle Permutationen der Zahlen 0 bis 2 auf 3 Plätzen haben möchte, die ein bestimmtes Kriterium (siehe Beispielcode unten) erfüllen. Also:

0 0 0
1 0 0
2 0 0
0 1 0
1 1 0
2 1 0
0 2 0
1 2 0
2 2 0
0 0 1
usw.

Das lässt sich prinzipiell mit der Funktion permn (https://de.mathworks.com/matlabcent.....exchange/7147-permn-v-n-k) und anschließendem aussortieren lösen, bei (mit realistischen 36 Plätzen und den Zahlen 0 bis 8 ) 36^9 Möglichkeiten reicht dafür der Speicher aber nicht aus. Durch die Bedingung werden aber sowieso die allermeisten Kombinationen herausgefiltert (es bleiben maximal einige 1000 übrig), weshalb ich versucht habe, dieses Problem anders anzugehen.

Ich habe einen funktionierenden, aber sehr umständlichen Code mit ineinandergeschachtelten While-Schleifen erzeugen können, hier ein Beispiel für alle Permutationen unter meiner Bedingung auf 5 Plätzen (Die Ausführung dauert nur wenige ms):

Code:

nu = [29 35 40 45 55];
Emax = 200;

N=length(nu);
erg = [];
temp=zeros(1,N);
E=0;

counter=1;
tic
while E<Emax
while E<Emax
while E<Emax
while E<Emax
while E<Emax
erg(counter,1:N)=temp;
counter=counter+1;
temp(1)=temp(1)+1;
E=sum(temp.*nu);
end
temp(1)=0;
temp(2)=temp(2)+1;
E=sum(temp.*nu);
end
temp(2)=0;
temp(3)=temp(3)+1;
E=sum(temp.*nu);
end
temp(3)=0;
temp(4)=temp(4)+1;
E=sum(temp.*nu);
end
temp(4)=0;
temp(5)=temp(5)+1;
E=sum(temp.*nu);
end
toc

Funktion ohne Link?

Das ganze funktioniert auch mit N>30 Plätzen in wenigen Sekunden, das ist aber schon sehr unübersichtlich.

Nun zu meiner eigentlichen Frage: Es muss doch möglich sein, das ganze variabel zu programmieren, d.h. für eine beliebige Anzahl an Plätzen? In meiner aktuellen Version müsste ich dafür ja Schleifen hinzufügen bzw. wegnehmen. Ist es auch möglich das Ganze vollständig zu Vektorisieren? Dabei tue ich mir immer sehr schwer, leider.

[Wen der physikalische Hintergrund interessiert: Die Werte nu sind die 3N-6 Normalmoden eines Moleküls und ich möchte alle Kombinationen von Schwingungsquantenzahlen der verschiedenen Moden ausgeben lassen, die unter einer bestimmten Energiegrenze liegen.]

Viele Grüße schonmal vielen Dank für jeden Tipp/Hinweis,
deepblue

Harald

Forum-Meister


	Beiträge: 24.495

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 21.12.2018, 20:10 Titel:

Hallo,

ich würde einen rekursiven Ansatz wählen.
Macht der Code denn das gewünschte? Mein Eindruck ist, dass E < Emax sein soll. Wenn die Bedingung abbricht, ist E aber > Emax

Vorschlag:

Code:

function temp = combinations(nu, Emax)

if length(nu) > 1
temp = [];
for k = 0:floor(Emax/nu(1))
furtherCombi = combinations(nu(2:end), Emax - k*nu(1));
temp = [temp; repmat(k, size(furtherCombi,1), 1), furtherCombi];
end
else
temp = (0:floor(Emax/nu))';
end

Funktion ohne Link?

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)

deepblue

Themenstarter

Forum-Newbie


	Beiträge: 2

	Anmeldedatum: 21.12.18

	Wohnort: ---

	Version: 2016

Verfasst am: 23.12.2018, 18:05 Titel:

Hallo,

Vielen Dank für deinen Vorschlag, das scheint genau das zu sein, was ich gesucht habe. Die beiden Varianten liefern auch identische Ergebnisse (bis auf den Sonderfall wenn E zuällig gleich Emax ist, das tritt aber mit den realen Werten nie auf).

Ich hätte noch eine Frage zur Performance der Schleifen- gegenüber der rekursiven Variante: Ich habe ein wenig herumprobiert und die Schleifen-Variante scheint etwas schneller zu sein, wenn Emax klein ist. Erhöht man Emax und lässt damit mehr Permutationen zu, ist die Rekursionsvariante deutlich schneller. Woran kann das liegen? (Getestet habe ich das mit dem angehängten File, ab etwa Emax=250 ist die rekursive Variante schneller)

Nochmal vielen Dank für die super praktische Lösung!
Viele Grüße,
deepblue

combinations_performance.m

Beschreibung:

Download

Dateiname:

combinations_performance.m

Dateigröße:

4.98 KB

Heruntergeladen:

235 mal

Harald

Forum-Meister


	Beiträge: 24.495

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 27.12.2018, 21:19 Titel:

Hallo,

ich würde auch den Profiler verwenden, um mir das genauer anzusehen.
Der rekursive Ansatz ist jedenfalls der flexiblere und ich würde ihn daher generell bevorzugen. Wenn geschachtelte whiles für feste Anzahlen von Parametern schneller sind, dann kann man das verwenden, wenn es um das letzte bisschen Performance geht.

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 28.12.2018, 16:52 Titel: Re: Beliebige Anzahl geschachtelter while-Schleife

Hallo deepblue,

Statt geschachtelter Schleifen oder einer Rekrusion kannst Du auch eine einzige WHILE-Schleife verwenden, und einen Vektor als Zähler:

Code:

iR = 0;
n = 36;
v = zeros(1, n); % Current index vector as row
m = 8;
ready = false;
Result = cell(1, 1000); % Do you have a good guess for the final size?
while ~ready
if Condition(v) % Insert what you need here
% Call the function with the index vector as first input:
iR = iR + 1;
Result{iR} = v;
end

% Increase index vector:
ready = true;
for iv = 1:n
if v(iv) < m
v(iv) = v(iv) + 1;
ready = false;
break; % Stop "for iv" loop
end
v(iv) = 0; % Reset this index
end
end
Result = Result(1:iR); % Crop unused elements

Funktion ohne Link?

Dies ist equivalent zu n geschachtelten Schleifen, die von 0 bis m laufen, ohne dabei unübersichtlich zu werden.

Gruß, Jan


Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:	Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen

Impressum | Nutzungsbedingungen | Datenschutz | FAQ |

RSS

Hosted by:

Copyright © 2007 - 2025 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.