Best Practice Algorithmus für Berechnung von Zahlenreihenfolge

[Keo]

Ich habe ein Array von sortieren Zahlen:
int i = {1, 3, 4, 5, 7, 8, 9, 11, 13}

Diese Zahlen möchte ich in zwei unterschiedlichen Listen abspeichern:

1. Eine Liste von Zahlen, die nicht in einer Reihenfolge stehen, also
Arrays.asList(1, 11, 13);

2. Eine Liste von Zahlen, die gruppiert in einer Reihenfolge stehen, also:
List<Integer[]> test = new ArrayList<>();
test.add(new Integer[]{3,4,5});
test.add(new Integer[]{7,8,9});

Wie könnte der Code für die Berechnung der beiden Listen aussehen?

 

[Thallius]

Ganz einfach eine Schleife die immer schaut ob die aktuelle Zahl die vorherige +1 ist. wenn ja, dann an die aktuelle Liste anhängen, wenn nein dann neue Liste erstellen und die nächsten daran anhängen

 

[Xyz1]

Ganz einfach ist es mit Sicherheit nicht, aber geb ich auch mal meine Lösung zum Besten:

    /**
     * @author DerWissende on 03/17/2016
     */
    private static List<List<Integer>> getLLI(int[] array) {
        List<List<Integer>> rueck = new LinkedList<List<Integer>>();
        rueck.add(new LinkedList<Integer>()); // isolated
        Arrays.sort(array); // zur Sicherheit

        if (array[0] + 1 < array[0 + 1]) { // vorher
            rueck.get(0).add(array[0]);
        } else {
            rueck.add(new LinkedList<Integer>());
            rueck.get(rueck.size() - 1).add(array[0]);
        }

        for (int i = 1; i < array.length - 1; i++) {
            if (array[i] - 1 > array[i - 1] && array[i] + 1 < array[i + 1]) {
                rueck.get(0).add(array[i]);
            } else {
                int j = rueck.get(rueck.size() - 1).get(rueck.get(rueck.size() - 1).size() - 1);
                if (array[i] - 1 == j) {
                    rueck.get(rueck.size() - 1).add(array[i]);
                } else {
                    rueck.add(new LinkedList<Integer>());
                    rueck.get(rueck.size() - 1).add(array[i]);
                }
            }
        }

        if (array[array.length - 1] - 1 > array[array.length - 1 - 1]) { // nachher
            rueck.get(0).add(array[array.length - 1]);
        } else {
            rueck.add(new LinkedList<Integer>());
            rueck.get(rueck.size() - 1).add(array[array.length - 1]);
        }

        return rueck;
    }

    /**
     * @author DerWissende on 03/17/2016
     */
    public static void main(String[] args) {
        System.out.println(getLLI(new int[]{1, 3, 4, 5, 7, 8, 9, 11, 13}));
    }

[[1, 11, 13], [3, 4, 5], [7, 8, 9]]

qwertqwert

Mit einem kleinen Beweis lässt sich sagen, ob sie immer funktioniert.

 

[Meniskusschaden]

Ich denke, die Komplexität entsteht durch die Sonderfälle für die Prüfung des ersten und letzten Array-Elements. Ich würde mir deshalb einfach zwei Hilfsmethoden boolean hasLeftNeighbor(int i)undboolean hasRightNeighbor(int i) erstellen. Da ist die Prüfung der jeweiligen Array-Grenze dann ganz einfach. In der Hauptschleife muß man nur noch für jedes Element prüfen, ob es einen linken und rechten Nachbarn hat.

 

[Meniskusschaden]

Es ist doch noch etwas komplizierte als ich erst dachte, weil ich übersehen habe, dass die zweite Liste nicht nur einfach die gruppierten Zahlen enthalten soll, sondern Listen mit den Zahlengruppen. Ich würde es der Lesbarkeit halber trotzdem mit Hilfsmethoden machen:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Reihenfolge {
    static int[] zahlen = {1, 3, 4, 5, 7, 8, 9, 11, 13};
    static List<Integer> einzelZahlen = new ArrayList<Integer>();
    static List<List<Integer>> gruppenListe = new ArrayList<List<Integer>>();

    public static void main(String[] args) {
        erzeugeGruppen();
        System.out.println(Arrays.toString(zahlen));
        System.out.println(einzelZahlen);
        System.out.println(gruppenListe);
    }

    private static void erzeugeGruppen() {
        List<Integer> gruppe = new ArrayList<Integer>();
        for (int i=0; i<zahlen.length; i++) {
            if (!hasLeftNeighbor(i) && !hasRightNeighbor(i)) {
                einzelZahlen.add(zahlen[i]);
                continue;
            }
            if (!hasLeftNeighbor(i) && hasRightNeighbor(i)) {
                gruppe = new ArrayList<Integer>();
                gruppenListe.add(gruppe);
            }
            if (hasLeftNeighbor(i) || hasRightNeighbor(i)) {
                gruppe.add(zahlen[i]);  
            }
        }
    }

    private static boolean hasLeftNeighbor(int i) {
        if (i==0) {
            return false;
        }
        return zahlen[i]-zahlen[i-1]==1;
    }
  
    private static boolean hasRightNeighbor(int i) {
        if (i==zahlen.length-1) {
            return false;
        }
        return zahlen[i+1]-zahlen[i]==1;
    }
}

 

[Xyz1]

Auch ne gute Lösung. Weil bei mir aber wieder nicht auf Danke geklickt wurde, werde ich das auch bei dir nicht tun.

Das continue; aber sehr vermeiden, mir würde dann sofort Spaghetti vorgeworfen werden...

 

[Meniskusschaden]

Das continue; aber sehr vermeiden, mir würde dann sofort Spaghetti vorgeworfen werden...

Das continue kann hier ersatzlos gestrichen werden. Funktioniert trotzdem. Falls man es drin lässt kann man die dritte if-Bedingung entfernen, weil sie aufgrund der ersten if-Bedingung ohnehin immer zutrifft:

//    if (hasLeftNeighbor(i) || hasRightNeighbor(i)) {
        gruppe.add(zahlen[i]);  
//    }

 

[Meniskusschaden]

Das continue; aber sehr vermeiden, mir würde dann sofort Spaghetti vorgeworfen werden...

Ich bin übrigens kein strikter Gegner von break und continue. Es kann durchaus zur Lesbarkeit beitragen, wenn man sofort sieht, dass man die Schleife an einer bestimmten Stelle verlässt bzw. die nächste Iteration startet. Bei verschachtelten Schleifen und in Verbindung mit Labels finde ich es allerdings auch grausam.

 

[Keo]

danke, ich habe noch eine Abfrage eingebaut, falls int[] zahlen nur ein Element beinhaltet.

Kennt jmd. noch schickere Lösungen? Vielleicht irgendwelche vorhanden Hilfsklassen, die mir die Arbeit erleichtert.

 

[Xyz1]

Vielleicht irgendwelche vorhanden Hilfsklassen, die mir die Arbeit erleichtert.

Nein, gibt keine, weil das so eine Mini-aufgabe ist, die man schnell selber schreiben soll können.

 

[Xyz1]

Okay, ich hab vergessen zu erwähnen, das(s) sich für sowas hervorragend eigentlich eine Deque eignet. Aber ich dachte, dieser Kommentar wird bestimmt sowieso kommen.

 

[Xyz1]

Ich hab es noch mal refactoret, um die Lesbarkeit maximal zu erhöhen:

    private static List<Integer> getFirst(List<List<Integer>> rueck) {
        return rueck.get(0);
    }
    
    private static List<Integer> getLast(List<List<Integer>> rueck) {
        return rueck.get(rueck.size() - 1);
    }
    
    private static Integer getLastElem(List<List<Integer>> rueck) {
        List<Integer> li = getLast(rueck);
        return li.get(li.size() - 1);
    }
    
    private static void addFirst(List<List<Integer>> rueck, int a) {
        getFirst(rueck).add(a);
    }
    
    private static void addLast(List<List<Integer>> rueck, int a) {
        getLast(rueck).add(a);
    }
    
    private static void addLastNew(List<List<Integer>> rueck, int a) {
        rueck.add(new LinkedList<Integer>());
        getLast(rueck).add(a);
    }
    
    private static List<List<Integer>> getLLI(int[] array) {
        List<List<Integer>> rueck = new LinkedList<List<Integer>>();
        rueck.add(new LinkedList<Integer>());                                   // isolated
        Arrays.sort(array);                                                     // zur Sicherheit

        if (array[0] + 1 < array[0 + 1]) {                                      // vorher
            addFirst(rueck, array[0]);
        } else {
            addLastNew(rueck, array[0]);
        }
        
        for (int i = 1; i < array.length - 1; i++) {
            if (array[i] - 1 > array[i - 1] && array[i] + 1 < array[i + 1]) {
                addFirst(rueck, array[i]);
            } else {
                if (array[i] - 1 == getLastElem(rueck)) {
                    addLast(rueck, array[i]);
                } else {
                    addLastNew(rueck, array[i]);
                }
            }
        }
        
        if (array[array.length - 1] - 1 > array[array.length - 2]) {            // nachher
            addFirst(rueck, array[array.length - 1]);
        } else {
            addLastNew(rueck, array[array.length - 1]);
        }
        
        return rueck;
    }

    /**
     * @author DerWissende on 03/17/2016
     */
    public static void main(String[] args) {
        System.out.println(getLLI(new int[]{1, 3, 4, 5, 7, 8, 9, 11, 13}));
    }

Ein "Gefällt mir" ist gerne willkommen.

 

[Flown]

Also basierend auf StuartMarks und meiner Idee gab es schon einen Post auf StackOverflow: HIER

Das kann man mit Geschick und Streams lösen. Erst muss man die Indizes der Gruppen im Array ermitteln. Wenn man die hat kopiert man anhand von den berechneten Indizes die Arrays in kleine Junks. Die Ergebnisse partitionieren und alle "Gruppen" mit Länge 1 in eine Liste zusammenfassen.
Dann kommt sowas raus:

public class Test {

  public static void main(String... args) {
    System.out.println(findGroupings(new int[] { 1, 3, 4, 5, 7, 8, 9, 11, 13 }));
  }

  public static ArrayRangeResult findGroupings(int[] arr) {
    if (arr == null || arr.length == 0) {
      return new ArrayRangeResult(arr, Collections.emptyList(), Collections.emptyList());
    }
    int[] x = IntStream.rangeClosed(0, arr.length).filter(i -> i == 0 || i == arr.length || arr[i - 1] + 1 != arr[i]).toArray();
    Map<Boolean, List<int[]>> collect = IntStream.range(0, x.length - 1).mapToObj(i -> Arrays.copyOfRange(arr, x[i], x[i + 1])).collect(Collectors.partitioningBy(i -> i.length > 1));
    return new ArrayRangeResult(arr, collect.get(true), collect.get(false).stream().flatMap(i -> Arrays.stream(i).boxed()).collect(Collectors.toList()));
  }
}

class ArrayRangeResult {
  private final int[] origin;
  private final List<int[]> groupings;
  private final List<Integer> delimiters;

  public ArrayRangeResult(int[] origin, List<int[]> groupings, List<Integer> delimiters) {
    this.origin = origin;
    this.groupings = groupings;
    this.delimiters = delimiters;
  }

  public int[] getOrigin() {
    return origin.clone();
  }

  public List<int[]> getGroupings() {
    return groupings.stream().map(g -> g.clone()).collect(Collectors.toList());
  }

  public List<Integer> getDelimiters() {
    return new ArrayList<>(delimiters);
  }

  @Override
  public String toString() {
    String result = "Array: " + Arrays.toString(origin) + "\n";
    result += "Groupings: " + groupings.stream().map(Arrays::toString).collect(Collectors.joining(",")) + "\n";
    result += "Delimiters: " + delimiters;
    return result;
  }
}