python - Como dividir uma lista em n grupos em todas as combinações possíveis de tamanho e elementos do grupo dentro do grupo?



(2)

Quero dividir uma lista em n grupos em todas as combinações possíveis (permitindo o tamanho do grupo variável).

Diga, eu tenho a seguinte lista:

lst=[1,2,3,4]

Se eu especificar n = 2, a lista poderá ser dividida em grupos de 1 elemento-3 elementos ou 2 elementos-2 elementos. Dentro dessas duas maneiras de dividir a lista, há combinações exclusivas de quais elementos estão em cada lista.

Com n = 2, estes seriam:

(1),(2,3,4)
(2),(1,3,4)
(3),(1,2,4)
(4),(1,2,3)
(1,2),(3,4)
(1,3),(2,4)
(1,4),(2,3)

Com n = 1, estes seriam:

(1,2,3,4)

E com n = 3, estes seriam:

(1),(2),(3,4)
(1),(3),(2,4)
(1),(4),(2,3)
(2),(3),(1,4)
(2),(4),(1,3)
(3),(4),(1,2)

Não estou interessado em grupos de comprimento 0, e a ordem dentro de um grupo não importa.

Encontrei duas perguntas semelhantes, mas elas não respondem exatamente à minha pergunta.

This questão divide uma lista em todas as combinações em que cada grupo tem o comprimento n (achei a resposta de @tokland) particularmente útil). No entanto, não estou procurando todos os grupos com a mesma duração.

E o primeiro passo this pergunta obtém combinações únicas de locais divididos para dividir uma lista em n grupos. No entanto, a ordem da lista é preservada aqui e combinações exclusivas de elementos dentro desses grupos não são determinadas.

Estou procurando uma combinação dessas duas perguntas - uma lista é dividida em n grupos em todas as combinações possíveis de tamanho de grupo, bem como combinações de elementos dentro de um grupo.

https://ffff65535.com


Podemos usar o algoritmo recursivo básico desta resposta e modificá-lo para produzir partições de um comprimento específico sem precisar gerar e filtrar partições indesejadas.

def sorted_k_partitions(seq, k):
    """Returns a list of all unique k-partitions of `seq`.

    Each partition is a list of parts, and each part is a tuple.

    The parts in each individual partition will be sorted in shortlex
    order (i.e., by length first, then lexicographically).

    The overall list of partitions will then be sorted by the length
    of their first part, the length of their second part, ...,
    the length of their last part, and then lexicographically.
    """
    n = len(seq)
    groups = []  # a list of lists, currently empty

    def generate_partitions(i):
        if i >= n:
            yield list(map(tuple, groups))
        else:
            if n - i > k - len(groups):
                for group in groups:
                    group.append(seq[i])
                    yield from generate_partitions(i + 1)
                    group.pop()

            if len(groups) < k:
                groups.append([seq[i]])
                yield from generate_partitions(i + 1)
                groups.pop()

    result = generate_partitions(0)

    # Sort the parts in each partition in shortlex order
    result = [sorted(ps, key = lambda p: (len(p), p)) for ps in result]
    # Sort partitions by the length of each part, then lexicographically.
    result = sorted(result, key = lambda ps: (*map(len, ps), ps))

    return result

Há muita coisa acontecendo aqui, então deixe-me explicar.

Primeiro, começamos com uma implementação procedural de baixo para cima (teminologia?) Do mesmo algoritmo recursivo acima mencionado :

def partitions(seq):
    """-> a list of all unique partitions of `seq` in no particular order.

    Each partition is a list of parts, and each part is a tuple.
    """
    n = len(seq)
    groups = []  # a list of lists, currently empty

    def generate_partitions(i):
        if i >= n:
            yield list(map(tuple, groups))
        else:
            for group in groups
                group.append(seq[i])
                yield from generate_partitions(i + 1)
                group.pop()

            groups.append([seq[i]])
            yield from generate_partitions(i + 1)
            groups.pop()

    if n > 0:
        return list(generate_partitions(0))
    else:
        return [[()]]

O algoritmo principal está na função generate_partitions aninhada. Basicamente, ele percorre a sequência e, para cada item, ele: 1) coloca o item em cada um dos grupos atuais (também conhecidos como partes) no conjunto de trabalho e se repete; 2) coloca o item em seu próprio grupo novo.

Quando chegamos ao final da sequência ( i == n ), produzimos uma cópia (profunda) do conjunto de trabalho que estamos construindo.

Agora, para obter partições de um tamanho específico, poderíamos simplesmente filtrar ou agrupar os resultados daqueles que procuramos e concluir com isso, mas essa abordagem realiza muito trabalho desnecessário (por exemplo, chamadas recursivas), se quisermos apenas partições de algum comprimento k .

Observe que na função acima, o comprimento de uma partição (ou seja, o número de grupos) aumenta sempre que:

            # this adds a new group (or part) to the partition
            groups.append([seq[i]])
            yield from generate_partitions(i + 1)
            groups.pop()

...É executado. Assim, limitamos o tamanho de uma partição simplesmente colocando uma proteção nesse bloco, da seguinte forma:

def partitions(seq, k):
    ...

    def generate_partitions(i):
        ...

            # only add a new group if the total number would not exceed k
            if len(groups) < k:
                groups.append([seq[i]])
                yield from generate_partitions(i + 1)
                groups.pop()

Adicionar o novo parâmetro e apenas essa linha à função de partitions agora fará com que ele gere apenas partições de comprimento até k . Isso é quase o que queremos. O problema é que o loop for ainda gera partições de comprimento menor que k .

Para remover essas ramificações recursivas, precisamos executar o loop for somente quando tivermos certeza de que temos elementos restantes suficientes em nossa sequência para expandir o conjunto de trabalho para um total de k grupos. O número de elementos restantes - ou elementos que ainda não foram colocados em um grupo - é n - i (ou len(seq) - i ). E k - len(groups) é o número de novos grupos que precisamos adicionar para produzir uma partição k válida. Se n - i <= k - len(groups) , não podemos desperdiçar um item adicionando-o a um dos grupos atuais - devemos criar um novo grupo.

Então, simplesmente adicionamos outra proteção, desta vez ao outro ramo recursivo:

    def generate_partitions(i):
        ...

            # only add to current groups if the number of remaining items
            # exceeds the number of required new groups.
            if n - i > k - len(groups):
                for group in groups:
                    group.append(seq[i])
                    yield from generate_partitions(i + 1)
                    group.pop()

            # only add a new group if the total number would not exceed k
            if len(groups) < k:
                groups.append([seq[i]])
                yield from generate_partitions(i + 1)
                groups.pop()

E com isso, você tem um gerador de partição k funcionando. Você provavelmente poderia recolher ainda mais algumas chamadas recursivas (por exemplo, se houver 3 itens restantes e precisarmos de mais 3 grupos, você já sabe que deve dividir cada item em seu próprio grupo), mas eu queria mostrar o funciona como uma ligeira modificação do algoritmo básico que gera todas as partições.

A única coisa que resta a fazer é classificar os resultados. Infelizmente, em vez de descobrir como gerar diretamente as partições na ordem desejada (um exercício para um cão mais inteligente), trapacei e apenas classifiquei a pós-geração.

def sorted_k_partitions(seq, k):
    ...
    result = generate_partitions(0)

    # Sort the parts in each partition in shortlex order
    result = [sorted(ps, key = lambda p: (len(p), p)) for ps in result]
    # Sort partitions by the length of each part, then lexicographically.
    result = sorted(result, key = lambda ps: (*map(len, ps), ps))

    return result

Um pouco auto-explicativo, exceto pelas funções principais. O primeiro:

key = lambda p: (len(p), p) 

diz para ordenar uma sequência por comprimento e depois pela própria sequência (que, em Python, é ordenada lexicograficamente por padrão). p significa "parte". Isso é usado para classificar as partes / grupos dentro de uma partição. Essa chave significa que, por exemplo, (4,) precede (1, 2, 3) , de modo que [(1, 2, 3), (4,)] seja classificado como [(4,), (1, 2, 3)] .

key = lambda ps: (*map(len, ps), ps) 
# or for Python versions <3.5: lambda ps: tuple(map(len, ps)) + (ps,)

O ps aqui significa "partes", plural. Este diz para ordenar uma sequência pelos comprimentos de cada um de seus elementos (que devem ser a própria sequência) e depois (lexicograficamente) pela própria sequência. Isso é usado para classificar as partições entre si, de modo que, por exemplo, [(4,), (1, 2, 3)] preceda [(1, 2), (3, 4)] .

Os seguintes:

seq = [1, 2, 3, 4]

for k in 1, 2, 3, 4:
    for groups in sorted_k_partitions(seq, k):
        print(k, groups)

produz:

1 [(1, 2, 3, 4)]
2 [(1,), (2, 3, 4)]
2 [(2,), (1, 3, 4)]
2 [(3,), (1, 2, 4)]
2 [(4,), (1, 2, 3)]
2 [(1, 2), (3, 4)]
2 [(1, 3), (2, 4)]
2 [(1, 4), (2, 3)]
3 [(1,), (2,), (3, 4)]
3 [(1,), (3,), (2, 4)]
3 [(1,), (4,), (2, 3)]
3 [(2,), (3,), (1, 4)]
3 [(2,), (4,), (1, 3)]
3 [(3,), (4,), (1, 2)]
4 [(1,), (2,), (3,), (4,)]

Seguindo os links úteis de @friendly_dog, estou tentando responder minha própria pergunta, aprimorando as funções usadas this post. Eu tenho uma solução grosseira que funciona, embora eu receie que não seja particularmente eficiente e possa usar alguma melhoria. Acabo gerando muito mais conjuntos de partições do que preciso e depois filtro os que diferem apenas por ordem de classificação.

Primeiro, tomo essas 3 funções das this :

import itertools
from copy import deepcopy

def slice_by_lengths(lengths, the_list):
    for length in lengths:
        new = []
        for i in range(length):
            new.append(the_list.pop(0))
        yield new

def partition(number):
    return {(x,) + y for x in range(1, number) for y in partition(number-x)} | {(number,)}

def subgrups(my_list):
    partitions = partition(len(my_list))
    permed = []
    for each_partition in partitions:
        permed.append(set(itertools.permutations(each_partition, len(each_partition))))

    for each_tuple in itertools.chain(*permed):
        yield list(slice_by_lengths(each_tuple, deepcopy(my_list)))

Em seguida, escrevo uma função que subgrups função de subgrups e a aplica a cada permutação da minha lista original. Eu percorro essas permutações de subgrupos e, se elas são iguais em comprimento ao número desejado de partições, as classifico de uma maneira que permita identificar duplicatas. Não tenho certeza se existe uma abordagem melhor para isso.

def return_partition(my_list,num_groups):
    filtered=[]
    for perm in itertools.permutations(my_list,len(my_list)):
        for sub_group_perm in subgrups(list(perm)):
            if len(sub_group_perm)==num_groups:
                #sort  within each partition
                sort1=[sorted(i) for i in sub_group_perm]
                #sort by first element of each partition
                sort2=sorted(sort1, key=lambda t:t[0])
                #sort by the number of elements in each partition
                sort3=sorted(sort2, key=lambda t:len(t))
                #if this new sorted set of partitions has not been added, add it
                if sort3 not in filtered:
                    filtered.append(sort3)
    return filtered

Executando-o na minha lista de exemplos original, vejo que ele produz a saída desejada, testada em duas partições e três partições.

>>> for i in return_partition([1,2,3,4],2):
...     print i    
... 
[[1], [2, 3, 4]]
[[4], [1, 2, 3]]
[[1, 2], [3, 4]]
[[3], [1, 2, 4]]
[[1, 3], [2, 4]]
[[2], [1, 3, 4]]
[[1, 4], [2, 3]]
>>> 

>>> for i in return_partition([1,2,3,4],3):
...     print i        
... 
[[1], [4], [2, 3]]
[[3], [4], [1, 2]]
[[1], [2], [3, 4]]
[[1], [3], [2, 4]]
[[2], [4], [1, 3]]
[[2], [3], [1, 4]]
>>> 




python