Optimales Verkleinern von Spaltenbreiten

[snafu]

Hallo Python-Freund:innen!

Ich verzweifle hier an einem Problem bzw suche eine möglichst elegante Lösung dafür.

Gegeben sei eine Liste von positiven (Ganz-)Zahlen, die für die Spaltenbreiten einer Tabelle stehen. Weiterhin gibt es eine Maximalbreite, die von der Tabelle eingenommen werden darf. Betrachtet werden sollen nur die Fälle, in denen die Summe der Spaltenbreiten die Maximalbreite überschreitet.

Es gilt nun, die Spalten so zu verkleinern, dass die komplette Tabelle in die vorgegebene Gesamtbreite passt. Dabei sollen möglichst gleich breite Spalten herauskommen¹, aber die anfangs vorgegebenen Spaltenbreiten sollen nicht überschritten werden. Anders gesagt: Eine Spalte kann nur verkleinert werden oder gleich bleiben, jedoch niemals breiter sein als die Vorgabe.

Mein Ansatz ist, die Spalten absteigend nach ihrer Breite zu sortieren (also höchste Breite zuerst). Dann wird auf Basis des Offset (= max. Breite - Gesamtbreite) schrittweise verkleinert bis der Offset bei 0 liegt und es somit passt. Das ist aber sehr umständlich, unübersichtlich, aufwändig, fehleranfällig und einfach nur doof. Gibt es da einen schlauen mathematischen Ansatz, um vorab möglichst viele Annahmen treffen zu können, sodass Iterationsschritte und Code eingespart werden können?

Ich freue mich über Hinweise aller Art. Wenn noch Fragen zum Vorgehen bestehen, stellt sie.

EDIT (Fußnote):
¹ Also was ich nicht möchte, ist dass man z.B. die größte Spalte einfach von 30 auf sagen wir mal 3 verkleinert und dies zusammen mit viel breiteren Spalten als Lösung sieht. Vielmehr soll quasi die breiteste Spalte auf die Breite der zweitgrößten gebracht werden und wenn das nicht passt, dann sollen die beiden auf die Breite der drittgrößten gebracht werden, usw. Jedoch das große Aber: Die Lösung soll immer die komplette Gesamtbreite ausnutzen. Beim letzten Angleichen kann es also gut sein, dass gar nicht bis zur nächsten Spaltenbreite heruntergangen werden muss, sondern weniger (gleichmäßige) Verkleinerung für die in Frage kommenden Spalten ausreicht. Spätestens da wird es also etwas tricky.

[__deets__]

Gibt es einen Grund, warum du nicht einfach jede Spalte um das Verhaeltnis von angegebener Gesamtbreite zu zur Verfuegung stehendem Platz verkleinerst? Also die Summe der Zahlen waere 100, und der Platz 50, dann dividierst du jede Spaltenbreite einfach durch 2.

Ansonsten gibt es zB Algorithmen wie cassowary https://en.wikipedia.org/wiki/Cassowary_(software), die koennten eine Loesung darstellen. *Einfacher* als dein Ansatz ist das ultimativ natuerlich nicht, aber ggf. hast du da mehr Spielmoeglichkeiten, die ein interessanteren Ergebnisraum erzeugen.

[snafu]

Gibt es einen Grund, warum du nicht einfach jede Spalte um das Verhaeltnis von angegebener Gesamtbreite zu zur Verfuegung stehendem Platz verkleinerst? Also die Summe der Zahlen waere 100, und der Platz 50, dann dividierst du jede Spaltenbreite einfach durch 2.

Der Grund ist, dass sich die Spaltenbreiten annähern sollen. Wenn ich also [20, 80] habe und 50 Maximalbreite, dann hätte ich gern [20, 30] als Lösung, nicht [10, 40].

[__deets__]

Dann schau mal cassowary an.

Oder eine alternative Modellierunge koennte sich an der Physik anlehnen: jede Zelle ist eine Feder, so gross wie die Pixel. Aber die Federkonstante ist umgekehrt proportional zur Breite. Damit wird jetzt bei Druck von beiden Seiten die groesseren Felder staerker zusammengedrueckt als die kleineren. Mit diesem Ansatz koenntest du auch bestimmte Zellen schuetzen, indem du einen Multiplikationsfaktor fuer sie einfuehrst.

Das ganze zu loesen ist irgendeine Differentialgleichung, das ist auch nichts, was ich so kurz aus dem Aermel schuettel. Aber auch "naiv-iterativ" kann man sich dem annaehern, oder mal suchen, ob es das als Problemstellung schon gibt. Kann ich mir sehr gut vorstellen.

[snafu]

Ich werde mir weiter Gedanken machen. Bin ich ja schon fast froh, dass es anscheinend nichts Triviales ist, das ich übersehen habe. Es ist auch nur für ein Hobbyprojekt. Ich werde den Ansatz hier posten, sobald ich etwas implementiert habe, das ich für halbwegs gescheit halte.

[sparrow]

@snafu: Ich persönlich mag ja, an den Stellen Klassen einzusetzen, deren Eigenschaften das Problem abbilden.

Code: Alles auswählen

import itertools


class ColumnWidth():

    def __init__(self, width):
        self.original_width = width
        self.__width = width
        self.is_width_modified = False

    @property
    def width(self):
        return self.__width

    @width.setter
    def width(self, value):
        if value > self.original_width:
            value = self.original_width
        self.is_width_modified = True
        self.__width = value


def optimized_column_widths(column_widths, max_width):
    columns = [ColumnWidth(column) for column in column_widths]
    while sum(c.width for c in columns) > max_width:
        widths = sorted(
            set([column.width for column in columns]),
            reverse=True
        )
        if len(widths) < 2:
            raise Exception("It seems there is no solution...")
        max_column_width = widths[0]
        second_max_column_width = widths[1]
        for column in columns:
            if column.width == max_column_width:
                column.width = second_max_column_width
    for column in itertools.cycle(columns):
        if sum(c.width for c in columns) >= max_width:
            break
        if column.is_width_modified:
            column.width += 1
    return [column.width for column in columns]

        
def main():
    column_widths = [20, 80]
    optimized_widthes = optimized_column_widths(column_widths, 50)
    print(optimized_widthes)
    

if __name__ == "__main__":
    main()

[snafu]

Ich habe jetzt etwas, das zwar nicht exakt die Vorgaben erfüllt, mir aber erstmal als Lösung ausreicht. Dabei vergleiche ich jede Breite mit ihrem Nachbarn und führe die Angleichung nur dann durch, wenn die Spalte größer als der Nachbar ist. Der Schritt erfolgt dann via new_width = max(width - offset, next_width), um nicht unter die Breite des Nachbarn zu rutschen. Für den Fall, dass der erste Durchgang nicht ausreicht, habe ich noch eine while-Schleife herum gebaut. Sie läuft solange offset > 0 and any(w > 1 for w in widths), da Spaltenbreiten niemals den Wert 0 annehmen sollen. Evtl ersetze ich die 1 später durch eine Mindestbreite, die als Argument mitgegeben werden kann. Der Offset wird selbstverständlich bei jeder Veränderung angepasst mittels offset -= width - new_width, da er ja sonst nicht schrumpfen würde. Ich teste das jetzt ausgiebig und muss bestimmt noch ein paar Randfälle bedenken, aber für's Erste bin ich ganz zufrieden damit...

EDIT: Ach egal, ich poste jetzt einfach mal die betreffende Methode.

Code: Alles auswählen

def shrink_columns(self, line_width=None):
    if line_width is None:
        line_width = get_terminal_size().columns
    offset = len(self) - line_width
    widths = self.get_column_widths()
    while offset > 0 and any(w > 1 for w in widths):
        pairs = zip_longest(widths, widths[1:], fillvalue=1)
        for i, (width, next_width) in enumerate(pairs):
            if width > next_width:
                new_width = max(width - offset, next_width)
                offset -= width - new_width
                widths[i] = new_width
    return self.justify(widths)

justify() gleicht die Elemente an, da es hier nicht wirklich um Tabellen geht, sondern um die spaltenweise Anordnung von Strings im Terminal, wobei die Spaltenbreiten eben automatisch ermittelt werden sollen. Für die Ausgabe sind auch bereits automatische Zeilenumbrüche innerhalb der Spalten implementiert, wenn die Breite geschrumpft ist. Mir hatte nur noch der Schritt des eigentlichen Schrumpfens der Spalten gefehlt.

[sparrow]

Auf jeden Fall ein bisschen spannend.
Aber der Code sollte das tun, was dein Anforderungen waren
Meine Prüfung, ob es eine Lösung gibt, hat noch nicht gestimmt. Das hier sollte sich wie deine Vorgabe verhalten:

Code: Alles auswählen

import itertools


class ColumnWidth():

    def __init__(self, width):
        self.original_width = width
        self.__width = width
        self.is_width_modified = False

    @property
    def width(self):
        return self.__width

    @width.setter
    def width(self, value):
        if value > self.original_width:
            value = self.original_width
        self.is_width_modified = True
        self.__width = value


def optimized_column_widths(column_widths, max_width):
    if sum(column_widths) < max_width:
        return column_widths
    columns = [ColumnWidth(column) for column in column_widths]
    while sum(c.width for c in columns) > max_width:
        widths = sorted(
            set([column.width for column in columns]),
            reverse=True)
        if len(widths) == 1 and widths[0] * len(columns) > max_width:
            raise Exception("It seems there is no solution...")
        max_column_width = widths[0]
        second_max_column_width = widths[1] if len(widths) > 1 else widths[0]
        for column in columns:
            if column.width == max_column_width:
                column.width = second_max_column_width
    for column in itertools.cycle(columns):
        if sum(c.width for c in columns) >= max_width:
            break
        if column.is_width_modified:
            column.width += 1
    return [column.width for column in columns]

        
def main():
    column_widths = [20, 80]
    optimized_widthes = optimized_column_widths(column_widths, 41)
    print(optimized_widthes)
    

if __name__ == "__main__":
    main()

Wenn am Ende alle Spalten nur noch eine Größe haben und sie ingesamt breiter sind als die maximale Breite, gibt es eine Exception.
Jetzt könnte man die Breite der Spalten wieder so weit verringern, dass es trotzdem passt, aber ich weiß nicht, ob das das vorkommen kann.

[snafu]

Wenn am Ende alle Spalten nur noch eine Größe haben und sie ingesamt breiter sind als die maximale Breite, gibt es eine Exception.
Jetzt könnte man die Breite der Spalten wieder so weit verringern, dass es trotzdem passt, aber ich weiß nicht, ob das das vorkommen kann.

Klar, die Spalten sollen dann gemeinsam auf eine passende Gesamtgröße geschrumpft werden. Ob Exception oder nicht, sei mal dahingestellt. Das hatte ich ja vorweg auch nicht angegeben.

Meine jetzige Lösung ist deutlich weniger komplex als deine, aber löst das ursprünglich beschriebene Problem - wie du schon richtigerweise schriebst - nicht wirklich. Wenn ich z.B. [9, 9, 9, 9, 1] habe und auf eine Gesamtbreite von 30 kommen will, dann spuckt er bei meinem Ansatz [9, 9, 9, 2, 1] aus. Gewünscht ist aber eigentlich [7, 7, 7, 8, 1] oder sowas (vielleicht auch [8, 8, 8, 5, 1]). Bin mir da selber nicht ganz schlüssig, ehrlich gesagt, hat nun aber auch keine Priorität für mich, da die "billige" Lösung für meinen Anwendungsfall (derzeit nur zwei Spalten) genügt. Das soll euch aber nicht vom Tüfteln für eine allgemeinere Lösung abhalten, zumal ich zu einem späteren Zeitpunkt sicherlich auch mal mehr Spalten "korrekt" schrumpfen lassen will.

[sparrow]

Es ist ziemlich nah dran:

Code: Alles auswählen

>>> x = [9, 9, 9, 9, 1]
>>> optimized_column_widths(x, 30)
[8, 7, 7, 7, 1]

[snafu]

Es ist ziemlich nah dran:

Code: Alles auswählen

>>> x = [9, 9, 9, 9, 1]
>>> optimized_column_widths(x, 30)
[8, 7, 7, 7, 1]

Wäre auch ne akzeptable Lösung. Ich schau mir deinen Code noch genauer an, ob ich was rauskürzen oder vereinfachen kann. Das Ergebnis sieht jedenfalls vielversprechend aus. Besten Dank dafür.

[kbr]

Interessantes Problem. Dafür habe ich hier einen anderen Ansatz, der pro Spalte einen gewichteten Skalierungsfaktor ansetzt und rekursiv läuft, bis es passt. Der verwendete SHRINK_FACTOR ist empirisch. Mit 1.6 klappt das soweit ganz gut.

Code: Alles auswählen

SHRINK_FACTOR = 1.6  # empirischer Faktor

def shrink_columns(widths, target_width):
    factor = sum(widths) / target_width
    max_col_width = max(widths)
    col_factors = [
        factor * col_width / max_col_width * SHRINK_FACTOR 
        if col_width < max_col_width else factor 
        for col_width in widths
    ]
    widths = [
        int(col_width / col_factor) 
        for col_width, col_factor in zip(widths, col_factors)
    ]
    if sum(widths) > target_width:
        return shrink_columns(widths, target_width)
    delta = target_width - sum(widths)
    return [w + 1 if delta > j else w for j, w in enumerate(widths)]

widths = [9, 9, 9, 9, 1]
target_width = 30

shrink_columns(widths, target_width)

Funktioniert übrigens auch, wenn die Tabellen-Zielbreite nicht verkleinert, sondern vergrößert wird. (Hatte aber nur wenig Testcases )

[sparrow]

@kbr: Aber dann werden Spalten auch breiter als sie vorher waren.

[kbr]

@sparrow: sicher, wenn die Tabelle breiter wird, dann werden auch die Spalten breiter. Die Funktion arbeitet in beide Richtungen. Schmale Spalten wachsen schneller, wenn die Tabelle breiter wird und schrumpfen langsamer, wenn die Tabelle schmaler wird.

[snafu]

Passt halt nur nicht zur Fragestellung.

[sparrow]

@kbr: Deine Spalten werden aber auch größer, wenn die Breite der Tabelle kleiner wird. [9, 9, 9, 9, 1] Zielbreite 30 wird bei deinem Code [7, 7, 6, 6, 4] . Aber snafu sagte: "aber die anfangs vorgegebenen Spaltenbreiten sollen nicht überschritten werden" - Die letzte Spalte "1" darf hinterher nicht größer als 1 sein.

[nezzcarth]

@snafu: Für die praktische Anwendung ist das vmtl. nichts, was du gebrauchen kannst, aber interessehalber habe ich es mal mit einer Art genetischem Algorithmus versucht. Die Schwierigkeit ist hier natürlich, eine gute Fitness Funktion zu finden. Meine sieht zur Zeit (etwas abweichend davon, wie man das normalerweise machen würde und die man daher evtl. nicht so nennen sollte) so aus:

Code: Alles auswählen

def evaluate(candidate, base, target):
    target_fail = abs(target - sum(candidate))
    deviations = sum(abs(x-y) for x, y in zip(sorted(candidate), sorted(base)))
    return stdev(candidate) + target_fail + deviations

Damit bekomme ich für dein letztes Beispiel relativ schnell und wiederholbar die Lösung, die du per Hand gefunden hattest:

Code: Alles auswählen

$ ./genetic_columns.py
Generation: 1
Candidate: [9, 4, 8, 3, 7] Eval: 13.588435821108957

Generation: 2
Candidate: [9, 8, 7, 3, 6] Eval: 13.302172886644268

…

Generation: 23
Candidate: [1, 6, 7, 8, 8] Eval: 9.91547594742265

Generation: 24
Candidate: [1, 8, 7, 7, 7] Eval: 9.82842712474619

Geht sicher noch deutlich besser und einige deiner Kriterien sind hier gar nicht explizit enthalten. Ich denke, so ein Verfahren kann sich vor allem lohnen, wenn es sich um sehr viele Spalten handelt.

[kbr]

@sparrow: Da hast Du recht, das hatte ich nicht berücksichtigt. Diese Nebenbedingung einzubauen ist jedoch nicht allzu schwierig. Vielleicht hilft die Idee gewichteter Skalierungsfaktoren dennoch weiter.

[snafu]

@nezzcarth
Gar nicht mal so schlecht und auch relativ kompakt gehalten. Ist garantiert, dass die Lösung mit der kleinsten Abweichung (Generation 24) auch immer korrekt ist? Wie ermittelst du die Kandidaten? Nimmst du dafür stumpf alle Kombinationen, die möglich sind?