È possibile rendere più efficiente questo algoritmo di permutazione raggruppato?

Question

È possibile rendere più efficiente questo algoritmo di permutazione raggruppato?

#1 da (4 voti)

1

Il seguente programma inizia con centinaia di permutazioni e le riduce a un piccolo set di risultati. Inoltre, sto solo cercando il primo risultato valido. Quali tecniche posso utilizzare per renderlo più efficiente?

#!/usr/bin/python3
from itertools import permutations, zip_longest


def get_result():
    checked = []
    for permutation in permutations_of_items_in_bins(items='aabbb', number_of_bins=3, items_per_bin=2):
        if permutation in checked:
            continue
        checked.append(permutation)
        if is_valid_result(permutation):
            return permutation
    # this is for debug only
    for x in sorted(checked):
        print(_format(x))
    return None


def is_valid_result(result):
    return False  # in reality, this may return True


# from: http://stackoverflow.com/questions/312443/how-do-you-split-a-list-into-evenly-sized-chunks
def _get_chunks(n, iterable, padvalue=None):
    "grouper(3, 'abcdefg', 'x') --> ('a','b','c'), ('d','e','f'), ('g','x','x')"
    return zip_longest(*[iter(iterable)]*n, fillvalue=padvalue)


def _format(iterable):
    return ','.join([''.join(c) for c in iterable])


def permutations_of_items_in_bins(items: str, items_per_bin: int, number_of_bins: int, pad='z'):
    # if not enough items to fit in all the bins, pad them with a value representing "empty"
    items = items.rjust(number_of_bins * items_per_bin, pad)
    # get all possible sort orders of the items
    _permutations = permutations(items)
    # that are unique
    unique_permutations = set(_permutations)

    # for each sort order, split them into bins in that order
    for permutation in unique_permutations:
        # split items into bins
        chunks = list(_get_chunks(items_per_bin, permutation))
        # item sort order in bins doesn't matter, so let's always sort the items in each bin
        normalized = [tuple(sorted(x)) for x in chunks]
        yield normalized


get_result()

"""
aa,bb,bz
aa,bz,bb
ab,ab,bz
ab,az,bb
ab,bb,az
ab,bz,ab
az,ab,bb
az,bb,ab
bb,aa,bz
bb,ab,az
bb,az,ab
bb,bz,aa
bz,aa,bb
bz,ab,ab
bz,bb,aa
"""

performance algorithms optimization python-3.x

posta Oleg 27.10.2016 - 01:11

fonte

1 risposta

Leggi altre domande sui tag performance algorithms optimization python-3.x

Qual è il nome di questo tipo di complessità? Notifiche in un'architettura di microservice: in Application Logic vs. Trigger di database

score 4 · Accepted Answer

Invece di generare tutto e rimuovere i duplicati, generali senza duplicati in primo luogo:

def permutations_of_items_in_bins(items, items_per_bin, number_of_bins, pad='z'):
    # Convert items to a dictionary that tracks how many we have of each
    pile = {}
    for item in items:
        try:
            pile[item] += 1
        except KeyError:
            pile[item] = 1

    # Pad to make sure we can generate combinations of the required length
    num_missing = items_per_bin * number_of_bins - sum(pile.values())
    if 0 < num_missing:
        try:
            pile[pad] += num_missing
        except KeyError:
            pile[pad] = num_missing

    # We need this for iteration on possibilities and for ordering the bins
    unique_items = list(sorted(pile.keys()))

    # While each combination is yielded the pile is updated to remove the items in that combination
    def combinations_consuming(size=items_per_bin, items=unique_items):
        if size == 0:
            yield ()
            return
        items = items[:]  # create a new list
        while items:
            item = items[0]
            if pile[item]:
                pile[item] -= 1
                for suffix in combinations_consuming(size - 1, items):
                    yield (item, *suffix)
                pile[item] += 1
            items.pop(0)

    def generate_bins(num=number_of_bins):
        if num == 0:
            yield ()
            return
        for combination in combinations_consuming():
            # The nested call to generate_bins will not be able to use the items already in combination
            for suffix in generate_bins(num - 1):
                yield (combination, *suffix)

    yield from generate_bins()