거대한 순열 대상 집합 (파이썬 또는 R)

Question

목표 : 문자열 목록에서 얻은 모든 가능한 순열 세트를 얻고 싶습니다 (또는 함께 작업 할 수 있습니다). 파이썬에서

예 :

# 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')} 

을 지금은 이것이다 : 내 분석 ('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', 'A', 'B', 'B')과 동일 좋아,하지만 함께 작업하고 싶은 목록에는 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이기 때문입니다.

내가 원하는 작업은 다음과 같습니다. 먼저 해당 순열 공간의 고유 요소 수, 즉 세트 길이를 알고 싶습니다. 고유 한 요소의 수를 얻으려면 분석적으로 수행하는 것이 가능할 수 있지만 각 고유 요소의 빈도가 다르므로이를 수행하는 방법이 다릅니다.

두 번째 순열 세트에서 이러한 고유 한 요소의 샘플을 얻을 수 있기를 바랍니다.

제공되는 도움말에 감사드립니다. 독특한 순열의 수를 계산

최저

, 알레한드로는

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')}