2回目の編集
わかりました、わかりました。シャッフルのようなサウンドを作ったのは、実際にはそうではありませんでした。これが答えです。もう少し複雑です。
まず紹介したいのはpprint. printこれは、物事を適切にフォーマットするバージョンにすぎません。
from pprint import pprint
pprint(items)
#>>> [{'brand': 'ibm', 'id': 1},
#>>> {'brand': 'ibm', 'id': 2},
#>>> {'brand': 'ibm', 'id': 3},
#>>> {'brand': 'ibm', 'id': 4},
#>>> {'brand': 'ibm', 'id': 5},
#>>> {'brand': 'ibm', 'id': 6},
#>>> {'brand': 'acer', 'id': 7},
#>>> {'brand': 'acer', 'id': 8},
#>>> {'brand': 'acer', 'id': 9},
#>>> {'brand': 'acer', 'id': 10},
#>>> {'brand': 'apple', 'id': 11},
#>>> {'brand': 'apple', 'id': 12}]
それはさておき、さあ、行きましょう。
アイテムをブランド別にグループ化します。
from collections import defaultdict
brand2items = defaultdict(list)
for item in items:
brand2items[item["brand"]].append(item)
pprint(brand2items)
#>>> {'acer': [{'brand': 'acer', 'id': 7},
#>>> {'brand': 'acer', 'id': 8},
#>>> {'brand': 'acer', 'id': 9},
#>>> {'brand': 'acer', 'id': 10}],
#>>> 'apple': [{'brand': 'apple', 'id': 11}, {'brand': 'apple', 'id': 12}],
#>>> 'ibm': [{'brand': 'ibm', 'id': 1},
#>>> {'brand': 'ibm', 'id': 2},
#>>> {'brand': 'ibm', 'id': 3},
#>>> {'brand': 'ibm', 'id': 4},
#>>> {'brand': 'ibm', 'id': 5},
#>>> {'brand': 'ibm', 'id': 6}]}
キーは気にしないので、値を取得できます。
items_by_brand = list(brand2items.values())
pprint(items_by_brand)
#>>> [[{'brand': 'apple', 'id': 11}, {'brand': 'apple', 'id': 12}],
#>>> [{'brand': 'ibm', 'id': 1},
#>>> {'brand': 'ibm', 'id': 2},
#>>> {'brand': 'ibm', 'id': 3},
#>>> {'brand': 'ibm', 'id': 4},
#>>> {'brand': 'ibm', 'id': 5},
#>>> {'brand': 'ibm', 'id': 6}],
#>>> [{'brand': 'acer', 'id': 7},
#>>> {'brand': 'acer', 'id': 8},
#>>> {'brand': 'acer', 'id': 9},
#>>> {'brand': 'acer', 'id': 10}]]
次に、結果をインターリーブします。基本的な考え方は、使い果たすのに最も時間がかかるため、最大のプールからより頻繁に取得したいということです。したがって、反復ごとに最も長く、popその項目の 1 つを取得したいのですが、繰り返したくないだけです。これを行うには、2 つの異なるグループ (最大の 2 つ) を取り、それらの結果をインターリーブします。
どのグループにもアイテムが残っていない場合は停止します。
from heapq import nlargest
shufflatored = []
while any(items_by_brand):
items1, items2 = nlargest(2, items_by_brand, key=len)
if items1: shufflatored.append(items1.pop())
if items2: shufflatored.append(items2.pop())
このheapqモジュールはあまり知られていませんが、流血の素晴らしいモジュールです。実際、かなりの努力をすれば、これをitems_by_brandヒープとして保持することでより効率的にすることができます。ただし、ヒープを操作するための他のツールはkeys を使用しないため、努力する価値はありません。これにはあいまいな回避策が必要です。
それだけです。ダブルアップを許可したい場合は、置き換えることができます
if items1: shufflatored.append(items1.pop())
if items2: shufflatored.append(items2.pop())
と
if items1: shufflatored.append(items1.pop())
if items1: shufflatored.append(items1.pop())
if items2: shufflatored.append(items2.pop())
if items2: shufflatored.append(items2.pop())
!
編集
決定論的なものが欲しいですか？え、なんで言わなかったの？
lst = list(range(20))
lst[::2], lst[1::2] = lst[1::2], lst[::2]
lst
#>>> [1, 0, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14, 17, 16, 19, 18]
魔法ですね。
値をその場で交換するこの方法について知っていることを願っています。
a = 1
b = 2
a, b = b, a
a
#>>> 2
b
#>>> 1
さて、lst[::2]他のすべての値は
lst[::2]
#>>> [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
lst[1::2]は他のすべての値であり、
lst[1::2]
#>>> [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
そのためlst[::2], lst[1::2] = lst[1::2], lst[::2]、他のすべての値を他のすべての値と交換します!
import random
items = [1,1,1,2,2,2,2,3,3,3,3,3,4,4,4,4,4,4]
[
iv[1] for iv in
sorted(
enumerate(items),
key=lambda iv: iv[0]+random.choice([-1, 1])
)
]
#>>> [1, 1, 2, 1, 2, 2, 3, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4]
[
iv[1] for iv in
sorted(
enumerate(range(20)),
key=lambda iv: iv[0]+random.choice([-1, 1])
)
]
#>>> [0, 2, 1, 4, 3, 5, 6, 7, 9, 8, 11, 10, 12, 14, 13, 15, 17, 16, 18, 19]
これはランダムシャッフルであるため、最初のリストにはほとんどのシャッフルが表示されません。選択された結果は、すべての可能性から手作業で選択されます。
基本的に、このアルゴリズムはリストを受け取り、それにインデックスを付けます。
items a b c d e f g h i j
indexes 0 1 2 3 4 5 6 7 8 9
次に、インデックス + からのランダムな選択で並べ替えます[-1, 1]。
items a b c d e f g h i j
indexes 0 1 2 3 4 5 6 7 8 9
sort by 1 0 3 2 5 4 5 6 9 8
そして結果は
items b a d c f e g h j i
indexes 1 0 3 2 5 4 6 7 9 8
sort by 0 1 2 3 4 5 5 6 8 9
そしてシャッフルです。シャッフルの種類を変更するには、たとえばシャッフルを多かれ少なかれ行うには、 list の詳細を変更します[-1, 1]。[-1, 0, 1]、[0, 1]および他のバリエーションを試すこともできます。
ステップのアルゴリズム:
indexed = enumerate(items)
shuffled = sorted(indexed, key=lambda iv: iv[0]+random.choice([-1, 1]))
# Remove the index, extract the values out again
result = [iv[1] for iv in shuffled]
さて、効率。
あなたが非常に鋭い人なら、ソートが伝統的に行われていることに気付くかもしれませんO(n log n)。Python は、優れたソート アルゴリズムである TimSort を使用します。比較ソート (別名、値を比較するソート) には、少なくともの上限が必要ですが、下限は!と低くO(n log n)することもできます。O(n)
これは、ソート済みかどうかを確認する限り、ソート済みのリストをソートするのは簡単だからです。TimSort には「ソート済み」というローカライズされた概念があり、値がソートされていることを非常に迅速に検出します。O(kn)これは、それらが多少シャッフルされているだけであるため、TimSortがkリストの「シャッフルネス」に近い何かを実行することを意味しますlog n。