Algorithmus fuer Kombinationen

Typ222

Also ich brauche einen Algorithmus der mir alle moeglichen Kombinationen bis zu einem bestimmten Wert liefert!
z.B. Der max Wert soll 11 sein und array mit Werten {4, 3, 5} soll folgendes liefern:
4, 4, 3
4, 3, 3
3, 4, 4
3, 3, 5
3, 3, 3
3, 4, 3
5, 4
5, 3, 3
(Hoff ich hab alle)

Also bisher hab ich sowas:

int arr[4] = {2, 1, 6, 3};
	int value = 0;
	int tmpV = 0;

	for (int i=0; i<c; i++) {
		value += arr[i];
		tmpV = value;
		std::cout << arr[i] << " " << arr[i] << " ";

		for (int k=0; k<c; k++) {
			if ((value + arr[k]) <= summationsLength) {
				value += arr[k];
				tmpV = value;
				std::cout << arr[k] << " " << arr[k] << " ";
			}

			for (int j=k; j<c; j++) {
				if ((value + arr[j]) <= summationsLength) {
					value += arr[j];
					std::cout << arr[j] << " " << arr[j] << " ";
				}
			}
			value = tmpV;
		}
		value = 0;
		std::cout << std::endl;
	}

Leider funktioniert der nicht wirklich korrekt, weis vlt wer ne Loesung??

SeppJ

http://www.cplusplus.com/reference/algorithm/next_permutation/

Typ222

Aber dadurch wuerd ich die Ausgabe
5,4
nicht erhalten...

SeppJ

Typ222 schrieb:

Aber dadurch wuerd ich die Ausgabe
5,4
nicht erhalten...

Ehrlich gesagt verstehe ich auch nicht, wie die 5,4 bei dir ins Schema passt (oder nach welchem Schema dein Beispiel überhaupt aufgebaut ist). Wenn Leerstellen auch erlaubt sind, dann für deiner Grundmenge eben noch Leerstellen hinzu.

Typ222

Es geht nicht um die Leerstellen sondern um die Ausgabe der Menge!
Es sollten ALLE MOEGLICHEN Kombinationen ausgegeben werden die in Summe den Maximalwert (z.B. 11) ergeben!

P.S.
Sorry hab ein Paar vergessen:
4, 3, 4
3, 3, 4
5, 5

Bashar

Das schreit nach Rekursion.

Typ222

Hat da vlt wer ne Idee mit der Rekursion blick da im Moment nicht ganz durch...

icarus2

Hab kurz was gecoded.

#include <iostream>
using std::cout;
using std::endl;

const int Elements = 3; // Amount of elements
const int const values[] = {3, 4, 5}; // Values to build a combination
int combination[3] = {0}; // Temporary combination
int combination_count = 0;

// Print a combination
void print_combination()
{
	for( int i = 0; i < Elements; i++ )
		cout << combination[i];
	cout << endl;
}

// Caluclates recursively all combinations of the array elements stored in 'values'. (Must start with 0).
void combinations( int position )
{
	// For each position loop through all possible elements
	for( int i = 0; i < Elements; i++ )
	{
		combination[position] = values[i];

		// Last position reached? If so print and increase count
		if ( position == Elements - 1 )
		{
			print_combination();
			combination_count++;
		}
		// Move to the position further right in the array
		else
			combinations( position + 1 ); // Recursive call
	}
}

int main()
{
	combinations( 0 );
	cout << endl << "Combinations: " << combination_count << endl << endl;
}

Gibt alle möglichen Kombination aus. Du kannst noch selber eine Funktion schreiben, die überprüft, dass die Sumem der Elemente kleiner als 11 ist.

Interessant sollte vor allem die Funktion combinations sein. Du kannst dann das ganze natürlich noch etwas flexibler programmieren. Im Moment ist alles ziemlich statisch.

PS:
Du kannst mit dieser Methode beliebig grosse Mengen nehmen für die Kombinationen. Du musst einfach die Konstante und die Längen der beiden Arrays anpassen.

*Edit
Sry wegen den englischen Kommentaren. Hoffe das macht dir nix aus. Habs aus Gewohnheit auf englisch gemacht.

Bashar

Typ222 schrieb:

Hat da vlt wer ne Idee mit der Rekursion blick da im Moment nicht ganz durch...

Aus deiner Erklärung geht nicht ganz hervor, was für dich alle Kombinationen sind. Du sagst, dass der Maximalwert nicht erreicht werden muss, so dass z.B. 5, 4 gültig ist, obwohl die Summe nur 9 statt 1 ist. OK, also alle Kombinationen, deren Summe 11 nicht übersteigt. Aber warum ist dann 5 nicht in deiner Aufzählung dabei? Ich vermute, du suchst alle maximalen Kombinationen, deren Summe kleiner gleich einem bestimmten Maximalwert ist.

Ich hab die Idee mit der Rekursion hier mal ausprogrammiert:

void print_combinations_max(vector<int> const& values, int start,
			    vector<int>& work, int max_sum) {
  bool is_maximal = true;

  for (int i = start, n = values.size(); i < n; ++i) {
    int x = values[i];
    if (x <= max_sum) {
      is_maximal = false;
      work.push_back(x);
      print_combinations_max(values, start, work, max_sum - x);
      work.pop_back();
    }
  }

  if (is_maximal) {
    for (int i = 0, n = work.size(); i < n; ++i)
      cout << work[i] << " ";
    cout << '\n';
  }
}

Aufruf:

int valuesArray[] = {4, 3, 5};
const int nValues = sizeof(valuesArray) / sizeof(valuesArray[0]);

vector<int> values(valuesArray, valuesArray + nValues);
vector<int> work;

print_combinations_max(values, 0, work, 11);

Ausgabe:

Zur Erkärung:
Rekursion braucht immer einen Basisfall und eine Regel, wie ein komplizierter Fall auf einen einfacheren Fall reduziert werden kann, so dass irgendwann der Basisfall erreicht wird. In diesem Fall lässt sich die Aufgabe, alle Kombinationen aus einer Menge {a₁, a₂, ..., a_n} bis zu einer Maximalsumme M zu finden folgendermaßen auf kleinere Aufgaben zurückführen: Für a₁ bis a_n bildet man jeweils alle Kombinationen bis zu einer nicht-negativen Maximalsumme von M - a_i und hängt a_i davor. Der Basisfall ergibt sich automatisch dadurch, dass das nicht möglich ist, wenn M - a_i irgendwann negativ wird.