Dynamische for Verschachtelung: alle Permutationen [alle Kombinationen v. Schwellwerten für d. Krit]
Hallo liebe Gemeinde,
ich habe folgende Anforderung und bin etwas ratlos.
id wert kriterium 1 kriterium 2 …
1 500 0.456 4354 …
2 616 0.266 444 …
3 234 0.836 556 …
4 543 0.3456 322 …
5 -55 0.1356 68 …
… … … … …
Ich habe eine Liste mit Werten und Kriterien. Von den Kriterien habe ich jeweils das Maximum. Die Kriterien sind alles double Zahlen und positiv.
Ich möchte die Werte addieren, wenn die Kriterien erfüllt sind. Ziel ist die Maximierung der Wert-Addition.
Es ist sicherlich möglich bei 2-3 Kriterien noch for-schleifen zu bauen, aber das ist weder dynamisch noch handhabbar.
wertSum = 0;
for (i = 0.001 bis krit1 max i++) {
for (j = 0 bis krit2 max j++) {
for (id=1 bis idmax id++)
wenn (krit1 < i) {
wenn (krit2 < j) {
wertSum += wert[id]
}
}
}
}
}
Die Komplexität ist aber iwann sinnfrei. dass mus doch einfacher gehen.
also ich hatte an iwas gedacht wie:
SummenRechner.Init(Liste von oben) - die soll aber auch dynamisch sein, weil zusätzl. Kriterien mgl.
SummenRechner.Add(krit1, 0,001, kritMax, kritErhöhungsSchritt als wert= also das i++)
...
Problem ist, dass ich mir etwas vorstellen kann in dem Kontext, aber nicht die Umsetzung der verschachtelung.
Habt Ihr ne Idee?
Hallo stephan.opitz,
ich sehe nicht, wo bei dir die Permutationen ins Spiel kommen. So wie ich es verstanden habe, willst du die Werte summieren, bei denen alle Kriterien erfüllt sind, also pseudocodemäßig ungefähr so:
wertSum = 0;
foreach (var id in ids) {
alleKritErfuellt = true;
for (int i = 0; i < numKrit; ++i) {
if (krit [id] [i] > max [i]) {
alleKritErfuellt = false;
break;
}
if (alleKritErfuellt) {
wertSum += wert[id];
}
}
Falls du doch Permutationen (oder Kombinationen) meinst siehe Anzahl und Berechnung möglicher Kombinationen und Permutationen [inkl. Code-Snippets].
herbivore
Hallo,
also worum es mir eigentlich geht ist die Summe des Wertes gesehen über alle Positionen. & die soll so hoch wie möglich sein. wenn bestimmte Kriterien nicht erfüllt sind, addiert er den Positionswert nicht mit rein.
Grundsätzlich ist es doch aber eine && Geschichte.
wenn Kriterium1 < i hat && Kriterium 2 < j hat
du durchläufst die Schleife einfach ohne verschachtelnd, oder?
da er bei dir immer die Schleife durchgeht, ist es zwar für ein Kriterium wahr, aber nicht in Kombination mit anderen.
evtl war mein for schleifen Ansatz oben auch falsch.
Gruß
Solche Kriterien kannst Du doch enorm einfach mit Linq und dem entsprechenden Where() bilden bzw. jeweils anhängen.
list.Where(xx).Where.(xxx)
if( any )
{
list = list.Where(xxx)
}
Einfach mal Linq 101 Samples durcharbeiten, da ist das mit ein Lernpunkt.
- performance is a feature -
Microsoft MVP - @Website - @AzureStuttgart - github.com/BenjaminAbt - Sustainable Code
Hallo stephan.opitz,
deine Beschreibung kommt mir sehr konfus vor. Ich habe immer noch nicht verstanden, was du willst. Vielleicht ist das sogar schon das Problem, dass du es selber nicht genau weißt. Falls nicht, dann schreibe doch noch mal ganz genau, was wann wie und warum addiert werden soll. Versetze dich dabei in jemanden, der keine Ahnung hat, was du treibst und was du willst.
herbivore
Hallo,
ich habe es für 2 for schleifen mal gelöst, aber wenn da noch mehr dazu kommen, dann wirds kompliziert. Rekursion ist glaube ich auch nicht die Lösung. & Linq.Where() m.E. nach auch nicht.
Mein Problem ist die verschachtelte if ((firstCurrCondition ≤ i) && (secondCurrCondition ≤ j)) Bedingung. Evtl seh ich es auch einfach nur nicht
using System.Collections.Generic;
using System.Linq;
namespace Test
{
public class Position
{
public Position()
{
ConditionAtomList = new List<ConditionAtom>();
}
public int PositionId { get; set; }
public decimal Value { get; set; }
public List<ConditionAtom> ConditionAtomList { get; set; }
}
public class ConditionAtomBorder
{
public ConditionAtomBorder()
{
MinValue = decimal.MaxValue;
MaxValue = decimal.MinValue;
}
public string Name { get; set; }
public decimal MinValue { get; set; }
public decimal MaxValue { get; set; }
public decimal IncreaseValue { get; set; }
}
public class ConditionAtom
{
public string Name { get; set; }
public decimal CurrValue { get; set; }
}
public class ConditionResult
{
public decimal Sum { get; set; }
public List<ConditionAtom> ConditionAtomList { get; set; }
}
public class ConditionCombinations
{
public List<ConditionResult> Exec()
{
// test positions
var positionList = new List<Position>
{
new Position
{
PositionId = 0,
Value = 10.0m,
ConditionAtomList = new List<ConditionAtom>
{
new ConditionAtom
{
Name = "Cond1",
CurrValue = 0.1m
},
new ConditionAtom
{
Name = "Cond2",
CurrValue = 0.8m
}
}
},
new Position
{
PositionId = 1,
Value = 15.0m,
ConditionAtomList = new List<ConditionAtom>
{
new ConditionAtom
{
Name = "Cond1",
CurrValue = 0.3m
},
new ConditionAtom
{
Name = "Cond2",
CurrValue = 0.10m
}
}
},
new Position
{
PositionId = 2,
Value = -5,
ConditionAtomList = new List<ConditionAtom>
{
new ConditionAtom
{
Name = "Cond1",
CurrValue = 0.1m
},
new ConditionAtom
{
Name = "Cond2",
CurrValue = 0.11m
}
}
}
};
// get atom names once
var atomNameList = new List<string>();
if (positionList.Count > 0)
{
atomNameList = positionList[0].ConditionAtomList.Select(conditionAtom => conditionAtom.Name).ToList();
}
// fill borders
var conditionAtomBorderList = new List<ConditionAtomBorder>();
foreach (var name in atomNameList)
{
var conditionAtomBorder = new ConditionAtomBorder
{
Name = name,
IncreaseValue = 0.1m
};
foreach (var conditionAtom in
from position in positionList
from conditionAtom in position.ConditionAtomList
where conditionAtom.Name == conditionAtomBorder.Name
select conditionAtom)
{
conditionAtomBorder.MinValue = (conditionAtom.CurrValue < conditionAtomBorder.MinValue) ? conditionAtom.CurrValue : conditionAtomBorder.MinValue;
conditionAtomBorder.MaxValue = (conditionAtom.CurrValue > conditionAtomBorder.MaxValue) ? conditionAtom.CurrValue : conditionAtomBorder.MaxValue;
}
conditionAtomBorderList.Add(conditionAtomBorder);
}
// find all combinations & return sum for each
var resultList = new List<ConditionResult>();
for (var i = conditionAtomBorderList[0].MinValue;
i <= conditionAtomBorderList[0].MaxValue;
i += conditionAtomBorderList[0].IncreaseValue)
{
for (var j = conditionAtomBorderList[1].MinValue;
j <= conditionAtomBorderList[1].MaxValue;
j += conditionAtomBorderList[1].IncreaseValue)
{
var sum = 0.0m;
foreach (var position in positionList)
{
var query = from myObject in position.ConditionAtomList
where myObject.Name == conditionAtomBorderList[0].Name
select myObject;
var conditionAtom = query.FirstOrDefault();
decimal firstCurrCondition = 0;
if (conditionAtom != null)
{
firstCurrCondition = conditionAtom.CurrValue;
}
query = from myObject in position.ConditionAtomList
where myObject.Name == conditionAtomBorderList[1].Name
select myObject;
conditionAtom = query.FirstOrDefault();
decimal secondCurrCondition = 0;
if (conditionAtom != null)
{
secondCurrCondition = conditionAtom.CurrValue;
}
if ((firstCurrCondition <= i) && (secondCurrCondition <= j))
{
sum += position.Value;
}
}
var listConditionAtom = new List<ConditionAtom>
{
new ConditionAtom
{
Name = conditionAtomBorderList[0].Name,
CurrValue = i
},
new ConditionAtom
{
Name = conditionAtomBorderList[1].Name,
CurrValue = j
}
};
resultList.Add(new ConditionResult { Sum = sum, ConditionAtomList = listConditionAtom });
}
}
return resultList;
}
}
}
LG
Hallo stephan.opitz,
jetzt habe ich zumindest verstanden, was du willst. Ich habe deine Beschreibungen weiter oben erneut gelesen und daraus ist mit keinem Wort zu erkennen, dass du die Summen für alle Kombinationen aus Schwell- bzw. Grenzwerten für die einzelnen Kriterien haben willst.
Kombinationen übrigens, nicht Permutationen.
Du sagst, die Kriterien sind bei dir double-Werte. Genau genommen wäre das Kriterium das Ergebnis des Vergleichs eines solchen double-Werts mit einem Schwellwert, aber das nur nebenbei. Ich bezeichne weiter die (einzelnen) Double-Werte als Kriterium (bzw. die Liste aller doube-Werte einer Kriteriumspalte). Es ist dann eben erfüllt, wenn es kleiner ist als der aktuelle Schwellwert.
Zunächst würde ich nicht mit einem festen IncrementValue arbeiten. Änderungen in der Summe treten nur auf, wenn der aktuelle Schwellwert den nächsthöheren Wert des Kriteriums annimmt. Du musst also als Vergleichswerte (im deinem Code ungünstigerweise i und j genannt) nur die tatsächlich in den jeweiligen Kriterium vorkommenden Werte verwenden - und zusätzlich noch einen Wert, der kleiner ist als alle Werte aus dem Kriterium.
Wenn AnzahlSchwellwerte(krit i) die Anzahl der unterschiedliche Werte ist, die in Kriterium i vorkommen, plus eins für den zusätzlichen untersten Schwellwert, dann ist die Anzahl der möglichen Kombinationen:
AnzahlSchwellwerte(krit 1) * AnzahlSchwellwerte(krit 2) * ... AnzahlSchwellwerte(krit n)
Das kann man natürlich rekursiv genau so lösen, wie in dem verklinkten Thread beschrieben, nur dass als "Alphabet" nicht eine Menge von Buchstaben ach übergeben wird, sondern eine Menge von Schwellwerte für das der Rekursionsebene entsprechenden Kriterium. Und dass nicht die Buchstaben zu einem String zusammengefügt werden, sondern erst auf der untersten Rekursionsebene die Summe berechnet wird. Damit man immer weiß, auf welcher Rekursionsebene man sich befindet, kann man statt iLen besser iLevel verwenden.
Für jemanden, der Rekursion beherrscht und auch sonst halbwegs programmieren kann, ist die Umsetzung nach dieser Beschreibung eine reine Fleißaufgabe. Die Frage selbst fällt sicher nicht unter Grundlagen, aber die Umsetzung der Lösungsskizze ist bei Kenntnis der betreffenden Grundlagen ohne Weiteres möglich. Bitte beachte von daher vorsorglich [Hinweis] Wie poste ich richtig? Punkt 1.1.1.
herbivore
Hallo liebe Gemeinde,
da ich immer noch eine brauchbare Lösung benötigte, habe ich etwas weiter probiert & eine Lösung für mich gefunden. Im Wesentlichen geht es um die Definition der For-Loops als ConditionAtomBorder & dem Aufruf via DoLoop.
Meinen Anforderungen genügt es damit:
public class ConditionAtomBorder
{
public ConditionAtomBorder()
{
MinValue = decimal.MaxValue;
MaxValue = decimal.MinValue;
}
public string Name { get; set; }
public decimal MinValue { get; set; }
public decimal MaxValue { get; set; }
public decimal IncreaseValue { get; set; }
public decimal CurrIdxValue { get; set; }
}
public class NestedForLoop
{
public readonly List<ConditionAtomBorder> ListConditionAtomBorder = new List<ConditionAtomBorder>();
public NestedForLoop()
{
ListConditionAtomBorder.Add(new ConditionAtomBorder
{
Name = "value1",
MinValue = 0,
MaxValue = 5,
IncreaseValue = 1
});
ListConditionAtomBorder.Add(new ConditionAtomBorder
{
Name = "value2",
MinValue = 2,
MaxValue = 6,
IncreaseValue = 1
});
/*
ListConditionAtomBorder.Add(new ConditionAtomBorder
{
Name = "value3",
MinValue = 50,
MaxValue = 52,
IncreaseValue = 1
});
*/
}
public void DoLoop()
{
Call(ListConditionAtomBorder, -1);
}
public static void Call(List<ConditionAtomBorder> list, int deepLvl)
{
deepLvl++;
if (deepLvl == list.Count)
{
// deep condition - do some stuff here
return;
}
// recursive call
var atomBorder = list[deepLvl];
var realDeepLvl = list.IndexOf(atomBorder); // current deep level
for (var i = atomBorder.MinValue; i < atomBorder.MaxValue; i += atomBorder.IncreaseValue)
{
Console.WriteLine(atomBorder.Name + " - i: " + i + " - deepLvl: " + realDeepLvl);
atomBorder.CurrIdxValue = i; // set curr value
Call(list, realDeepLvl);
}
}
In der Liste habt Ihr jederzeit Zugriff auf die aktuellen Werte über CurrIdxValue.
Viel Spass damit.