Verfasst am: 23.02.2013, 14:17
Titel: Permutationen ohne Wiederholung
Ich suche die Anzahl der Permutationen einer Zahlenfolge von 1 bis 11,
für die folgende Bedingungen gelten sollen:
1,2,3 können an 1. bis 10. Stelle stehen
4,5,9,10,11 können an 3. bis 11.Stelle stehen
6,7,8 können an 1. bis 9. Stelle stehen.
Dafür habe ich bisher keine brauchbare Formel oder ein Verfahren gefunden.
Mich interessiert nur die Gesamtzahl, nicht die Auflistung der Permutationen!
Danke im voraus für Hilfe !
Verfasst am: 24.02.2013, 02:46
Titel: Re: Permutationen ohne Wiederholung
Hallo Windbe,
Das hört sich wie eine Hausaufgabe an, oder möchtest Du einen Safe knacken? Insgesamt gibt es nur 39'916'800 Permutationen der Zahlen 1 bis 11. Das lässt sich leicht im RAM auswerten, wobei man aber darauf achten sollte, dass das Array den Typ UINT8 hat, da ein DOUBLE 8 mal mehr Speicher benötigt. Der PERMS Befehl hilft hier.
Danach kann man die unerwünschten Permutationen entfernen. Man erhält weniger als 4537000 Möglichkeiten.
Gruß, Jan
windbe
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 24.02.2013, 13:58
Titel: Permutationen ohne Wiederholung
Danke für die schnelle Antwort.
Für Hausaufgaben bin ich schon zu alt, einen Safe will ich auch nicht knacken, es geht um eine Zugreihenfolge in einem Schachproblem.
Wahrscheinlich verstehe ich zu wenig von Mathematik, aber ich kann mir aus deiner Antwort noch kein praktisches Verfahren ableiten. Kannst du das bitte noch etwas auusführlicher darstellen?
Verfasst am: 24.02.2013, 17:02
Titel: Re: Permutationen ohne Wiederholung
Hallo windbe,
Code:
D = perms(uint8(1:11)); % VChooseKO(uint8(1:11), 11) % 1,2,3 können an 1. bis 10. Stelle stehen - also nicht an der 11. Stelle:
D(D(:, 11) == 1, :) = [];
D(D(:, 11) == 2, :) = [];
D(D(:, 11) == 3, :) = [];
% 4,5,9,10,11 können an 3. bis 11.Stelle stehen - also nicht an 1. und 2.: for iv = [4,5,9,10,11]
D(D(:, 1) == iv, :) = [];
D(D(:, 2) == iv, :) = [];
end
% 6,7,8 können an 1. bis 9. Stelle stehen. for iv = [6,7,8]
D(D(:, 10) == iv, :) = [];
D(D(:, 11) == iv, :) = [];
end size(D)
Das ist natürlich ineffizient und sehr häßlich. Eine konstruktive Methode wäre flexibeler und würde keine Zeit damit vertrödeln nicht benötigte Permutationen zu erzeugen. Aber wenn dies nur einmalig benötigt wird und nur wenige Sekunden Rechenzeit vergeudet - was soll's.
ABER, leider erzeugt Matlab's PERMS Befehl temporäre Arrays vom Typ DOUBLE, und das benötigt 8 mal mehr Speicher. Meine 2GB-Maschine wird davon gesprengt. Deswegen verwende ich: http://www.mathworks.com/matlabcent.....eexchange/26397-vchooseko, das deutlich schneller und Speicher-schonender ist. Dies aber muss man wiederum erstmal installieren und kompilieren. Wenn man dann noch keinen C-Compiler installiert hat, wird es zunehmend komplizierter.
Vielleicht reicht Dir dann das Endergebnis: 4536000
Gruß, Jan
Windbe
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 25.02.2013, 13:49
Titel: Permutationen ohne Wiederholung
Danke für die wiederum prompte Bearbeitung!
Ich habe inzwischen den ersten von 6 Anfangszügen "per Hand", natürlich mit Rechnerunterstützung, komplett untersucht und komme auf eine Zahl der Varianten von 49.712. Das deutet auf eine Gesamtzahl für alle 6 Anfangszüge
in der Größenordnung von etwa 300.000 hin.
Die starke Abweichung zu deinem Ergebnis liegt m. E. daran, dass ich nicht alle einschränkenden Bedingungen exakt formuliert hatte, als da sind:
2 + 3 müssen stets vor 4 stehen
1 + 3 müssen stets vor 5 stehen
6 + 7 müssen stets vor 9 stehen
7 + 8 müssen stes vor 10 stehen
2 + 8 müssen stets vor 11 stehen
Lässt sich das auch noch einprogrammieren?
Wie gesagt, ich bin nur an der Gesamtzahl, nicht an einzelnen Reihenfolgen interessiert.
Dank im voraus für deine Bemühungen !
Verfasst am: 26.02.2013, 13:01
Titel: Re: Permutationen ohne Wiederholung
Hallo Windbe,
Schau Dir doch mal meinen Code an. Du kannst sicherlich die neuen Bedingungen mit Hilfe der gezeigten Methoden implementieren.
Gruß, Jan
Windbe
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 26.02.2013, 22:00
Titel: Permutationen ohne Wiederholung
Wenn ich das richtig verstehe, könnte das wie folgt lauten:
Code:
% 2,3 müssen stets vor 4 stehen for iv = [2,3]
D(D(4,:) = = iv,:) = [] % 1,3 müssen stets vor 5 stehen for iv = [1,3]
D(D(5,:) = = iv,:) = [] % 6,7 müssen stets vor 9 stehen for iv = [6,7]
D(D(9,:) = = iv,:) = [] % 7,8 müssen stets vor 10 stehen for iv = [7,8]
D(D(10,:) = = iv,:) = [] % 2,8 müssen stets vor 11 stehen for iv = [2,8]
D(D(11,:) = = iv,:) = []
Verfasst am: 26.02.2013, 23:12
Titel: Permutationen ohne Wiederholung
Offensichtlich sind da ohne meine Absicht Smilies in meine Formeln geraten, weil ich jeweils eine Leertaste vergessen habe. Also nochmal:
% 2,3 müssen stets vor 4 stehen
for iv = [2,3]
D(D(4, : ) = = iv,: ) = []
usw. usw.
Windbe
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 27.02.2013, 12:52
Titel: Permutationen ohne Wiederholung
Wenn das Programm ok ist, dann alles in das erste Excel-Feld eintragen?
Muss der Befehl end nicht erst ganz zum Schluss kommen oder auch zwischendurch wie in deinem Programm?
Danke für deine Unterstützung eines Programmier-Laien !
jo
Verfasst am: 27.02.2013, 15:29
Titel: Re: Permutationen ohne Wiederholung
Hallo Windbe,
Wenn das Programm ok wäre, würde es ja laufen. Macht es aber nicht.
Nein, das "end" muss nicht erst am Schluss kommen, wie auch in der Dokumentation (Getting Started Kapitel) erklärt wird. Jede FOR-Schleife wird mit einem "end" abgeschlossen. Siehe auch "help for".
Der Operator zum Vergleich heißt "==" ohne Space zwischen den "=".
Zitat:
Code:
% 2,3 müssen stets vor 4 stehen for iv = [2,3]
D(D(4,:) = = iv,:) = []
Dies wäre "2 und 3 müssen vor der 4. Position stehen".
Man kann nicht einfach die erste und zweite Position der Indices vertauschen, es ist also ein deutlicher Unterschied, ob man "D(:, 4)" oder "D(4, :)" schreibt.
Zitat:
Wenn das Programm ok ist, dann alles in das erste Excel-Feld eintragen?
Was genau möchtest Du in welches Excel-Feld eintragen???
Woher kommt den plötzlich Excel?
Ich habe den Eindruck, dies ist die falsche Methode um eine zuverlässige Lösung zu bekommen. Ich würde empfehlen entweder die Getting Started Kapitel zu lesen um grundlegende Matlab-Kenntnisse zu bekommen, oder jemand zu fragen, ob er das bei angemessener Gegenleistung für Dich schreibt (siehe Unterforum "Programmieraufträge").
Gruß, Jan
Windbe
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 02.03.2013, 17:09
Titel: Permutationen ohne Wiederholung
Bitte entschuldige mein laienhaftes Wissen in der Programmierung, ich hatte angenommen, dass perms ein Excel-Befehl ist.
Dass das Programm nicht läuft, könnte m. E. daran liegen, dass sich Widersprüche zwischen dem ersten und zweiten Teil ergeben können.
Im zweiten Teil ab "2+3 müssen stets vor 4 stehen" usw. meinte ich mit der 4 nicht die Position, sondern die Zahl 4, ich hätte also besser formulieren sollen: 2+ 3 müssen stets vor der 4 stehen. Das gilt dann auch für die folgenden Forderungen.
Deshalb müsste das sicher ein anderer Programmiercode sein.
Bitte erbarme dich nochmals zu dieser Änderung !
jo
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