Permutation

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

Partner:

Forum

Option

[Erweitert]

• Diese Seite per Mail weiterempfehlen

Gehe zu:

Kairos

Forum-Anfänger


	Beiträge: 28

	Anmeldedatum: 12.11.10

	Wohnort: ---

	Version: ---

Verfasst am: 12.11.2010, 16:23 Titel: Permutation

Hallo Leute,

ich bin schon recht lange Leser im Forum und hatte bis dato auch immer alle Antworten gefunden. Diesmal bin ich aber am verzweifeln und möchte euch direkt um Hilfe bitten.
Ich habe folgende Aufgabenstellung:

Alle Permutationen eines binären Vektors finden.

Ich habe schon einige Lösungen, welche allerdings entweder an Speicher oder CPU oder Programmieraufwand stoßen. Der binäre Vektor hat bis zu 100 Zeichen. Ich suche also einen Weg Permutation mit Reihenfolge und ohne zurücklegen.

BSP:

xperms[1 1 0] soll ausgeben [1 0 1], [0 1 1]. Ich habe keinen entsprechenden Befehl gefunden.

Meine bisherigen Wege: Alle Permutationen bilden (100!), mehrfachnennungen löschen -> Speicher
100 while schleifen mit if-Verzweigung schreiben -> Programmieraufwand, CPU
Und (nicht lachen) Vektor als Binärzahl definieren und immer +1 rechnen. Ergebnisse speichern, die richtige Anzahl von Einsen enthalten. -> möglich, aber unschön, weil matlab keinen String größer 2^52 verarbeiten will.

Hat jemand eine Idee? Vektorlänge ist variabel, Anzahl Einsen und Nullen ist variabel. Eigentlich doch ein Problem aus der Schule. Schüssel mit 2 Ballarten, ohne zurücklegen. Da muss es doch eine praktische Lösung für geben?!

Vieln Dank für die Hilfe, Kairos

Sco

Forum-Meister


	Beiträge: 699

	Anmeldedatum: 15.08.10

	Wohnort: Dundee

	Version: 2008a, 2010a

Verfasst am: 12.11.2010, 17:12 Titel:

Hallo,

Zitat:

Ich habe keinen entsprechenden Befehl gefunden.

Nach 2 min. suchen bin ich auf den Befehl 'perms' gestossen.

Dies tut was du moechtest, allerdings nur bis etwa 10 Nummern.

Code:

P = unique(perms([1 1 0]),'rows');

Funktion ohne Link?

Wie das noch bei 2^52 Zahlen gehen soll, weiss ich leider auch nicht.

MFG

Sco

Kairos

Themenstarter

Forum-Anfänger


	Beiträge: 28

	Anmeldedatum: 12.11.10

	Wohnort: ---

	Version: ---

Verfasst am: 12.11.2010, 17:39 Titel:

Hi,

das ist variante 1, welche ich oben geschrieben habe. Erst alle Permutationen erzeugen, und dann die unnötigen löschen. Ab 11 leider nicht mehr zu gebrauchen. Ich brauche einen Befehl, der das bis 97 kann. Also nur die x über y Varianten berechnet und nicht alle x!

Wie gesagt gehts mit der Binärzahl, aber mit 97bit kann man schon eine verdammt große zahl darstellen, zu der Matlab addieren muss.

Sco

Forum-Meister


	Beiträge: 699

	Anmeldedatum: 15.08.10

	Wohnort: Dundee

	Version: 2008a, 2010a

Verfasst am: 12.11.2010, 18:18 Titel:

Hallo,

habe ich ja auch geschrieben, dass es ab 10 nicht mehr zu gebrauchen ist. Schau mal im Matlab Exchange, vielleicht findest du da was.

MFG

Sco

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 12.11.2010, 22:26 Titel: Re: Permutation

Hallo Kairos,

Zitat:

Alle Permutationen eines binären Vektors finden.
Der binäre Vektor hat bis zu 100 Zeichen. Ich suche also einen Weg Permutation mit Reihenfolge und ohne zurücklegen.
BSP: xperms[1 1 0] soll ausgeben [1 0 1], [0 1 1].

Ich verstehe das Beispiel nicht. Ein Vektor mit 3 Elementen erzeugt 6 Permutationen. Wieso erhälst Du nur 2? Wenn die Einsen als gleich gelten, sollten es zumindest 3 sein: [0 1 1], [1 0 1], [0 1 1].

Möchtest Du alle Möglichkeiten finden N Einsen in einen Vektor mit M Nullen zu schreiben? Dann wäre die Aufgabe equivalent dazu N Zahlen aus [1:M] zu ziehen, ohne Zurücklegen und ohne Reihenfolge (also die Ausgabe ist immer sortiert) - das wären dann Kombinationen, und keine Permutationen.

Dafür gibt es einerseits die Matlab Funktion NCHOOSEK. Die ist aber verblüffend langsam. In der FEX gibt es aber hinreichend viele effizienter programmierte Lösungen, z.B. Matt Fig's COMBINATOR oder mein C-Mex VCHOOSEK (eine reine Matlab-Version befindet sich in der Test-Funktion TestVChoosek).

Gruß, Jan

Kairos

Themenstarter

Forum-Anfänger


	Beiträge: 28

	Anmeldedatum: 12.11.10

	Wohnort: ---

	Version: ---

Verfasst am: 12.11.2010, 23:26 Titel:

Da stehn doch 3 Antworten (Ausgangsvektor + 2 Antworten = 3). Bei Dir ist übrigens eine doppelt. Very Happy

Der Unterschied zwischen Permutation und Kombination wurde mir wohl in der Schule nicht beigebracht. Hab mal Wikipedia gefragt und kenne nun den Unterschied.

Ich probiere Deine Antworten durch. Wenn eine davon fixer geht als das addieren der Binärzahl, dann bin ich oberglücklich. Danke für die Antwort, ich berichte wieder nach dem probieren.

LG Kairos

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 12.11.2010, 23:54 Titel:

Hallo Kairos,

Zitat:

Da stehn doch 3 Antworten (Ausgangsvektor + 2 Antworten = 3).

Nunja, den Ausgangsvektor als Antwort mitzuzählen ist nicht gerade selbsterklärend.

Ich muss aber nochmal Nachfragen: Was ist denn nun genau die Frage? Es ist sehr mühsam eine praktische Lösung zu erklären, wenn die Frage nicht eindeutig gestellt ist.
Liege ich mit der Vermutung richtig, dass Du alle binären Vektoren mit M Stellen und N Einsen erzeugen möchtest?

Wenn ja, kannst Du M und N irgendwie begrenzen? Für M=100 und N=50 sind das sonst 1.0*10^29 Vektoren a 100 Byte. Auch für M=100 und N=15 flögen Dir da noch 3080 PetaByte um die Ohren. Die Begrenzung von NCHOOSEK liegt also nicht so sehr in der ineffizienten Programmierung (ein Faktor 1000 macht bei solchen Problemen schon gar nicht mehr so viel aus...), sondern in der schieren Masse der Ergebnisse.

Gruß, Jan

Kairos

Themenstarter

Forum-Anfänger


	Beiträge: 28

	Anmeldedatum: 12.11.10

	Wohnort: ---

	Version: ---

Verfasst am: 15.11.2010, 19:17 Titel:

Du liegst mit deiner Vermutung genau richtig. Es entstehen n!/(n1!*n2!) Ergebnisse. Ich brauche sie theoretisch nicht speichern, da ich nur das Optimum (also nur einen Vektor) brauche.

Im fertigen Programm wird die Anzahl der Ergebnisse noch weiter durch Randbedingungen verkleinert. Die einsen müssen einen min und max Abstand zueinander einhalten.

Wenns nicht auf einen Schwung geht, wäre auch ein Befehl wie "nächste Kombination" sinnvoll. DIe Befehle und Programm die ich gefunden habe, gehen jedoch nicht zuverlässig alle Kombinationen durch.

Nochmal kurz meine bisherige Lösung (nur das Prinzip): Beispiel Kombination von [1 1 0]

Code:

Z = 1; % Zähler bis max bin2dec(ones(1,97))
N = 3!/(1!*2!) % Variablen ausm GUI, je nach länge, anzahl 1 und 0
N1 = 1; % Anzahl gültige Ergebnisse
while N1 <= N
B = dec2bin(Z); % Aus Zähler Binärzhal machen
if sum(B) == 2 % Abfrage ob richtige Anzahl 1, eigentlich auch noch Abfrage nach min/max Abstand von einsen. Für uns erstmal unwichtig.
E(N1) = B; % Speichern der gültigen Ergebnisse
N1 = N1 + 1; % Zähler nächstes Ergebnis
end
Z = Z + 1; % Zähler nächster versuch
end

Funktion ohne Link?

Matlab muss bis 1.5846e+029 hochaddieren. Das braucht nen weilchen...
Speicher ist nicht das Problem, da ich E nicht speichern muss. Ich kann bei jeden Schritt abfragen, ob das aktuelle E besser oder schlechter als das gespeicherte ist.

Sieht irgendjemand eine schnellere Möglichkeit das Problem zu lösen? Dieser Programmteil wird leider nicht nur 1x aufgerufen, sondern etwa 50x. Falls es keine Möglichkeit gibt, werde ich die Aufgabe an sich erklären. Vielleicht fällt uns ja was anderes ein.

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 17.11.2010, 13:24 Titel:

Hallo Kairos,

Zitat:

Code:

B = dec2bin(Z);
if sum(B) == 2

Funktion ohne Link?

Das ist nicht effizient. DEC2BIN macht aus einem DOUBLE einen String (!), SUM macht daraus wieder ein DOUBLE-Vector und summiert ihn. Dazu muss DEC2BIN auch nooch jede Logarithmen und POW2 berechnen, was Dein Programm deutlich bremst.

Du könntest stattdessen die notwendigen Zeilen aus "dec2bin.m" herauskopieren und so viel wie möglich vor der Schleife berechnen, z.B. alle LOG2 und POW2 Aufrufe.

Zitat:

Matlab muss bis 1.5846e+029 hochaddieren. Das braucht nen weilchen...

Wobei natürlich auch zu bemerken ist, dass Matlab das gar nicht kann. Es rechnet ja nur mit DOUBLEs, die nur 16 Dezimal-Ziffern haben. Deshalb:

Code:

disp((1.0e18 + 1) - 1.0e18)
>> 0

Funktion ohne Link?

Wenn Du also sowieso mit einem Binär-Vektor arbeiten möchtest, mach das am besten direkt:

Code:

B(1:100) = uint8(0);

Funktion ohne Link?

Dann verteile die Einsen in diesem Vektor gemäß den minimalen und maximalen Abständen.
Es ist übrigens nicht nur wegen des Speichers unmöglich 10^29 Vektoren zu berechnen, es dauert auch sicherlich länger als 14 Milliarden Jahre. Du musst also unbedingt schon beim Erstellen der Vektoren alle nötigen Einschränkungen berücksichtigen.

Gruß, Jan

Kairos

Themenstarter

Forum-Anfänger


	Beiträge: 28

	Anmeldedatum: 12.11.10

	Wohnort: ---

	Version: ---

Verfasst am: 17.11.2010, 15:36 Titel:

Hallo Jan,

danke für die Antwort. Wenn ich alle Bedingungen abklopfen will, muss ich eine Menge programmieren. Es bleibt mir wohl nichts anderes übrig.
Mein letzter Versuch, bevor ich einen genetischen Algorithmus für das Problem schreibe, wird sein die Kombinationen mit zurücklegen zu untersuchen.

Also 100 Elemente, 50 Einsen. Pause (also Anzahl Nullen) beträgt dann 0, 1 oder 2. Das Problem kann ich nicht ganz mathematisch korrekt ausdrücken. Weil man die verschieden großen Pausen zurücklegen darf, die Anzahl der Einsen aber fest ist. Dafür kann ich ein Programm schreiben, auch wenns etwas aufwendig ist.
Ich fürchte aber, dass auch das mein Rechner in keiner akzeptablen Zeit berechnen kann. Na mal schaun.

MfG Kairos

PS: Und vielen Dank für die informatischen Hiwneise. Ich bin Reglungstechniker und verstehe nicht so viel von der Informatik. Eine Zahl ist eine Zahl ^^. Warum erzeugt dec2bin eine string und keine uint8? Wer macht denn sowas... warum gibts eigentlich kein uint1 Format? Also nur 1bit pro zeichen. Ist das eine dumme Frage? Smile

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 17.11.2010, 19:01 Titel:

Hallo Kairos,

Zitat:

Eine Zahl ist eine Zahl

Schön wär's! Leider ist eine Zahl meistens eine Zahl. Dann gibt's aber auch noch NaN's ("not a number"), was aber auch eine Zahl ist. Und natürlich gibt's dann noch verschiedene NaNs (signaling und not-signaling), aber zum Glück beschränkt sich Matlab auf eine Sorte.

Zitat:

Warum erzeugt dec2bin eine string und keine uint8?

Matlab hat einen binäre Type: LOGICAL. Der ist intern ein UINT8. In Matlab 5.3 war das sogar ein DOUBLE und konnte auch andere Werte als 0 und 1 annehmen, es wurden aber alle nicht-Nuller als 1 interpretiert. Schräg, nicht wahr?!

Zitat:

warum gibts eigentlich kein uint1 Format? Also nur 1bit pro zeichen.

Der Zugriff im Speicher ist ziemlich zeitaufwändig. Wenn man aber mit großen Bitmaps umgehen möchte, klappt das über UINT8-Variablen ganz gut.

Gruß, Jan

Kairos

Themenstarter

Forum-Anfänger


	Beiträge: 28

	Anmeldedatum: 12.11.10

	Wohnort: ---

	Version: ---

Verfasst am: 24.11.2010, 10:30 Titel:

Abschließend bleibt zu sagen, dass diese Problem mit allen möglichen Vereinfachungen wohl auf keinem binären Rechner zu lösen sein wird. Ein genetischer Algorithmus findet meist die richtige Lösung.


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.