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: 135
Registriert: Montag 7. Juli 2008, 20:22

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

@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

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: 3554
Registriert: Donnerstag 25. Juni 2009, 14:40
Wohnort: Bonn

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: 3843
Registriert: Mittwoch 17. Oktober 2007, 21:40
Wohnort: WW
Kontaktdaten:

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: 1012
Registriert: Sonntag 19. September 2010, 13:45
Wohnort: Hagen
Kontaktdaten:

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/ - ausgestorbener Support für HL2-Server
BlackJack

@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

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