permutationen zählen

ich möchte zählen, wie viele zahlenkombinationen es bei einem lotto-ähnlichen spiel gibt.
zählen bedeutet, dass ich nicht den binomialkoeffizienten ${49 \choose 6}$ ausrechnen will, sondern alle kombinationen von 6 aus 49 zahlen erzeugen und zählen möchte.

kann mir jemand einen tipp geben, wie ich die gültigen kombinationen möglichst effizient erzeugen kann, und dabei alle logisch gleichwertige kombinationen (1, 2, 3, 4, 5, 6 und 6, 3, 4, 1, 2, 5 sind gleichwertig) ignoriert werden?

ich kenne std::next_permutation und std::prev_permutation, weiß aber nicht wie ich das in diesem fall effizient einsetzen kann. einfach alle permutationen der 49 zahlen zu berechnen und nur einen teil davon zu betrachen erscheint mir äußerst ineffizient.

Fellhuhn

Die tollen Variablennamen sind übrigens Absicht.

Aber das willst du nicht ausführen das Programm. Das bringt nichts. Du willst die Werte auch nirgends speichern. Bringt auch nichts.

#include <vector>
#include <iostream>

using namespace std;

int main(){
    vector<int> zahlen;
    for(int i = 1; i < 49; i++) zahlen.push_back(i);

    for(int i = 0; i < zahlen.size() - 5; i++)
	for(int ii = i+1; ii < zahlen.size() - 4 && i != ii; ii++)
	    for(int iii = ii+1; iii < zahlen.size() - 3 && ii != iii && iii != i; iii++)
		for(int iv = iii+1; iv < zahlen.size() - 2 && iv != iii && iv != ii && iv != i; iv++)
		    for(int v = iv+1; v < zahlen.size() - 1 && v != iv && v != iii && v != ii && v != i; v++)
			for(int vi = v+1; vi < zahlen.size() && vi != v && vi != iv && vi != iii && vi != ii && vi != i; vi++)
			cout << zahlen[i] << " " 
			     << zahlen[ii] << " "
			     << zahlen[iii] << " "
			     << zahlen[iv] << " "
			     << zahlen[v] << " "
			     << zahlen[vi] << endl;
}

Willst du nur die Anzahl der möglichen Lösungen haben?
49! / 43! / 6! wenn ich nicht irre.

hallo, so in der richtung habe ich mir auch schon was gedacht. ein wenig mehr flexibilität wäre aber besser, weil ich nicht nur 6 aus 49 ausrechnen will.

Fellhuhn schrieb:

Willst du nur die Anzahl der möglichen Lösungen haben?

nein, das ist ja einfach.

49! / 43! / 6! wenn ich nicht irre.

http://www.google.de/search?q=49+choose+6

Fellhuhn

Ist ja identisch.

Nun, aber du willst über 16 Millionen mögliche Lösungen haben? Wofür? Also was willst du anschließend damit machen?

pumuckl

Wenn du nur die Kombinationen der 6 ueber 49 Zahlen zaehlen willst, rechnest du im Grunde den Binomialkoeffizienten aus.
Wenn du die Kombinationen selbst haben moechtest, wirds etwas komplizierter. Ich schreib mal die Kombinationen von 3 aus 5 auf, das sind nur 10, aber man kann meinen folgenden Gedankengang daran nachvollziehen. Um nicht staendig latex benaspruchen zu muessen nenn ich den binomialkoeffizienten n ueber k im Folgenden bkoeff(n,k)

321  - 1. Komb.  
421                  
431
432  - 4. Komb.
521
531
532
541
542
543  - 10. Komb.

Es faellt auf, dass die 1,4 und 10 genau bkoeff(3,3), bkoeff(4,3) und bkoeff (5,3)

Folgender Code fuellt mir einen vector mit der x-ten Kombination von k aus n:

void kombi(int n, int k, int x, std::vector<int>& vec) {
  assert(0<k && k<=n && x<=bkoeff(n,k));
  if(k==1) {
    vec.push_back(x);
    return;
  }
  if(x==1) {
    while(k>0) vec.push_back(k--); //erste Kombination ist einfach
    return;
  }
  int number = k;
  int koeff = 1;
  int tmp;
  while ((tmp = bkoeff(number,k)) < x) {
    ++number;
    koeff = tmp;
  }
  vec.push_back(number);
  kombi(number-1,k-1,x-koeff,vec);
}

Aufruf dann wie folgt:

std::vector<int> v;
kombi(5,3,3,v); //in v steht jetzt 431

/edit: zwei returns vergessen...

es geht um spiele mit computergegnern, die die aktuelle spielsituation bewerten sollen. um verschiedene lösungsmöglichkeiten auf korrektheit zu prüfen, möchte ich sie mit brute-force methoden testen. die paar millionen zahlen sollten sich ja recht fix testen lassen - kann ruhig auch mal eine nacht oder zwei dauern.

@pumuckl: das funktioniert sehr gut, danke! ist auch ziemlich schnell , mit einer kleinen optimierung über 250.000 kombinationen pro sekunde auf meinem rechner.

pumuckl

noch ne kleine Modifikation (falls vector der flaschenhals ist), funktioniert dann auf jedem beliebigen Container (zur Not auch auf arrays)

template<class Iter>
void kombi(int n, int k, int x, Iter it) {
  assert(0<k && k<=n && x<=bkoeff(n,k));
  if(k==1) {
    *it = x;
    return;
  }
  if(x==1) {
    *it = k;
    while(k>1) *(++it) = --k; //erste Kombination ist einfach
    return;
  }
  int number = n;
  int koeff = 1;
  while (x <= (koeff = bkoeff(number-1,k))) {
    --number;
  }
  *it = number;
  kombi(number-1,k-1,x-koeff,++it);
}

/edit: noch eine kleine Aenderung: number von oben runter zaehlen statt von unten hoch.

mit diesem algorithmus und einer lut für bkoeff kann ich nun auf meinem rechner alle 13.983.816 kombinationen in weniger als 4 sekunden ausrechnen - das sind über 3.500.000 kombinationen pro sekunde.

das ist sehr viel mehr als ich erwartet hätte.

falls es jemanden interessiert:

static int bcoeff_table[128 * 128];

inline int compute_coeff(int n, int k)
{
	if(k == 0)
		return 1;

	if(k * 2 > n)
		return compute_coeff(n, n - k);

	int result = n;
	for(int i = 1; i < k; ++i)
		result = (result * (n - i)) / (i + 1);

	return result;
}

void compute_coeff_table()
{
	for(int i=1; i < 128; ++i)
		for(int j = 1; j < 128; ++j)
			bcoeff_table[i*128+j] = compute_coeff(i, j);
}

inline int bkoeff(int n, int k)
{
        assert(n < 128 && k < 128);
	return bcoeff_table[n*128+k];
}

void kombi(int n, int k, int x, int* vec)
{
	assert(0 < x && 0 < k && k <= n && x <= bkoeff(n,k));

	if(k==1)
	{
		*vec = x;
		return;
	}

	if(x==1) 
	{
		while(k > 0)
			*(vec++) = k--;
		return;
	}

	int number = k;
	int koeff = 1;
	int tmp;
	while((tmp = bkoeff(number,k)) < x) 
	{
		++number;
		koeff = tmp;
	}

	*vec = number;
	kombi(number-1, k-1, x-koeff, ++vec);
}

void testkombis()
{
	static const int n = 49;
	static const int k = 6;

	compute_coeff_table();
	int limit = bkoeff(n, k);
	std::cout << "kombis: " << limit << std::endl; 

	DWORD start = GetTickCount();

	int out[k];
	std::fill(&out[0], &out[k-1], 0);	
	for(int i=1; i <= limit; ++i)
	{
		kombi(n, k, i, out);
		/*if((i & 0xfffff) == 0)
			std::cout << i << std::endl;
		for(int j=0; j<k; ++j)
			std::cout << out[j] << " ";
		std::cout << std::endl;*/
	}
	DWORD end = GetTickCount();
	std::cout << limit << " kombis in " << (end-start) << " ms" << std::endl;
}

int main()
{
	testkombis();
}

.filmor

Um ohne Tabelle auszukommen (oder die Tabelle schneller zu berechnen) ist vielleicht ganz praktisch, dass bin(n, k) = n / (n - k) * bin(n - 1, k) ist.

pumuckl

ganz schnell gehts mit

void compute_coeff_table()
{
    for(int n=0; n < 128; ++n) bcoeff_table[i] = 1; //bin(n,0) = 1
    for(int k=1; k < 128; ++k) 
      for(int n=k; n < 128; ++n)
        bcoeff_table[n+128*k] = bcoeff_table[n-1+128*k] + bcoeff_table[n-1+128*(k-1)];
}

inline int bkoeff(int n, int k)
{
        assert(n < 128 && k < 128);
    return bcoeff_table[n+k*128];
}

ergibt

n-->
k 1 1 1 1 1 1 1 ...
| 0 1 2 3 4 5 6 ...
| 0 0 1 3 6 
v 0 0 0 1 4 
  0 0 0 0 1