[C++] k elementig Teilmengen ausgeben

yihaaa

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

Skym0sh0

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.

yihaaa

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;
	}

SeppJ

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.

yihaaa

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

Gruß
yihaaa