Entwickler-Ecke :: Thema anzeigen - Liste - Zahlen ergänzen bzw. fehlende Zahlen erkennen

galagher - Sa 18.04.15 16:41
Titel: Liste - Zahlen ergänzen bzw. fehlende Zahlen erkennen

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:

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!

galagher - 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:

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;

Palladin007 - 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.

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:

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 :D
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# - 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.

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:

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:

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);

galagher - 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.

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):

C#-Quelltext

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

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

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!