3

たとえば、リストto_beは次の要素で構成されます：3 of "a"、4 of "b"、3 of "c"、5 of "d".. ..

to_be = ["a", "a", "a", "b", "b", "b", "b", "c", "c", "c", "d", "d", "d", "d", "d", ...]

今、私はそれをこのようにしたいと思います：

done = ["a", "b", "c", "d", ... , "a", "b", "c", "d", ... , "b", "d", ...] (notice: some items are more than others as in amounts, but they need to be still in a pre-defined order, alphabetically for example)

これを行うための最速の方法は何ですか？

4

5 に答える 5

12

あなたが何を望んでいるかを理解していると仮定するとitertools.zip_longest、itertools.groupbyとを組み合わせることで比較的簡単に実行できitertools.chain.from_iterable()ます。

最初に項目をセット ( "a"s、"b"s など...) にグループ化し、必要な順序 (各セットから 1 つ) になるように圧縮し、chain を使用して 1 つのリストを作成し、次に削除します。圧縮によって導入されたNone値。

>>> [item for item in itertools.chain.from_iterable(itertools.zip_longest(*[list(x) for _, x in itertools.groupby(to_be)])) if item]
['a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'b', 'd', 'd']

ただし、もう少し読みやすくするために、リスト内包表記の一部を分離したい場合があります。

>>> groups = itertools.zip_longest(*[list(x) for _, x in itertools.groupby(to_be)])
>>> [item for item in itertools.chain.from_iterable(groups) if item]
['a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'b', 'd', 'd']

(指定されたバージョンは 3.x 用です。2.x の場合は、必要になりizip_longest()ます。)

いつものように、空の文字列や 0 などが予想される場合は、 を実行する必要があります。また、値if item is not Noneをそのままにしておく必要がある場合はNone、センチネル オブジェクトを作成し、それに対して ID をチェックします。

zip の代わりに、ドキュメントに記載されているレシピを使用するroundrobin()こともできます。これにより、次のように簡単になります。

>>> list(roundrobin(*[list(x) for _, x in itertools.groupby(to_be)]))
['a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'b', 'd', 'd']

最後の注意として、観察者は私がgroupby()ジェネレーターからリストを作成していることに気付くかもしれませんが、これは無駄に思えるかもしれません.理由はdocsから来ています:

返されるグループ自体は、基になる iterable を groupby() と共有するイテレータです。ソースが共有されているため、groupby() オブジェクトが進められると、前のグループは表示されなくなります。そのため、後でそのデータが必要になった場合は、リストとして保存する必要があります。

于 2012-11-15T04:05:44.163 に答える
2 
to_be = ["a", "a", "a", "b", "b", "b", "b", "c", "c", "c", "d", "d", "d", "d", "d"]
counts = collections.Counter(to_be)
answer = []
while counts:
    answer.extend(sorted(counts))
    for k in counts:
        counts[k] -= 1
    counts = {k:v for k,v in counts.iteritems() if v>0}

今、answer次のようになります。

['a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'b', 'd', 'd']
于 2012-11-15T04:07:39.463 に答える
1

これが最速かどうかはわかりませんが、これが私の刺し傷です。

>>> d = defaultdict(int)
>>> def sort_key(a):
...     d[a] += 1
...     return d[a],a
...

>>> sorted(to_be,key=sort_key)
['a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'b', 'd', 'd']

関数にラップ:

def weird_sort(x):
    d = defaultdict(int)
    def sort_key(a):
        d[a] += 1
        return (d[a],a)
    return sorted(x,key=sort_key)

もちろん、これには iterable の要素がハッシュ可能である必要があります。

于 2012-11-15T04:07:45.227 に答える
0

Lattywareのものより少しエレガントではありません：

import collections
def rearrange(l):
    counts = collections.Counter(l)
    output = []
    while (sum([v for k,v in counts.items()]) > 0):
        output.extend(sorted([k for k, v in counts.items() if v > 0))
        for k in counts:
            counts[k] = counts[k] - 1 if counts[k] > 0 else 0
    return counts
于 2012-11-15T04:08:03.643 に答える
0

「手動でステート マシン」を使って実行する方がはるかに効率的ですが、比較的小さなリスト (<5000) の場合は、これを行う Python グッズを利用しても問題はありません。

to_be = ["a", "a", "a", "b", "b", "b", "b", "c", "c", "c", "d", "d", "d", "d", "d","e", "e"]


def do_it(lst):
    lst = lst[:]
    result = []

    while True:
        group = set(lst)
        result.extend(sorted(group))
        for element in group:
            del lst[lst.index(element)]
        if not lst:
            break
    return result

done = do_it(to_be)

上記の関数の「大きな」複雑さは、本当に BIG になるはずです。私はそれを理解するためにイベントを起こしていませんでした。

于 2012-11-15T04:08:07.590 に答える