Anzahl Teilmengen einer n-elementigen Menge

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

Partner:

Forum

Option

[Erweitert]

• Diese Seite per Mail weiterempfehlen

Gehe zu:

Tolpatsch

Forum-Anfänger


	Beiträge: 33

	Anmeldedatum: 18.02.09

	Wohnort: ---

	Version: ---

Verfasst am: 30.06.2010, 23:15 Titel: Anzahl Teilmengen einer n-elementigen Menge

Hi!
Die Anzahl der Teilmengen einer n-elementigen Menge M ist 2^n. Bei einer Menge mit 3 Elemented gibts demzufolge 2^3=8 verschiedene Teilmengen. Mein Ziel wäre es nun folgende Matrix zu bekommen (jede Zeile steht für eine Teilmenge):

Code:

[1 1 1; 1 0 0; 0 1 0; 0 0 1; 1 1 0; 1 0 1; 0 1 1; 0 0 0]

Funktion ohne Link?

Eine 1 bedeutet, dass jenes Element in der Teilmenge enthalten ist und eine 0 bedeutet, dass jenese Element nicht enthalten ist. Bei grossen n kann eine solche Matrix sehr gross werden. Ich versuche ein Program zu schreiben, dass möglichst grosse n's handeln kann. Leider hält sich mein Erfolg in Grenzen. Hat jemand eine Idee?

Vielen Dank und Gruss!

michai

Forum-Fortgeschrittener


	Beiträge: 83

	Anmeldedatum: 22.02.10

	Wohnort: ---

	Version: ---

Verfasst am: 01.07.2010, 08:17 Titel:

Was hast du denn bisher?

Harald

Forum-Meister


	Beiträge: 24.499

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 01.07.2010, 10:10 Titel:

Hallo,

als Startpunkt würde ich nehmen:

Code:

M = dec2bin(0:2^n-1)

Funktion ohne Link?

Um die Matrix in der gewünschten Form zu bekommen:

Code:

M = arrayfun(@str2num, dec2bin(0:2^n-1))

Funktion ohne Link?

Wenn n größer werden soll, könnte man sich auch ein rekursives Vorgehen vorstellen (Matrix für n erstellen -> daraus die Matrix für n+1 machen).

Grüße,
Harald

Harald

Forum-Meister


	Beiträge: 24.499

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 01.07.2010, 13:11 Titel:

Hallo,

mich hat der Ehrgeiz gepackt:

Code:

function M = teilmengen(n)

M(2^n, n) = 0;
% M(1,1) = 0; <-- not necessary. Is 0 anyway
M(2,1) = 1; % setup for I = 1
I = 1;
while I < n % setup for I + 1
M(2^I+1:2^(I+1), 1:I) = M(1:2^I , 1:I);
% M(1:2^I, I+1) = zeros(2^I, 1); <-- not necessary. Is 0 anyway
M(2^I+1:2^(I+1), I+1) = ones(2^I, 1);
I = I + 1;
end

Funktion ohne Link?

Für n=20 erzeugt das auf meinem Rechner in < 1 s eine Datenmenge von 167 MB. Beat that! Very Happy

Viel Spaß beim Weiterverarbeiten Wink

Grüße,
Harald

Tolpatsch

Themenstarter

Forum-Anfänger


	Beiträge: 33

	Anmeldedatum: 18.02.09

	Wohnort: ---

	Version: ---

Verfasst am: 01.07.2010, 16:06 Titel:

Vielen Dank für die guten Tipps, Werde sie mal laufen lassen!

In Matlab gibt's die function 'nchoosek', sie gibt alle möglichen Teilmengen aus einer Menge an. Mit ein paar for and while loops lässt sich das in eine binäre Matrix umwandeln. ANyway, danke für die Hilfe!

greetz!


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.