Pythonの限定組み合わせ

Question

私は200要素のリストを持っています。私はこれらの要素の長さkのすべての組み合わせの10％を無作為に計算し、その結果をリストに保存したいと思います。例えば

：

は['A', 'B', 'C', 'D']のよう'ABCD'を想定し、Iは長さ2の組み合わせこの場合、すべての可能な組み合わせは6になりたい（N /（（N-K）X k）は！！）。私は0.6 - > 1（ラウンドアップ）の10％を得たいと思っています。

私はitertools.combinations('ABCD', 2)を試しましたが、それは私にすべての組み合わせを与えます。

---

ここにいくつか私の問題に関する情報があります。

私は

all_points_coordinates = [ 
    [-1.6339171050450814, 2.5160117038362722], 
    [-1.7207293090531386, 2.4574561328669748], 
    [0.10469849010750323, 2.9981724810572872], 
] 

を持っていると私はそれらの3の組み合わせを計算し、

def all_way(points): 
    point = len(points) 
    allrout = [] 
    allrout = list(itertools.permutations(points, point)) 
    return allrout 

を使用したいが、それは私に私のポイントのすべての組み合わせを提供します。私が100ポイントを実行すると、非常に時間がかかるので、これらの組み合わせのうちの限られた数を計算したい。

Answer 1

あなたがそれらの小さなサブセットを選ぶ前に、事前にすべての組み合わせを計算したくない場合は、2つのオプションがあります。

1. 醜いのが、

   • シャッフル仕事をしていませんあなたのリストの要素。結果をセットに追加する
   • セットが希望の長さになるまで続けます。

2. 美しいが、複雑な

   • 指標< n個のリストを作成します！ （nはあなたのリストの要素の数である）
   • this questionに似各インデックス（のための組み合わせを計算し

Answer 2

オプション1（ランダムではないだけ必要なものを生成）。：

itertools.combinations()によって返された結果の最初の10％のパーセントを取る。

import itertools 
from math import factorial, ceil  

original = 'ABCD' 
k = 2 
percentage = 0.1 
configurations = factorial(len(original))/(factorial(len(original) - k) * factorial(k)) 
take = ceil(percentage * configurations) 
res = [] 
for i, comb in enumerate(itertools.combinations(original, k), 1): 
    res.append(comb) 
    if i == take: 
     break 
print(res, len(res)) 

---

2（ランダムしかし最初全リストを生成する）オプション：

がランダムitertools.combinations()によって返された結果の10％パーセントを取ります。 Python 3が必要です。6random.choices()

# Python 3.6 you can do this 
import random 
import itertools 
from math import factorial, ceil 

original = 'ABCD' 
k = 2 
percentage = 0.1 
configurations = factorial(len(original))/(factorial(len(original) - k) * factorial(k)) 
take = ceil(percentage * configurations) 
res = random.choices([x for x in itertools.combinations(original, k)], k=take) 

originalもリストすることができるからです。

Answer 3

もう少し単純な可能性：すべての組み合わせを生成しますが、ランダム変数が< 0.1の場合は、結果の組み合わせの10％程度にしてください。

>>> sum(1 for _ in itertools.combinations(range(100), 3)) # total count for comparison 
161700 
>>> res = [c for c in itertools.combinations(range(100), 3) if random.random() < 0.1] 
>>> len(res) 
16227 

random.sampleを使用した場合に比べ、これはまだ すべての組み合わせを生成し、それらの90％を廃棄しますが、それは、メモリにすべての組み合わせ を保つする必要がないという利点を有する

すぐに。また、結果は、おおよその組み合わせの10％になりますが、正確には一致しません。大量の場合、それはあまり問題にならないはずです。

Answer 4

random.sampleを使用してランダムな組み合わせを生成し、複数の組み合わせを何度も生成しないようにセットを使用できます。ここには簡単なデモがあります。

from random import seed, sample 

seed(42) 

def random_combinations(seq, size, num): 
    combos = set() 
    while len(combos) < num: 
     item = sample(seq, size) 
     combos.add(tuple(item)) 
    return list(combos) 

# test 

data = [ 
    (0, 1), (2, 3), (4, 5), (6, 7), (8, 9), 
    (10, 11), (12, 13), (14, 15), (16, 17), (18, 19), 
] 

# Make 20 random 3-element combinations 
combos = random_combinations(data, 3, 20) 
for i, item in enumerate(combos, 1): 
    print('{:>2}: {}'.format(i, item)) 

出力

1: ((2, 3), (12, 13), (8, 9)) 
2: ((6, 7), (18, 19), (4, 5)) 
3: ((2, 3), (16, 17), (18, 19)) 
4: ((0, 1), (4, 5), (12, 13)) 
5: ((14, 15), (10, 11), (4, 5)) 
6: ((2, 3), (0, 1), (8, 9)) 
7: ((6, 7), (16, 17), (0, 1)) 
8: ((12, 13), (2, 3), (8, 9)) 
9: ((6, 7), (14, 15), (8, 9)) 
10: ((10, 11), (18, 19), (8, 9)) 
11: ((0, 1), (14, 15), (2, 3)) 
12: ((18, 19), (10, 11), (6, 7)) 
13: ((18, 19), (12, 13), (0, 1)) 
14: ((10, 11), (8, 9), (4, 5)) 
15: ((8, 9), (2, 3), (6, 7)) 
16: ((2, 3), (0, 1), (6, 7)) 
17: ((16, 17), (6, 7), (12, 13)) 
18: ((2, 3), (12, 13), (18, 19)) 
19: ((0, 1), (2, 3), (6, 7)) 
20: ((6, 7), (10, 11), (2, 3)) 

tobias_kコメントで述べたようにnumは、組み合わせの総数に近すぎない場合、このコードは、適切です。 <の組み合わせの総数の50％が欲しい場合は、それでも問題はないが、それを超えると、既に生成されている組み合わせを再生成する可能性が高くなり、長い間ループする原因になります。このコードは異なる順序で、これら3対を含むタプル、例えば((2, 3), (8, 9), (12, 13))は異なることが((2, 3), (12, 13), (8, 9))を考慮することは

---

注意。

私たちは私たちのアイテムをセットにすることができますしたくない場合。これにはfrozensetを使用する必要があります。これは、通常のセットは変更可能であり、したがってハッシュできないため、アイテムを設定できないからです。

from random import seed, sample 

seed(42) 

def random_combinations(seq, size, num): 
    combos = set() 
    while len(combos) < num: 
     item = sample(seq, size) 
     combos.add(frozenset(item)) 
    return [tuple(u) for u in combos] 

# test 

data = [ 
    (0, 1), (2, 3), (4, 5), (6, 7), (8, 9), 
    (10, 11), (12, 13), (14, 15), (16, 17), (18, 19), 
] 

# Make 20 random 3-element combinations 
combos = random_combinations(data, 3, 20) 
for i, item in enumerate(combos, 1): 
    print('{:>2}: {}'.format(i, item)) 

1: ((0, 1), (2, 3), (6, 7)) 
2: ((0, 1), (2, 3), (8, 9)) 
3: ((16, 17), (6, 7), (0, 1)) 
4: ((12, 13), (2, 3), (18, 19)) 
5: ((12, 13), (2, 3), (8, 9)) 
6: ((12, 13), (18, 19), (0, 1)) 
7: ((8, 9), (4, 5), (10, 11)) 
8: ((16, 17), (2, 3), (18, 19)) 
9: ((8, 9), (6, 7), (14, 15)) 
10: ((0, 1), (4, 5), (12, 13)) 
11: ((8, 9), (10, 11), (18, 19)) 
12: ((10, 11), (6, 7), (2, 3)) 
13: ((0, 1), (14, 15), (2, 3)) 
14: ((10, 11), (18, 19), (6, 7)) 
15: ((8, 9), (2, 3), (6, 7)) 
16: ((4, 5), (6, 7), (18, 19)) 
17: ((8, 9), (4, 5), (2, 3)) 
18: ((16, 17), (4, 5), (6, 7)) 
19: ((16, 17), (6, 7), (12, 13)) 
20: ((4, 5), (10, 11), (14, 15)) 

Answer 5

出力Iこの

point= len(points) 
p=int(point*10/100) 
allrout = list(itertools.islice(itertools.permutations(points, point),p)) 
print(len(allrout)) 
return allrout