[C++] k elementig Teilmengen ausgeben



  • Hallo Leute,
    ich habe ein Problem eine elegante Lösung zu finden, welche mir wie die Überschrift schon sagt, alle k elementig Teilmengen ausgibt.
    Ein Beispiel: Ich habe die Menge { 1, 2 , 3, 4, 5 } und nun möchte ich alle 3 elementige Teilmengen haben. Das wären hier { 1, 2 ,3 }, { 1, 2 ,4 }, { 1, 2 ,5 },{ 1, 3 ,4 }, { 1, 3 ,5 }, { 1, 4 ,5 }, { 2, 3 ,4 }, { 2, 3 ,5 }, { 2, 4 ,5 }, { 3, 4 ,5 }. Das sollte nun 10 Mengen sein. Hat jemand eine Idee wie man diese elegant finden kann?

    Mit freundlichen Grüßen
    yihaaa



  • Mehr oder weniger elegant:

    #include <vector>
    #include <set>
    #include <algorithm>
    
    using namespace std;
    
    int main()
    {
    	int tmpSet[] = {1, 2, 3, 4, 5};
    	vector<int> set(begin(tmpSet), end(tmpSet));
    
    	set<vector<int>> result;
    
    	do {
    		vector<int> tmp(set.begin(), set.begin()+3);
    		result.insert(tmp);
    	} while ( next_permutation(set.begin(), set.end()) );
    
    	return 0;
    }
    

    Ungetestet und ineffizient... 🙄



  • Mehr oder weniger umfangreich
    Diesen Link nur anklicken, wer immun gegen generischen Template-Code ist

    Getestet und Effizient...



  • Leider gibt es noch kein next_combination() im aktuellen Standard, auch wenn es dazu schon ein Proposal gab. Bei Howard Hinnant findet man allerdings eine [url=http://home.roadrunner.com/~hinnant/bloomington/combinations.html]fertige Implementierung[url] dazu.
    Dadurch wird der Code von Skym0sh0 schon mal einiges effektiver, da man sich etliche Iterationen spart.



  • Okay erst mal Danke an euch drei! Ich habe mal den Code etwas umgebaut und dort werden aber alle Permutationen von den z.B. drei Elementen gemacht. Mein Ziel ist es aber die Reihenfolgen außer acht zu lassen. Beispiel { 1, 2, 3 } = { 3, 2, 1 }.

    Gruß
    yihaaa

    std::vector<int> set;
    	set.push_back( 1 );
    	set.push_back( 2 );
    	set.push_back( 3 );
    	set.push_back( 4 );
    	set.push_back( 5 );
    
    	std::set<std::vector<int>> result;
    
        do {
    		std::vector<int> tmp(set.begin(), set.begin()+3);
            result.insert(tmp);
        } while ( next_permutation(set.begin(), set.end()) );
    
    	for ( std::set< std::vector< int > >::iterator it = result.begin( ); it != result.end( ); it++ )
    	{
    		std::cout << it->at( 0 ) << it->at( 1 ) << it->at( 2 )  << std::endl;
    	}
    

  • Mod

    Ein kleiner Besuch bei Bit Twiddling Hacks:
    http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation

    Bringt uns zu folgendem Code, der als Inspiration dienen soll:

    #include <iostream>
    #include <bitset>
    
    using namespace std;
    
    unsigned long long binomial(unsigned n, unsigned k)
    {
      if (k > n) return 0;
      unsigned result = 1;
      for (unsigned d=1; d <= k; d++) {
        result *= n--;
        result /= d;
      }
      return result;    
    }
    
    unsigned long long next_permutation(unsigned long long v)
    {
      unsigned long long t = (v | (v - 1)) + 1;  
      return t | ((((t & -t) / (v & -v)) >> 1) - 1);
    }
    
    int main()
    {
      const unsigned n = 5;
      const unsigned k = 3;
    
      unsigned long long permutation = (1 << k) - 1;
    
      for (unsigned int i = 0; i < binomial(n,k); ++i)
        {
          bitset<n> foo(permutation);
          cout << foo << '\n';
          permutation = next_permutation(permutation);
         }
    }
    

    http://ideone.com/2S7hkH

    Die Verbindung zu deinen Mengen bekommst du bestimmt selber hin. Unangenehm wird es, wenn die Grundmenge größer wird als sizof(long long)*CHAR_BIT (also in der Regel 64). Dann musst du den next_permutation Hack auf einen Typen mit höherer Genauigkeit übertragen.



  • Genau so hatte ich das gedacht SeppJ. Danke an alle die geholfen haben. Kann jetz closed werden.

    Gruß
    yihaaa


Log in to reply