Liste in Bereiche zerlegen

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
BastiL
User
Beiträge: 116
Registriert: Montag 7. Juli 2008, 20:22

Sonntag 23. Juli 2017, 15:17

Hallo zusammen,

ich grüble aktuell über folgendem Problem: Ich habe eine Liste mit einer Zahlenreihe. Diese Liste kann mehrere Millionen Zahlen enthalten. Ich möchte die Liste in zusammenhängende Zahlenberiche zerlegen:

Liste = [1,2,3,5,6,7,8,9,11,13,14,15,17]

Ergebnis = [1-3, 5-9, 11, 13-15, 17]

Keine Idee wie ich das vernünftig mache. Ich denke über einen Ansatz mit Sets nach, bei dem ich eine zweite Liste erzeuge:

Liste2 = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17]

Dann mittels eines Sets die Differenz bilden so die Idee und das irgendwie nutzen um die Liste zu zerteilen. Aber wie? Mir fehlt irgendwie die zündende Idee.
BlackJack

Sonntag 23. Juli 2017, 15:56

@BastiL: Die Grundidee wäre sich die Zahlen immer paarweise anzuschauen und die Differenz zu bilden. Immer wenn die nicht 1 beträgt, fängt man eine neue Gruppe an. Für's paarweise iterieren gibt es in der Dokumentation vom `itertools`-Modul ein Rezept. Und `itertools.groupby()` kann beim gruppieren helfen.

Es stellt sich auch die Frage nach dem Ergebnis, denn ``[1-3, 5-9, 11, 13-15, 17]`` ist ja kein gültiges Literal für Python, es sei denn Du meinst tatsächlich das da Werte abgezogen werden sollten und das Ergebnis dann ``[-2, -4, 11, -2, 17]`` sein soll. Du brauchst also irgend eine Repräsentation für die Elemente wie Zeichenketten, oder Tupel, oder eine eigene Klasse.
BlackJack

Mittwoch 26. Juli 2017, 16:48

Die Grundidee mal mit CoffeeScript und `lodash` als Bibliothek für `zip()`, `groubBy()` & Co umgesetzt:
[codebox=coffeescript file=Unbenannt.coffee]#!/usr/bin/env coffee
'use strict'
_ = require 'lodash'


class Range

constructor: (@first, @last) ->

toString: -> if @first == @last then "#{@first}" else "#{@first}-#{@last}"


createMarkerFunction = ->
groupIndex = 0
(a, b) ->
result = {groupIndex: groupIndex, value: a}
groupIndex += 1 if b - a != 1
result


groupNumberRanges = (numbers) ->
_(numbers)
.zipWith _.concat(_.tail(numbers), [0]), createMarkerFunction()
.groupBy 'groupIndex'
.map (group) -> new Range _.first(group).value, _.last(group).value
.value()


main = ->
numbers = [1, 2, 3, 5, 6, 7, 8, 9, 11, 13, 14, 15, 17]
result = groupNumberRanges numbers
console.log result
console.log _.invokeMap(result, 'toString').join(', ')


main() if require.main == module[/code]
Ausgabe:
[codebox=text file=Unbenannt.txt][ Range { first: 1, last: 3 },
Range { first: 5, last: 9 },
Range { first: 11, last: 11 },
Range { first: 13, last: 15 },
Range { first: 17, last: 17 } ]
1-3, 5-9, 11, 13-15, 17
[/code]
Benutzeravatar
/me
User
Beiträge: 3200
Registriert: Donnerstag 25. Juni 2009, 14:40
Wohnort: Bonn

Donnerstag 27. Juli 2017, 12:41

itertools aus der Standardbibliothek ist mächtig.

Code: Alles auswählen

import itertools
data = [1,2,3,5,6,7,8,9,11,13,14,15,17]
groups = (list(x) for _, x in itertools.groupby(data, lambda x, c=itertools.count(): x - next(c)))
for element in groups:
    print('element={}'.format(element))
Das Ergebnis:
[codebox=text file=Unbenannt.txt]element=[1, 2, 3]
element=[5, 6, 7, 8, 9]
element=[11]
element=[13, 14, 15]
element=[17][/code]
Im Prinzip läuft einfach ein Zähler parallel zu der Zahl und wenn der Abstand zwischen der Zahl und dem Zähler sich ändert, dann wird eine neue Gruppe erstellt.

Eine Stringdarstellung bekommst du, wenn du statt der for-Schleife folgenden Code einsetzt (der Code lässt sich natürlich auch freundlicher schreiben):

Code: Alles auswählen

print(', '.join('-'.join(map(str, (item[0], item[-1])[:len(item)])) for item in groups))
Benutzeravatar
noisefloor
User
Beiträge: 2456
Registriert: Mittwoch 17. Oktober 2007, 21:40
Wohnort: Görgeshausen
Kontaktdaten:

Donnerstag 27. Juli 2017, 13:43

Hallo,

irgendwann hatte BlackJack mal eine Lösung eines ähnlichen Problems mit Hilfe von `collections.deque` gelöst. Was ich damals total toll fand, darum hier eine mögliche Lösung damit:

Code: Alles auswählen

from collections import deque

my_list = [1,2,3,5,6,7,8,9,11,13,14,15,17]
queue = deque([], maxlen=2)
result = []
sub_result = []
for element in my_list:
    queue.append(element)
    if len(queue)==2 and queue[1]-queue[0] > 1:
            result.append(sub_result)
            sub_result = []
    sub_result.append(element)
if sub_result:
    result.append(sub_result)
print(result)
Gruß, noisefloor
Benutzeravatar
DeaD_EyE
User
Beiträge: 207
Registriert: Sonntag 19. September 2010, 13:45
Wohnort: Hagen
Kontaktdaten:

Donnerstag 27. Juli 2017, 13:54

Ein Ansatz mit einem Generator. Ist aber noch verbesserungswürdig und geht halt nur in die positive Richtung.
Ein Generator, der beide Richtungen kann, ließe sich mit etwas mehr Fleiß auch implementieren.
Anstatt Strings, würde ich range-objekte ausgeben. Wichtig ist dabei auch das Verhalten vom Slicing zu kennen.

sequenz[start_inklusive:ende_exklusive:schritt]

Code: Alles auswählen

def positive_rows(sequence):
    fmt = '{}-{}'
    last = start = None
    for element in sequence:
        if last is None:
            last = start = element
            continue
        if element == (last + 1):
            last = element
        else:
            yield fmt.format(start, last)
            last = start = element
    yield fmt.format(start, last)
Zuletzt geändert von Anonymous am Donnerstag 27. Juli 2017, 14:52, insgesamt 1-mal geändert.
Grund: Quelltext in Python-Codebox-Tags gesetzt.
sourceserver.info - sourceserver.info/wiki/ - Support für HL2-Server
BlackJack

Donnerstag 27. Juli 2017, 14:56

@DeaD_EyE: Das letzte ``yield`` würde ich noch mit einem ``if`` schützen falls `sequence` leer ist, und `sequence` ist schon zu viel verlangt, es reicht `iterable`.
BlackJack

Montag 31. Juli 2017, 23:24

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf-8
from __future__ import absolute_import, division, print_function
from itertools import chain, groupby, izip, tee
from operator import itemgetter


def pairwise(iterable):
    it_a, it_b = tee(iterable)
    next(it_b)
    return izip(it_a, it_b)


def iter_ranges(numbers):
    """Iterate over pairs of ranges, i.e. the start and end point of
    consecutive numbers.

    If the start and end in a pair is equal the range just consists of that
    single number.

    >>> list(iter_ranges([]))
    []
    >>> list(iter_ranges([1]))
    [(1, 1)]
    >>> list(iter_ranges([1, 2, 3, 4, 10, 20, 21, 22]))
    [(1, 4), (10, 10), (20, 22)]
    """
    def mark():
        i = 0
        # 
        # What number is chained doesn't matter but we need an extra
        # one so the last element of `numbers` will be assigned to `a`
        # and yielded eventually.
        # 
        for a, b in pairwise(chain(numbers, [0])):
            yield (i, a)
            if b - a != 1:
                i += 1

    for _, group in groupby(mark(), itemgetter(0)):
        first = last = next(group)
        for last in group:
            pass
        yield (first[1], last[1])


def main():
    numbers = [1, 2, 3, 5, 6, 7, 8, 9, 11, 13, 14, 15, 17]
    print(list(iter_ranges(numbers)))


if __name__ == '__main__':
    main()
Antworten