一组巨大的置换对象（在Python或R中）

Question

目标：我想从字符串列表中获得（或能够使用）一组所有可能的排列。你知道吗

Python示例：

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')与('A', 'A', 'B', 'B')相同，（尽管'A'可能改变了位置），我确实：

# 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。你知道吗

我想做的是： 首先我想知道排列空间中唯一元素的数目，即集合的长度。为了得到唯一元素的数量，可以用解析的方法来计算，但是由于每个唯一元素的频率是不同的，我不知道该怎么做。你知道吗

第二，我希望能够得到排列集合中那些独特元素的样本。你知道吗

如果能提供任何帮助，我将不胜感激。你知道吗

最好的， 亚历杭德罗

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