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.
Liste in Bereiche zerlegen
@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.
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.
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]
[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]
itertools aus der Standardbibliothek ist mächtig.
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
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))
[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))
- noisefloor
- User
- Beiträge: 3856
- 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:
Gruß, noisefloor
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)
- DeaD_EyE
- User
- Beiträge: 1021
- 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]
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.
Grund: Quelltext in Python-Codebox-Tags gesetzt.
sourceserver.info - sourceserver.info/wiki/ - ausgestorbener Support für HL2-Server
@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`.
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()