Integer-Partitionierung und Entscheidungstabelle generieren

22/06/2008 - 08:26 von ET | Report spam
Angewandte Mathematik und Programmierung

Thema:
Integer-Partitionierung und Entscheidungs- bzw. Wertetabelle generieren.

Aufgabe:
Es ist programmatisch eine Entscheidungstabelle effizient zu generieren.
Es handelt sich durchweg nur um die Menge der natürlichen
Zahlen >= 0, also um Integerwerte.
Es geht darum, einen Wert (v) in einer Schleife (oder mehreren Schleifen)
in 6 Teile zu splitten (A,a,B,b,C,c; siehe unten) und alle möglichen
Kombinationen effizient zu ermitteln. D.h. es sollten unnötige
Schritte (insb. Schleifendurchlàufe und Abfragen) nach Möglichkeit
vermieden bzw. minimiert werden.

Inputwerte (hier nur Beispielwerte):
k = 5 (k ist immer > 0)
v = 30 (v ist immer > k)

Die zu generierende Tabelle hat 8 Spalten:
A a B b C c D d <-- Spalten-Name
[0] [1] [2] [3] [4] [5] [6] [7] <-- Element-Index

Bei den Spalten mit den Kleinbuchstaben handelt es sich um boolsche Werte (0/1).

Die Regeln:
1.) A kann Werte 0 bis k haben
2.) a+b+c muss immer 1 ergeben
3.) Die Summe A+a+B+b+C+c muss v ergeben
Natürlich impliziert dies u.a. folgendes:
A=v-a-B-b-C-c
B=v-A-a-b-C-c
C=v-A-a-B-b-c
4.) D=A+B
5.) d=a+b

Man kann A+a+B+b (entspricht D+d) als Hauptgruppe ansehen
und C+c als die Restgruppe (von v).
Ziel ist alle Hauptgruppen zu ermitteln, wobei dann die Werte
der jeweiligen Restgruppe natürlich automatisch auch stimmen.

Das Ziel:
Alle möglichen Kombinationen, die diese Regeln erfüllen
in kleinstmöglicher Anzahl von Schritten (Schleifendurchlàufen)
finden und tabellarisch auflisten, bzw. eine 2-dim array damit füllen.
Es dürfen natürlich keine Reihenduplikate vorkommen.
Die Methode muss für jedes gültige Inputpaar v,k funktionieren,
mindestens bis k0 und vP0, wobei wie gesagt gilt 0<k<v,
oder anders gesagt v>k>0.

Zusatzoption:
Wenn es direkt machbar ist, so sollte die Tabelle implizit
nach den beiden Spalten D und d (als Einheit) aufsteigend
(oder absteigend) sortiert sein. Ansonsten muss man es
entsprechend sortieren durch einen, leider kostspieligen,
sort()-Aufruf. Also, nach Möglichkeit den sort()-Aufruf einsparen
und stattdessen versuchen die Tabelle entsprechend
irgendwie intelligent zu generieren.

Lösungsvorschlàge:
Sollten in Standard-Pseudocode sein, wobei alles 0-basiert sein
sollte (d.h. Indices sollten bei Element 0 beginnen und nicht
wie in einigen Sprachen üblich bei 1).
Eine direkte Lösung in Standard C ist auch OK.
D.h. die Spalten kann man auch als Vektor-Element ansehen
und ansprechen; z.B. wàre Spalte b gleich Element 3 (vgl. oben).
ABER: es gibt meines Wissens keine Formel um die Anzahl
der gültigen Möglichkeiten vorweg auszurechnen (müsste man auch
noch ermitteln falls für die Lösung der Aufgabe unbedingt nötig).
Also, es muss nicht unbedingt in einem Vektor bzw. Array realisiert werden,
es kann auch einfach zeilenweise ausgeprinted werden.

Viel Spass
 

Lesen sie die antworten

#1 karl
22/06/2008 - 09:21 | Warnen spam
ET schrieb:


es kann auch einfach zeilenweise ausgeprinted werden.



^^^^^^^^^^^^
Dödel.

Ähnliche fragen