Découpage d'une liste en n partitions de longueur presque égale

Question

Je cherche un moyen rapide, propre et pythonique de diviser une liste en exactement n partitions presque égales.

partition([1,2,3,4,5],5)->[[1],[2],[3],[4],[5]]
partition([1,2,3,4,5],2)->[[1,2],[3,4,5]] (or [[1,2,3],[4,5]])
partition([1,2,3,4,5],3)->[[1,2],[3,4],[5]] (there are other ways to slice this one too)

Il y a plusieurs réponses ici Itération sur les tranches de liste qui se rapprochent beaucoup de ce que je veux, sauf qu'ils sont axés sur la taille de la liste, et je me soucie de la numéro des listes (certaines d'entre elles comportent également la mention None). Il est évidemment possible de convertir ces listes de manière triviale, mais je suis à la recherche d'une meilleure pratique.

De même, des personnes ont signalé d'excellentes solutions ici Comment diviser une liste en morceaux de taille égale ? pour un problème très similaire, mais je suis plus intéressé par le nombre de partitions que par la taille spécifique, tant qu'elle est dans la limite de 1. Encore une fois, c'est trivialement convertible, mais je suis à la recherche d'une meilleure pratique.

Answer 1

Juste un point de vue différent, qui ne fonctionne que si [[1,3,5],[2,4]] est une partition acceptable, dans votre exemple.

def partition ( lst, n ):
    return [ lst[i::n] for i in xrange(n) ]

Cela satisfait l'exemple mentionné dans l'exemple de @Daniel Stutzbach :

partition(range(105),10)
# [[0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100],
# [1, 11, 21, 31, 41, 51, 61, 71, 81, 91, 101],
# [2, 12, 22, 32, 42, 52, 62, 72, 82, 92, 102],
# [3, 13, 23, 33, 43, 53, 63, 73, 83, 93, 103],
# [4, 14, 24, 34, 44, 54, 64, 74, 84, 94, 104],
# [5, 15, 25, 35, 45, 55, 65, 75, 85, 95],
# [6, 16, 26, 36, 46, 56, 66, 76, 86, 96],
# [7, 17, 27, 37, 47, 57, 67, 77, 87, 97],
# [8, 18, 28, 38, 48, 58, 68, 78, 88, 98],
# [9, 19, 29, 39, 49, 59, 69, 79, 89, 99]]

Answer 2

Voici une version similaire à celle de Daniel : elle divise aussi équitablement que possible, mais place toutes les plus grandes partitions au début :

def partition(lst, n):
    q, r = divmod(len(lst), n)
    indices = [q*i + min(i, r) for i in xrange(n+1)]
    return [lst[indices[i]:indices[i+1]] for i in xrange(n)]

Il évite également l'utilisation de l'arithmétique des flottants, car cela me met toujours mal à l'aise. :)

Edit : un exemple, juste pour montrer le contraste avec la solution de Daniel Stutzbach

>>> print [len(x) for x in partition(range(105), 10)]
[11, 11, 11, 11, 11, 10, 10, 10, 10, 10]

Answer 3

def partition(lst, n):
    division = len(lst) / float(n)
    return [ lst[int(round(division * i)): int(round(division * (i + 1)))] for i in xrange(n) ]

>>> partition([1,2,3,4,5],5)
[[1], [2], [3], [4], [5]]
>>> partition([1,2,3,4,5],2)
[[1, 2, 3], [4, 5]]
>>> partition([1,2,3,4,5],3)
[[1, 2], [3, 4], [5]]
>>> partition(range(105), 10)
[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [11, 12, 13, 14, 15, 16, 17, 18, 19, 20], [21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31], [32, 33, 34, 35, 36, 37, 38, 39, 40, 41], [42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52], [53, 54, 55, 56, 57, 58, 59, 60, 61, 62], [63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73], [74, 75, 76, 77, 78, 79, 80, 81, 82, 83], [84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94], [95, 96, 97, 98, 99, 100, 101, 102, 103, 104]]

Version Python 3 :

def partition(lst, n):
    division = len(lst) / n
    return [lst[round(division * i):round(division * (i + 1))] for i in range(n)]

Answer 4

Voici une façon de le faire.

def partition(lst, n):
    increment = len(lst) / float(n)
    last = 0
    i = 1
    results = []
    while last < len(lst):
        idx = int(round(increment * i))
        results.append(lst[last:idx])
        last = idx
        i += 1
    return results

Si len(lst) ne peut pas être divisé uniformément par n, cette version distribuera les éléments supplémentaires à des intervalles à peu près égaux. Par exemple :

>>> print [len(x) for x in partition(range(105), 10)]
[11, 10, 11, 10, 11, 10, 11, 10, 11, 10]

Le code pourrait être plus simple si cela ne vous dérange pas que tous les 11 soient au début ou à la fin.

Answer 5

Cette réponse fournit une fonction split(list_, n, max_ratio) pour les personnes qui veulent diviser leur liste en n pièces avec au plus max_ratio rapport à la longueur de la pièce. Cela permet une plus grande variation que le l'auteur de la question "au plus une différence dans la longueur des pièces".

Il fonctionne par échantillonnage n longueurs de pièces dans la plage de rapports souhaitée [1 , max_ratio) en les plaçant l'un après l'autre pour former un "broken". bâton " avec les bonnes distances entre les " points de rupture " mais la mauvaise longueur totale. La mise à l'échelle du bâton brisé à la longueur souhaitée nous donne les positions approximatives des points de rupture que nous voulons. Pour obtenir des points de rupture entiers les points de rupture nécessitent un arrondi ultérieur.

Malheureusement, les arrondis peuvent conspirer pour rendre les pièces trop courtes, et vous permettre de dépasser le rapport max_ratio. Voir le bas de cette réponse pour un exemple.

import random

def splitting_points(length, n, max_ratio):
    """n+1 slice points [0, ..., length] for n random-sized slices.

    max_ratio is the largest allowable ratio between the largest and the
    smallest part.
    """
    ratios = [random.uniform(1, max_ratio) for _ in range(n)]
    normalized_ratios = [r / sum(ratios) for r in ratios]
    cumulative_ratios = [
        sum(normalized_ratios[0:i])
        for i in range(n+1)
    ]
    scaled_distances = [
        int(round(r * length))
        for r in cumulative_ratios
    ]

    return scaled_distances

def split(list_, n, max_ratio):
    """Slice a list into n randomly-sized parts.

    max_ratio is the largest allowable ratio between the largest and the
    smallest part.
    """

    points = splitting_points(len(list_), n, ratio)

    return [
        list_[ points[i] : points[i+1] ]
        for i in range(n)
    ]

Vous pouvez l'essayer comme ça :

for _ in range(10):
    parts = split('abcdefghijklmnopqrstuvwxyz', 4, 2)
    print([(len(part), part) for part in parts])

Exemple d'un mauvais résultat :

parts = split('abcdefghijklmnopqrstuvwxyz', 10, 2)

# lengths range from 1 to 4, not 2 to 4
[(3, 'abc'),  (3, 'def'), (1, 'g'),
 (4, 'hijk'), (3, 'lmn'), (2, 'op'),
 (2, 'qr'),  (3, 'stu'),  (2, 'vw'),
 (3, 'xyz')]