Matrix aus Vektoren - Kombinationen generieren

happystudent

Hallo,

angenommen ich habe eine (quadratische) Matrix aus Vektoren. Für diese Matrix soll vom Benutzer die Größe (also das n der nxn-Matrix) vorgegeben werden sowie die maximale Vektoren-Länge minus 1 (nennen wir mal k).

Was ich jetzt bräuchte ist eine Funktion, die mir aus diesen Werten alle Kombinationsmöglichkeiten, die Matrix zu befüllen, generiert. Also etwa so:

#include <boost\numeric\ublas\matrix.hpp>

using stack_matrix = boost::numeric::ublas::matrix < std::vector<int> > ;

std::vector<stack_matrix> generate_stack_matrices(size_t matrix_size, size_t max_stack_size)
{
	std::vector<stack_matrix> result;
	// Implementierung ...
	return result;
}

int main()
{
	auto matrices = generate_stack_matrices(3, 2);
	// Mach irgendwas damit
}

Hier sind die Werte n = 3 und k = 2. Also ist die Matrix eine 3x3 Matrix und die Vektoren haben maximal eine Länge von 2 + 1 = 3.

Für die Vektoren gilt zusätzlich, dass sie

Entweder leer
Oder nur positive (mit 0) integer Werte enthalten, wobei der größte Wert höchstens gleich der Vektor-Länge ist
Und zusätzlich sortiert sind (im ersten Index die kleinste, im höchsten die größte Zahl steht)
Keine Duplikate enthalten

Für ein k = 2 wären also gültige Vektoren:

v1 = [] // Leer
v2 = [0, 1, 2] // Sortiert, maximale Länge ist k + 1, also 3
v3 = [0, 2] // Lücken sind zulässig
v4 = [2] // Auch zulässig

ungültige Vektoren wären dagegen:

v1 = [3] // Wert ist größer als k
v2 = [2, 1] // Nicht (bzw. falsch) sortiert
v3 = [1, 1, 2] // Duplikate sind nicht erlaubt
v4 = [-1] // Negative Werte nicht erlaubt
v5 = [0, 1, 2, 3] // Vektor zu lang, maximale Länge ist 3

Was ich jetzt brauche, ist eine möglichst effiziente Implementierung die alle nur möglichen Matrizen für die Nutzer-Vorgaben generiert. Also alle Kombinationsmöglichkeiten für alle Vektoren die die oben genannten Bedingungen erfüllen.

Da das ziemlich kompliziert und (vermutlich) auch sehr rechenaufwendig wird, wollte ich hier mal um Tipps etc. fragen wie man das am besten angehen könnte. Und ob es da vielleicht schon (zumindest teilweise) fertige Sachen in der STL gibt die man verwenden könnte?

SeppJ

Du bist doch jetzt schon eine ganze Weile beim Programmieren, irgendwie kann ich kaum glauben, dass du das nicht selber hin bekämst, wenn du es nur mal versuchen würdest. Die naheliegenden Lösungen sind doch recht einfach und dürften allesamt ziemlich nahe an der effizientesten Lösung (welche auch immer das sein mag) liegen.

happystudent

SeppJ schrieb:

Du bist doch jetzt schon eine ganze Weile beim Programmieren, irgendwie kann ich kaum glauben, dass du das nicht selber hin bekämst, wenn du es nur mal versuchen würdest. Die naheliegenden Lösungen sind doch recht einfach und dürften allesamt ziemlich nahe an der effizientesten Lösung (welche auch immer das sein mag) liegen.

Naja, ich bräuchte halt sowas wie std::next_combination, was es ja leider nicht gibt so wie es aussieht... Deswegen wollte ich mal fragen obs was ähnliches dafür gibt. Hinkriegen werd ich das schon, will aber halt vermeiden "das Rad neu zu erfinden" wenn es da schon was geeignetes in std/boost gibt.