HUGEパーミュテーションオブジェクトのセット（PythonまたはR）

Question

目的：私は、文字列のリストから得られたすべての可能な置換の集合を取得したい（または扱うことができます）ようにしたいと思います。 Pythonで

例：（'A'位置を変更しているかもしれないが）私の分析('A', 'A', 'B', 'B')ため以来

import pandas as pd 
import itertools 

list1 = ['A', 'A', 'B', 'B'] 

# Get all permutations 
list1_perm = list(itertools.permutations(list1)) 

len(list1_perm) 
24 

list1_perm 
[('A', 'A', 'B', 'B'), 
('A', 'A', 'B', 'B'), 
('A', 'B', 'A', 'B'), 
('A', 'B', 'B', 'A'), 
('A', 'B', 'A', 'B'), 
('A', 'B', 'B', 'A'), 
('A', 'A', 'B', 'B'), 
('A', 'A', 'B', 'B'), 
('A', 'B', 'A', 'B'), 
('A', 'B', 'B', 'A'), 
('A', 'B', 'A', 'B'), 
('A', 'B', 'B', 'A'), 
('B', 'A', 'A', 'B'), 
('B', 'A', 'B', 'A'), 
('B', 'A', 'A', 'B'), 
('B', 'A', 'B', 'A'), 
('B', 'B', 'A', 'A'), 
('B', 'B', 'A', 'A'), 
('B', 'A', 'A', 'B'), 
('B', 'A', 'B', 'A'), 
('B', 'A', 'A', 'B'), 
('B', 'A', 'B', 'A'), 
('B', 'B', 'A', 'A'), 
('B', 'B', 'A', 'A')] 

は、('A', 'A', 'B', 'B')と同じであり、私は：

# Get set of permutations 
set1_perm = set(itertools.permutations(list1)) 

len(set1_perm) 
6 

set1_perm 
{('A', 'A', 'B', 'B'), 
('A', 'B', 'A', 'B'), 
('A', 'B', 'B', 'A'), 
('B', 'A', 'A', 'B'), 
('B', 'A', 'B', 'A'), 
('B', 'B', 'A', 'A')} 

さて、これはあります素晴らしいですが、私が扱うリストには481の文字列があり、異なる周波数の5つのユニークな文字列があります。

len(real_list) 
481 

len(set(real_list)) 
5 

# Count number of times each unique value appears 
pd.Series(real_list).value_counts() 
A 141 
B 116 
C 80 
D 78 
E 66 

これはitertools.permutations(real_list)の問題ではありませんが、setを取得したい場合は、時間がかかります。これは、順列の数が9.044272819E+1082であるためです。

私がしたいことは次のとおりです。 まず、その置換空間内のユニークな要素の数、つまりセットの長さを知りたいと思います。ユニークな要素の数を取得するには、解析的に行うことは可能かもしれませんが、それぞれの固有の要素の頻度が異なるため、その方法はありません。

第2回私は、順列のセット内のこれらのユニークな要素のサンプルを取得したいと考えています。

提供されているヘルプに感謝します。

ベスト、ユニークな順列の数を計算 アレハンドロ

Answer 1

は、単に式を適用の問題である - 私たちは知っている私たちがn明確な要素を持っていた、我々はn!順列を持っているでしょう。繰り返しの順列を考慮するには、反復文字の順列の各カウントで除算する必要があります。これは多項係数です。

だから、ユニークな数を生成するための単純な実装が

from math import factorial 
from functools import reduce 
from collections import Counter 

def perm_cnt(l): 
    denom = reduce(lambda x,y: x*factorial(y), Counter(l).values()) 
    return factorial(len(l)) // denom 

のようなものに見えるかもしれその後ユニークな順列からサンプリングすることは、おそらく最も単純にあなたのサンプル値を確保することによって達成されて、ユニークなまますべてのユニークな値とを生成しようとするのに対し、サンプリング。 itertoolsモジュールにはrecipeがあり、これは役に立ちます。random_permutation

def random_permutation(iterable, r=None): 
    "Random selection from itertools.permutations(iterable, r)" 
    pool = tuple(iterable) 
    r = len(pool) if r is None else r 
    return tuple(random.sample(pool, r)) 

ので

def uniq_sample(l, size): 
    s = set() 
    perm_size = perm_cnt(l) 
    cnt = 0 
    while cnt < min(perm_size, size): 
     samp = random_permutation(l) 
     if samp not in s: 
      s.add(samp) 
      cnt += 1 
    return s 

デモ

>>> perm_cnt(list1) 
6 

>>> perm_cnt(['a']*3 + ['b']*5 + ['d']*2) 
2520 

>>> perm_cnt(np.random.randint(10, size=20)) 
105594705216000 

>>> uniq_sample(list1, 4) 
{('A', 'A', 'B', 'B'), 
('B', 'A', 'A', 'B'), 
('B', 'A', 'B', 'A'), 
('B', 'B', 'A', 'A')}