3. Teilmengen rekursiv bestimmen (Pseudocode)

Teilmengen rekursiv bestimmen (Pseudocode)

  • J

    Hallo zusammen,

    sitze gerade mit meinen C++ Anfängerkenntnissen einer Informatik-VL vor der Aufgabe die Teilmengen einer endlichen Menge à la \{1,\dots,n\} auszugeben.

    Ich weiß, dass ich die Rekursion so handhaben könnte:

    Rekursionsanker
    wenn Menge {m}\{m\} (also einelementig), dann
    Teilmengen = ∅,{m}\emptyset, \{m\}

    Rekursionsschritt:
    Teilmengen\left(\{1,\dots,n\}\right) = Teilmengen\left(\{1,\dots,n-1\}\right) und (Teilmengen\left(\{1,\dots,n-1\}\right) \cup \{n\})

    Wie könnte man eine solche rekursive Funktion programmieren? Mich irrititert die Realisierung der Vereinigung, schließlich sollen wir alles in einer Funktion abarbeiten und ich kann die vorherigen Teilmengen, die ich ja im Endeffekt duplizieren muss um sie mit dem verbliebenen Element zu vereinigen nicht zwischenspeichern.

    Hoffe ihr könnt mir helfen.

    Grüße
    Joe

    0
  • V

    Im Rekursionsschrintt von Dir habe ich eine Endlosschleife.
    edit: Ach, ich vermute, Du hast die letzte schließende runde Klammer falsch angebracht.

    0
  • J

    Hallo volkard,

    ja die Klammer soll eingentlich hinterher kommen, denn ich will das Element n einfach in die generierten Teilmengen vereinigen.

    Man könnte den Rekursionsanker auch im Grunde auf eine leere Menge bzw. einen leeren String beziehen, der dann einfach nur die leere Menge bzw. das leere Wort ausgibt.

    Ich bräuchte aber mal einen Tipp wie ich meine Überlegungen zu einem Algorithmus fassen kann.

    0
  • B

    Wie stellst du die Mengen denn in C++ dar?

    0
  • J

    Ich stelle die Menge zur Zeit als String dar (also sind es im Grunde Worte - deswegen auch das leere Wort oben :)), Arrays wären alternativ natürlich auch möglich (wobei mir Strings lieber wären). Es ist eine allgemein gestellte Aufgabe, aber mir sind solche Datentypen wie Listen oder Mengen (jedenfalls kenne ich diese aus Delphi) in C++ nicht bekannt und dürfen daher nicht verwendet werden.

    Mein Problem ist also im Grunde die Formulierung eines Algorithmus, da ich nicht weiß ob die Ausgabe direkt in der Funktion erfolgt soll - also "void" oder eben als string zurückgegeben werden soll. Dann wäre die Vereinigung die einfache Konkatenation "+", aber wie sollte ich das einfach angehen?

    0
  • V

    JoeSunnex schrieb:

    ja die Klammer soll eingentlich hinterher kommen, denn ich will das Element n einfach in die generierten Teilmengen vereinigen.

    Nein.

    Teilmengen({1,…,n}) = Teilmengen({1,…,n−1}) und Teilmengen({1,…,n−1})∪{n}
    passt auch nicht.

    Willst ja nicht hinten (Teilmengen({1,…,n−1})∪{n} haben, also die Menge der Teilmengen mit {n] vereinigen.
    Dann käme ja was raus wie
    Teilmengen({1,2,3})={{},{1},{2},{1,2}} und {{},{1},{2},{1,2}}∪{3}
    also
    Teilmengen({1,2})={{},{1},{2},{1,2}} und {{},{1},{2},{1,2},{3}}
    also
    Teilmengen({1,2})={{},{1},{2},{1,2},{3}}

    Also Teilmengen({1,…,n−1})∪{n} ist ein magischer Ausdruck, der meint, an jede Menge aus Teilmengen(...) wird {n] drangehängt und da vesteckt sich doch irgendwas sehr großes.
    Nicht so hübsch. Deswegen geht das so auch nicht zu programmieren.

    Vielleicht eine andere Rekursionsregel?
    Ich würde gerne was abspalten, was ich direkt ausgeben kann.
    teilmengen({1,…,n})={1,…,n} und teilmengen(...) und ...

    0
  • V

    Hab da was gefunden. Die Sachen(rest), die ich mir merken mußte, um sie später an die Ausgabe dranzuhängen, merke ich mir, indem ich sie als zweiten Funktionsparameter ebenso die Rekursion hinunterschubste wie die Menge selber.

    teilmengen({},rest)={rest}
    teilmengen({1,…,n},rest)=teilmengen({1,…,n-1},rest) ∪ teilmengen({1,…,n-1},{n}∪rest)
    teilmengen({1,…,n})=teilmengen({1,…,n},{})

    //Mit rot verschlüssselt, für den Fall, dass Du noch ein weinig rätseln magst.

#vapyhqr <vbfgernz>
#vapyhqr <fgevat>
hfvat anzrfcnpr fgq;

//Mhrefg zvg Fgevatf:

ibvq grvyzratra(fgevat zratr,fgevat erfg){
    vs(zratr==""){
        pbhg<<erfg<<'\a';
    }
    ryfr{
        fgevat a=zratr.fhofge(zratr.yratgu()-1,1);
        fgevat nasnat=zratr.fhofge(0,zratr.yratgu()-1);
        grvyzratra(nasnat,erfg);
        grvyzratra(nasnat,a+erfg);
    }
}
ibvq grvyzratra(fgevat zratr){
    grvyzratra(zratr,"");
}

hafvtarq ybat ybat p=0;

//Haq wrgmg zvg Mrvtrea.
//Qvr zratr vfg mjvfpura ortva haq raq.
//Qre erfg vfg mjvfpura raq haq erfgraq.
ibvq grvyzratra(qbhoyr* ortva,qbhoyr* raq,qbhoyr* erfgraq){
    vs(ortva==raq){
        sbe(qbhoyr* v=raq;v!=erfgraq;++v)
            pbhg<<*v<<' ';
        pbhg<<'\a';
    }
    ryfr{
        ++p;
        fjnc(*(erfgraq-1),*(raq-1));//trfnzgra erfg hz rvara Cyngm anpu yvaxf ebyyra
            //jrtra qrf ebyyraf vfg qvr Ervurasbytr qre Nhftnor avpug zrue angüeyvpu.
        grvyzratra(ortva,raq-1,erfgraq-1);//yvaxre orervpu vfg rvaf xyrvare, qre erfg oyrvog
        ++p;
        fjnc(*(erfgraq-1),*(raq-1));//jvrqreurefgryyra

        grvyzratra(ortva,raq-1,erfgraq);//yvaxre orervpu vfg rvaf xyrvare, qre erfg rvaf teößre oyrvog
            //yhfgvt, jvr a qnorv iba fryore iba zratr anpu erfg jnaqreg.
    }
}
ibvq grvyzratra(qbhoyr* ortva,qbhoyr* raq){
    grvyzratra(ortva,raq,raq);
}

vag znva(){
    pbhg<<"fgneg\a";
    grvyzratra("nop");
    pbhg<<"raqr\a";

    pbhg<<'\a';

    pbhg<<"fgneg\a";
    qbhoyr zratr[]={2,3,5,};
    grvyzratra(ortva(zratr),raq(zratr));
    pbhg<<"raqr\a";
    pbhg<<p<<'\a';
}
    0
  • J

    Einfach noch einen zusäzlichen parameter X einfügen. Immer wenn man ne Menge A gefunden hat und ausgeben will, gibt man stattdessen A vereinigt X aus.

    Teilmengen({1,...,n},X) = Teilmengen({1,...,n-1}, 😵 vereinigt Teilmengen({1,...,n-1},X u {n})

    Basisfall: Teilmengen(leere Menge,X) = {X}

    Anfangs einfach X auf leere Menge setzen...

    0
  • ?

    Da das Ganze nach funktionaler Programmierung schreit, hab ich mich mal eine TMP Lösung gewagt:

    http://ideone.com/qGvg5K

    Man beachte den Typ von t 🤡

    0
  • V

    tmper schrieb:

    Da das Ganze nach funktionaler Programmierung schreit, hab ich mich mal eine TMP Lösung gewagt:

    http://ideone.com/qGvg5K

    Man beachte den Typ von t 🤡

    Kannste noch machen, daß

    t.print();

    oder ein ähnlicher Aufruf zur Laufzeit alle auf dem Bildschirm anzeigt?

    0
  • ?

    Mit operator<< ließe sich das ganze sicherlich besser lösen. Mit nur der member function hatte ich das Problem die Grenzen des sets zu erkenne, deshalb eine freie Funktion:

    http://ideone.com/jR6nTR

    0
  • ?

    Jetzt funktioniert auch die Potenzmenge der leeren Menge:

    http://ideone.com/b73VkQ

    0
  • ?

    Das grenzt ja fast an Rufmord wenn hier jemand anders unter dem Namen "tmper" einen TMP-Code vorlegt 😉

    Mit der in diesem Forum entwickelten TMP-Bibliothek wird das Problem ein Kinderspiel:

    #include <iostream>

template <int I> using element = std::integral_constant<int, I>; // für tmper

template <typename TL> struct go {
  template <typename I> struct go2 {
    template <typename J, typename T> struct go3
      : std::conditional<static_cast<bool>(I::value & (1 << J::value)), T, void> {};
    using type = filter<zip_with<go3, make_index_list<size<TL>::value>, TL>,
                        static_not<std::is_void>::template action>;
  };
};

template <typename... E>
using all_subsets = transform<make_index_list<(1<<(sizeof...(E)))>, go<type_list<E...> >::template go2>;

template <typename T> struct print_ { static void print(std::ostream& os) { os << T::value; } };
template <typename... Ts> struct print_<type_list<Ts...> > {
  static void print(std::ostream& os)
  { os << "{ "; (void)expression_sequence((print_<Ts>::print(os),os<<' ')...); os << "}"; }
};
template <typename TL> void print(std::ostream&os=std::cout) { print_<TL>::print(os);os<<'\n'; }

int main()
{
  print<all_subsets<element<0>, element<1>, element<2>>>();
  print<all_subsets<>>();
}

    (gesamter Code)

    0
  • J

    Ich danke euch für die Hinweise, ich habe anscheinend den Wald vor lauter Bäume nicht gesehen und so einen zweiten Parameter für die Funktion für "unnötig" gehalten und Ansätze im Internet waren etwas komplex.

    Der Ansatz von volkard ist mir am sympathischsten, da ich ihn verstehe, während ich die anderen Ansätze aufgrund der starken "Objektorientierung" (eigene Klassen, Befehle für eigene Klassen,...) nicht ganz lesen kann.

    Hier aber der Ansatz (obwohl die überladene Funktion gar nicht hätte sein müssen :D):

    void teilmengen(string menge,string rest){
    if((menge == "") && (rest == "")){
        cout << "epsilon" << endl;  // Ausgabe des leeren Wortes
    }

    else if(menge==""){
        cout<< rest << endl;
    }
    else{
        string n=menge.substr(menge.length()-1,1);
        string anfang=menge.substr(0,menge.length()-1);
        teilmengen(anfang,rest);
        teilmengen(anfang,n+rest);
    }
}
void teilmengen(string menge){
    teilmengen(menge,"");
}
    0
  • C
    Mod

    templer schrieb:

    { os << "{ "; (void)expression_sequence((print_<Ts>::print(os),os<<' ')...); os << "}"; }

    expression_sequence benötigt geschweifte Klammern, sonst ist es nur ein normaler Funktionsaufruf ohne besondere Einschränkungen hinsichtlich der Reihenfolge der Auswertung der Argumente:

    { os << "{ "; (void)expression_sequence{(print_<Ts>::print(os),os<<' ')...}; os << "}"; }
    0
Anmelden zum Antworten