Liste - Zahlen ergänzen bzw. fehlende Zahlen erkennen

galagher · Verfasst: Sa 18.04.15 16:41

Hallo!

Ich habe eine ListBox mit Zahlen, zB:

Quelltext

1:
2:
3:

001
002
004

Ich möchte nun diese Liste durchlaufen und es soll dabei erkannt werden, dass 003 fehlt, dies soll in eine andere Liste geschrieben werden.
Es kann auch vorkommen, das zwei oder mehr Zahlen fehlen, auch das soll erkannt werden:

markieren

Quelltext

1:
2:
3:
4:

Alle fehlenden Zahlen möchte ich in einer anderen Liste haben, in diesem Beispiel also 011, 012, 013, dann ab 015 bis 020.

Ein Logikproblem, und ich komme auf keine Lösung!

_________________
gedunstig war's - und fahle wornen zerschellten karsig im gestrock. oh graus, es gloomt der jabberwock - und die graisligen gulpen nurmen!

Th69 · Verfasst: Sa 18.04.15 17:24

Hallo,

was ist daran so schwer? Wenn die Zahlen in der Liste sortiert sind (ansonsten eben zuvor sortieren), dann in einer Schleife jeweils zwei aufeinanderfolgende Zahlen vergleichen, und wenn die Differenz größer als 1 ist, dann die fehlenden Zahlen (wiederum eine Schleife) in die andere Liste schreiben.

Ralf Jansen · Verfasst: Sa 18.04.15 17:47

Die obligatorische, dem Verständnis nicht helfende, LINQ Antwort

markieren

C#-Quelltext

1:
2:

List<Int32> list = new List<int>() { 9, 10, 14, 21 }; // testDaten
List<Int32> missingValues = Enumerable.Range(list.Min(), list.Max() - list.Min() + 1).Except(list).ToList();

galagher · Verfasst: Sa 18.04.15 19:32

Th69 hat folgendes geschrieben :

was ist daran so schwer?

Es mir vorzustellen! :nixweiss:

Th69 hat folgendes geschrieben :

dann in einer Schleife jeweils zwei aufeinanderfolgende Zahlen vergleichen, und wenn die Differenz größer als 1 ist, dann die fehlenden Zahlen (wiederum eine Schleife) in die andere Liste schreiben.

Also zwei Schleifen, wobei die zweite, die schreibt, innerhalb der ersten liegt?

Ich gehe also von 0 bis Count-2, subtrahiere das jeweils nächste Item vom aktuellen Item, wenn > 1, schreibe Zahl. Das müsste ich dann in einer zweiten Schleife machen, ich weiss aber nicht, wie!

Ich schreibe die Zahlen erstmal sortiert in eine TStringList.
Aber so wird immer nur eine Zahl geschrieben, zwei fehlende nicht:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

for i := 0 to L.Count-2 do
begin
  if StrToInt(L[i+1]) - StrToInt(L[i]) > 1 then
  begin
    n := StrToInt(L[i])+1;
    L1.Add(IntToStr(n));
  end;
end;

_________________
gedunstig war's - und fahle wornen zerschellten karsig im gestrock. oh graus, es gloomt der jabberwock - und die graisligen gulpen nurmen!

Palladin007 · Verfasst: Sa 18.04.15 20:50

Warum so kompliziert mit Vergleichen von zwei Zahlen?
Es reicht doch schon, einfach hoch zu zählen und zu schauen, ob eine Zahl da ist oder nicht.

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

var list = new List<int>() { 1,5,8,4 };
var missingValues = new List<int>();

for (int i = list.Min() + 1; i < list.Max(); i ++)
{
    if (!list.Contains(i))
        missingValues.Add(i);
}

Natürlich muss die Ausgangsliste dazu ziemlich oft durchsucht werden.
Ich weiß nicht, wie performant das ist, wenn das ein Problem darstellen sollte, geht ja auch noch diese Möglichkeit:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

var list = new List<int>() { 1,5,8,4 };
var missingValues = new List<int>();

var number = list.Min();
for (int i = 0; i < list.Count; ) // beachte: hier steht kein i++
{
    number++;

    if (list[listIndex] == number)
        i++; // Das steht hier, damit erst das nächste Listen-Element betrachtet wird, wenn alle fehlenden Zahlen bis dahin erkannt wurden
    else
        missingValues.Add(number);
}

Das ist kein Delphy, ich hoffe, Du verstehst den Code trotzdem, ist nichts allzu kompliziertes dabei.
list.Min() und list.Max() geben den jeweils kleinsten bzw. höchsten Wert aus der Liste zurück, die restlichen Methoden decken sich glaube ich alle mit Delphy.
list.Min() und list.Max() kannst Du ja auch durch deinen Mindest- und Höchst-Wert ersetzen, z.B. 0 und 100.

Bei der Antwort von Ralph sieht das ja etwas anders aus

Enumerable.Range erstellt eine vollständige Zahlen-Liste im angegeben Bereich (durch list.Min() und list.Max() - 1 vorgegeben) und sucht anschließend mit Except(list) die Unterschiede zur Ausgangsliste heraus, was in diesem Fall die fehlenden Zahlen sind. Das ToList() am Ende steht dort, da viele LINQ-Methoden IEnumerable zurück geben, was grundsätzlich keine Liste ist und erst zu einer gemacht werden muss.

C# · Verfasst: Sa 18.04.15 20:57

So wie ich es verstanden habe, sind deine Zahlen als String vorhanden und nicht als Integer. Ich kann leider nur C#, ich hoffe ich habe den Code genug erklärt.

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:

 static void Main(string[] args)
        {
            List<string> sampleList = new List<string> {"001", "002", "004", "005", "008", "009", "015"};
            List<string> missingList = new List<string>();

            // jedes Element der Liste durchgehen   
            for (int i = 1; i < sampleList.Count; i++)
            {
                // die vorherige Zahl in der Liste ermitteln (untere Grenze)
                // int.Parse() wandelt den string in eine Zahl um
                int lower = int.Parse(sampleList[i - 1]);

                // die aktuelle Zahl ermitteln (obere Grenze)
                int upper = int.Parse(sampleList[i]);

                // da lower schon in der Liste vorkommt, wird es erst mal um 1 erhöht
                // falls lower dann immer noch kleiner als upper ist, wird es zur anderen Liste hinzugefügt
                // anschließend wird es wieder um 1 erhöht
                for (lower++; lower < upper; lower++)
                {
                    // fügt die fehlende Zahl im Format "000" (z.B. "003") hinzu
                    missingList.Add(string.Format("{0:000}", lower));
                }
            }

            
            Console.WriteLine("Original sample list:");
            foreach (string s in sampleList) Console.WriteLine(s);

            Console.WriteLine("\nMissing numbers:");
            foreach (string s in missingList) Console.WriteLine(s);

            Console.ReadKey();
        }

Die Ausgabe des Codes:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

Original sample list:
001
002
004
005
008
009
015

Missing numbers:
003
006
007
010
011
012
013
014

/// EDIT

Um Ralf zu ergänzen hier nochmal das gleiche in Linq:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

List<string> sampleList = new List<string> { "001", "002", "004", "005", "008", "009", "015" };
            List<string> missingList =
                Enumerable.Range(sampleList.ConvertAll(s => int.Parse(s)).Min(),
                    sampleList.ConvertAll(s => int.Parse(s)).Max() - sampleList.ConvertAll(s => int.Parse(s)).Min())
                    .Select(i => string.Format("{0:000}", i))
                    .Except(sampleList)
                    .ToList();

            Console.WriteLine("Original sample list:");
            foreach (string s in sampleList) Console.WriteLine(s);

            Console.WriteLine("\nMissing numbers:");
            foreach (string s in missingList) Console.WriteLine(s);

_________________
Der längste Typ-Name im .NET-Framework ist: ListViewVirtualItemsSelectionRangeChangedEventHandler

Palladin007 · Verfasst: Sa 18.04.15 21:51

Ich würde es mir da ja eher einfach machen und die Ausgangsliste in eine Int-Liste übertragen. Das lässt sich simpel mit einer Schleife lösen.
Der Rest danach ist so, wie vorher beschrieben.

Was .NET angeht:
Es gibt IComparer, dann erstelle ich mir eben einen IComparer, der strings als Zahlen behandelt und entsprechend vergleicht.
Ich meine, dass alle benötigten Methoden auch eine Überladung anbieten, die IComparer entgegen nimmt, oder zumindest eine Func, die entsprechendes erledigt.

Aber auch unter .NET würde ich einfach die String-Liste in eine Int-Liste schreiben, das ist bedeutend einfacher ^^

galagher · Verfasst: Sa 18.04.15 22:22

Ich danke euch allen für eure Tipps und die rasche Hilfe, mich verwirren nur "obere Grenze" und "untere Grenze" etwas, wie auch Min() und Max(). Jedenfalls muss der schreibende Teil des Ganzen eine Schleife sein, oder, so habe ich es jetzt gelöst, man aktualisiert bei jedem Schreiben der fehlenden Zahlen die zu lesende Liste, dazu habe ich alles in ein repeat/until gepackt.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

  c := liste1.count;
  x := c;

  repeat
    for i := 0 to liste1.count-2 do
    begin
      if item+1 - item > 1 then
      begin
        //berechne die fehlende zahl
        //schreibe diese in liste2
        //füge sie in liste1 bei i+1 ein
        c := liste1.count;
      end;
    end;
    Inc(x);
until x >= c;

Ist eine Schleife und klappt!

Zur Frage nach der Performance - bei 001 bis maximal 999 ist diese wohl vernachlässigbar!

Zu C (genauer: C++) - lange ist's her, über 20 Jahre! ja, ich verstehe den Code im Wesentlichen, nur fällt mir auf: Bei Delphi kann man den Zähler einer for-Schleife nicht erhöhen, bei C geht das scheinbar (ich erinnere mich nicht mehr):

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:

for (int i ...
{
...
        i++; //Bei Delphi geht Inc(i) nicht, weil in for verwendet!
...
}

_________________
gedunstig war's - und fahle wornen zerschellten karsig im gestrock. oh graus, es gloomt der jabberwock - und die graisligen gulpen nurmen!

Th69 · Verfasst: So 19.04.15 09:30

Hallo,

bei deinem ersten Quellcode fehlt noch die innere Schleife:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

for i := 0 to L.Count-2 do
begin
    nLow = StrToInt(L[i]);
    nHigh = StrToInt(L[i+1]);
    if nHigh - nLow > 1 then
        for j := nLow+1 to nHigh-1 do
            L1.Add(IntToStr(j));
end;

galagher · Verfasst: So 19.04.15 18:50

Th69 hat folgendes geschrieben :

bei deinem ersten Quellcode fehlt noch die innere Schleife:

So ist's kürzer und funktioniert ebenfalls korrekt!

_________________
gedunstig war's - und fahle wornen zerschellten karsig im gestrock. oh graus, es gloomt der jabberwock - und die graisligen gulpen nurmen!

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme