Jetzt soll zum einen jede Zeile nur einmal auftauchen, d.h. Zeile 3 (oder 1) müssten verändert werden.
Außerdem sollen in keiner Zeile nur identische Elemente stehen, also Zeile 4 ist unzulässig.
Gibt es da kompakte Ansätze für? Mir fallen nur ganz wirre while, if und for Ansätze ein, die wahrscheinlich auch klappen würden, aber das Problem ist, wenn ein Element verändert wird, müssen wieder die Bedingungen geprüft werden. Und die Prüfung ist das, was ich sehr schwierig finde und nur mit einer for Schleife realisieren könnte (eine Zeile jeweils mit allen anderen Zeilen vergleichen, und das für jede Zeile durchführen), aber selbst die krieg ich nicht hin.
Mein Ansatz wäre:
Code:
%Prüfung auf unterschiedliche Elemente in einer Zeile
for i=1:(p-1) if %gleiche Elemente
A(i,:)=randi([1,p],1,M);
end end
Das Problem ist die Prüfung auf gleiche Elemente.
Und es müsste am Schluss beides nochmal geprüft werden, um eine übergeordnete while Schleife einzusetzen.
Aber selbst wenn das klappt, KÖNNTE es lange in der while Schleife hängen bleiben (unwahrscheinlich, aber möglich).
Ich hoffe, jemand hat eine Idee und kann mir einen FIngerzeig in die richtige Richtung geben.
Einen vollkommen allgemeinen Ansatz für solche Probleme der Kombinatorik kann es nicht geben. "M ist erstmal unbeschränkt" erfordert mehrere verschiedene Ansätze, da sich M=4, M=40000 und M=4e12 nicht mit den gleichen Methoden sinnvoll behandeln lassen.
Kannst Du dies also irgendwie einschränken?
Gruß, Jan
razmatazz.guest
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 20.06.2013, 15:03
Titel:
Ja klar.
Verzeihung ich vergesse immer wieder, dass ganz andere Größenordnungen möglich sind..
M liegt hier im Bereich <10.
p maximal bei 4.
razmatazz.guest
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 21.06.2013, 13:14
Titel:
Ok habe es mit while und for Schleifen gemacht, nicht schön, aber es macht was es soll, und ist noch recht allgemein, wie ich finde.
Für jemanden der vlt. eine Inspiration braucht hier der Code:
%Prüfen ob Zeilenelemente ausschließlich identisch sind for i=1:p
%Zeilenwerte in einen Spaltenvektor schreiben
hilf_vek=A(i,1:1:size(A,2))' ;
hilf_vek=unique(hilf_vek,'rows');
whilelength(hilf_vek)==1
A(i,:)=randi([1,p],1,M);
hilf_vek=A(i,1:1:size(A,2)) ;
hilf_vek=unique(hilf_vek,'rows');
end end
%Nochmals Zeilenelemente auf Gleichheit prüfen
for i=1:p
%Zeilenwerte in einen Spaltenvektor schreiben
hilf_vek=A(i,1:1:size(A,2))' ;
hilf_vek=unique(hilf_vek,'rows');
iflength(hilf_vek)==1
werte_ok=0;
%sobald eine Zeile mit identischen Zeilenelementen gefunden ist,
%Abbruch dieser Schleife und zurück zum Anfang der äußersten while Schleife
break end end
die Lösung gefällt mir gut, kann mir gar nicht vorstellen, warum die nicht schneller ist.
Aber allein im Zuge der Übersichtlichkeit werde ich meine durch deine ersetzen.
Meine Überlegungen waren irgendwie verknotet, und so ist es auch der Code, vorallem habe ich unique unnötig verkompliziert.
Und wieder einen neuen Befehl kennen gelernt (intersect).
ich denke es liegt am intersect warums langsamer ist. aber das weis jan oder so bestimmt besser
razmatazz.guest
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 22.06.2013, 11:23
Titel:
Fällt mir gerade erst auf:
"Matrix(k,=0; " ist durch Initialisierung mit "Matrix=zeros(p,m);" überflüssig.
Außerdem hängt sich das ganze in der while a==1 Schleife auf, wenn die Spalten zwar unterschiedliche Elemente beinhalten, Zeilen aber gleich sind, weil es nicht mehr geändert wird.
NxM Matrix mit zufälligen Zahlen aus 1:p
M liegt hier im Bereich <10.
p maximal bei 4.
Dies erlaubt noch einen brute-force Ansatz, bei dem man zuerst alle möglichen Kombinationen erzeugt und dann zufällig welche aussucht, "N=p" lasse ich weg, da dies von der allgemeinen Lösung abgedeckt wird. Zur effizienten Erstellung aller möglichen Kombinationen wird dies benötigt: http://www.mathworks.com/matlabcent.....exchange/26242-vchoosekro
Code:
p = 4;
M = 10;
N = 15;
pool = VChooseKRO(uint8(1):uint8(p), M); % Unique combinations
% Delete rows with all equal elements:
index = all(bsxfun(@eq, pool, pool(:, 1)), 2);
pool(index, :) = [];
% Take N rows:
select = randperm(size(pool, 1), N);
% Older: select = randperm(size(pool, 1)); select = select(1:N);
result = pool(select, :);
das ist eine super Idee mit dem erzeugen aller Kombination und dann auswählen.
Und die Geschwindigkeit ist heftig.
Ich bin nur nicht zu 100% sicher, ob ich es tatsächlich überehme, da ich von der Zugänglichkeit die bisherigen Lösungen schöner finde. Aber Rechenzeit (allerdings nicht so wichtig bei meinem Problem), Schlankheit, und das Umgehen des möglichen langen Verweilens in den while Schleifen sprechen aber für deine Lösung.
Meine Unentschlossenheit zu deiner Lösung bitte nicht falsch verstehen.
Deine Antwort hat mich wahrlich verblüfft und ich danke dir für deine Leistung.
Ein schönes Wochenende
und mit freundlichen Grüßen,
Christoph
NxM Matrix mit zufälligen Zahlen aus 1:p
M liegt hier im Bereich <10.
p maximal bei 4.
Dies erlaubt noch einen brute-force Ansatz, bei dem man zuerst alle möglichen Kombinationen erzeugt und dann zufällig welche aussucht, "N=p" lasse ich weg, da dies von der allgemeinen Lösung abgedeckt wird. Zur effizienten Erstellung aller möglichen Kombinationen wird dies benötigt: http://www.mathworks.com/matlabcent.....exchange/26242-vchoosekro
Code:
p = 4;
M = 10;
N = 15;
pool = VChooseKRO(uint8(1):uint8(p), M); % Unique combinations
% Delete rows with all equal elements:
index = all(bsxfun(@eq, pool, pool(:, 1)), 2);
pool(index, :) = [];
% Take N rows:
select = randperm(size(pool, 1), N);
% Older: select = randperm(size(pool, 1)); select = select(1:N);
result = pool(select, :);
Damit komme ich auf 0.10 Sekunden (R2011b/64, Win7, Core2Duo). Für M=8, N=15, p=4 werden 0.0067 sec benötigt.
Für großes M wird die Erstellung aller möglichen Kombinationen also der Flaschenhals, da es p^M Möglichkleiten gibt. Gleichzeitig sinkt aber auch die Chance, dass man zufällig zwei gleiche Vektoren erhält. Ausserdem sind von den 4^10=1'048'576 Lösungen nur 4, bei denen alle Elemente gleich sind. Die Rejection-Methode ist dann also viel effizienter, also zufällige Kombinantionen erzeugen und bei Bedarf verwerfen.
Dann gibt es noch einen goldenen Weg, der beide Vorteile kombiniert: Erzeugung garantiert unterschiedlicher Kombinationen ohne gleich alle zu erzeugen:
Code:
p = 4;
M = 10;
N = 15;
% select = randperm(p ^ M, N);
select = double(Shuffle(p ^ M, 'index', N));
index = (select(:) - 0.5) * p .^ (1-M:0);
index = rem(floor(index), p) + 1;
V = uint8(1):uint8(p);
result = V(index);
Wenn N in der Nähe von p^M liegt, kann diese Zurückweisungsmethode sehr zeitraubend werden. Dann würde ich einen Zähler einbauen, der es erstmal 10 mal so versucht und beim 11.ten mal auf die obige Methode zurückgreift.
Natürlich könnte man auch eine statistische Abschätzung machen, ab welchem Verhältnis N zu p^M sich die eine oder andere Methode besser eignet.
Noch ein allgemeiner Ratschlag: Es scheint bei diesem Problem um zehntel bis 1000stel Sekunden zu gehen. Wenn dies Milliardenfach durchgeführt wird, könnte es sich lohnen eine Stunde aufzuwenden, um Millisekunden weniger Laufzeit zu erreichen. Aber eine Woche mit der Optimierung zu verbringen, damit das Program insgesamt 20 Sekunden kürzer läuft, wäre natürlich Zeitverschwendung.
Gruß, Jan
Einstellungen und Berechtigungen
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
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.
RSS