Python itertools.product 使用方法

Question

我正在使用itertools这个包，想要创建一个包含900个值的数组，这个数组里有1、2和3的所有可能组合，然后把这个数组变成一个30乘30的矩阵。下面的代码可以做到这一点，并且运行得很好。

for data in itertools.product([1,2,3], repeat=900):
    datalist=list(data)
    landarray=np.asarray(datalist).reshape(30, 30)

不过，我希望每个值（1、2和3）在这个900个值的数组中恰好出现300次。谢谢你的帮助！

Answer 1

(哈哈) 你知道你的代码会生成大约10的430次方个矩阵吗？

就算是限制版，也会产生大约10的426次方个矩阵。

你可能要花费非常非常长的时间才能完成这个。

---

补充说明一下规模：

如果宇宙中的每一个原子（大约10的80次方个）

每秒能进行十亿亿次操作（10的18次方）

而且每次操作能处理十亿个矩阵（10的9次方）

如果你能用十亿个宇宙（10的9次方）

持续进行当前宇宙年龄的十亿倍（大约10的26秒）

那么你也只会完成大约十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的十亿分之一的百分之一。

(我开始感觉像卡尔·萨根了 ;-)

Answer 2

只需要把一个已经分布均匀的数组打乱一下就可以了。

landarray = np.repeat([1,2,3], 300)
np.random.shuffle(landarray)
landarray = landarray.reshape((30,30))

我可以保证你不会得到重复的 landarray。换句话说，你需要制作大约 [edit] 10^213 个 landarray，才有50%的机会会重复一次。

Answer 3

你想要生成所有的排列组合，数据来源是 np.repeat([1,2,3], 300) 这个多重集合。有一个算法可以在 O(1) 的时间内生成下一个排列。这里有一个简单的算法，它使用了C++ 的 std::next_permutation() 函数，并按照字典顺序打印出排列组合：

#!/usr/bin/env python
"""Print all multiset permutations."""
import pyximport; pyximport.install() # $ pip install cython
from next_permutation import next_permutation

n = 3
multiset = bytearray('a'*n + 'b'*n + 'c'*n)
print(multiset)
while next_permutation(multiset):
    print(multiset)

其中 next_permutation 模块是一个用 Cython 定义的 Python C 扩展模块：

# cython: boundscheck=False
#file: next_permutation.pyx
cimport cpython.array # support array.array() on Python 2
from libcpp cimport bool

ctypedef unsigned char dtype_t
ctypedef dtype_t* Iter

cdef extern from "<algorithm>" namespace "std":
   bool cpp_next_permutation "std::next_permutation" (Iter first, Iter last)

def next_permutation(dtype_t[:] a not None):
    return cpp_next_permutation(&a[0], &a[0] + a.shape[0])

要构建这个模块，需要指定语言为 C++：

#file: next_permutation.pyxbld
from distutils.extension import Extension

def make_ext(modname, pyxfilename):
    return Extension(name=modname,
                     sources=[pyxfilename],
                     language="c++")

输出

aaabbbccc
aaabbcbcc
aaabbccbc
aaabbcccb
aaabcbbcc
aaabcbcbc
aaabcbccb
aaabccbbc
aaabccbcb
aaabcccbb
aaacbbbcc
aaacbbcbc
aaacbbccb
aaacbcbbc
aaacbcbcb
aaacbccbb
..snip..
cccaabbba
cccabaabb
cccababab
cccababba
cccabbaab
cccabbaba
cccabbbaa
cccbaaabb
cccbaabab
cccbaabba
cccbabaab
cccbababa
cccbabbaa
cccbbaaab
cccbbaaba
cccbbabaa
cccbbbaaa

next_permutation() 函数可以接受任何支持缓冲区接口的东西，比如它支持 numpy 数组：

import numpy as np
multiset = np.repeat(np.array([1,2,3], dtype=np.uint8), 3)