python - 生成带有约束的列表

Question

我需要生成一个长度为 n 的列表：

1. 具有来自域 [-1, 0, 1] 的元素
2. 正好有 k 个非零元素

我知道我的元素将是 [-1, 0, 1] 与自身的叉积的子集，但是简单地使用 iterables 包生成叉积然后删除“错误”的那些是不可能的及时换n大于10真的。

我想知道有没有可行的方法？

注意对于上下文，问题是使用搜索算法生成圆形加权矩阵。从概念上对问题的任何洞察力也值得赞赏。

Answer 1

问题简化为查找具有n-k零和k非零的列表，然后将非零特化为 -1 和 1。

您可以使用索引组合轻松完成此操作：

def gen_lists(n, k):
    for nzinds in itertools.combinations(range(n), n-k):
        l = [0] * n
        for nz in itertools.product([-1,1], repeat=n-k):
            for i,v in zip(nzinds, nz):
                l[i] = v
            yield l

样本输出：

>>> for l in gen_lists(3, 1):
...     print l
... 
[-1, -1, 0]
[-1, 1, 0]
[1, -1, 0]
[1, 1, 0]
[-1, 0, -1]
[-1, 0, 1]
[1, 0, -1]
[1, 0, 1]
[0, -1, -1]
[0, -1, 1]
[0, 1, -1]
[0, 1, 1]

Answer 2

与其试图列出一个大清单并删除一些东西，你可以尝试从底部开始构建它。制作 k 个非零元素。制作 nk 0 个元素。将它们放在一起，然后将混合物洗牌：

import random
k = 5
n = 10
non_zero = k * [1,-1]
random.shuffle(non_zero)
z = (n-k)*[0]
result = non_zero[0:k] + z
random.shuffle(result) # [0, 1, -1, 0, 1, 0, 1, -1, 0, 0]

Answer 3

怎么样：生成一个有序列表，其中包含您需要的 -1、0 和 1 的数量，并遍历该排序的所有排列。像这样：

import itertools

def generateLists(n, k):
    numberOfZeroes = n - k
    for numberOfOnes in range(0, k+1):
        numberOfNegativeOnes = k - numberOfOnes
        orderedList = [-1] * numberOfNegativeOnes + [0] * numberOfZeroes + [1] * numberOfOnes
        for possibleOrderings in itertools.permutations(orderedList):
            yield possibleOrderings

for i in generateLists(3, 2):
    print i

输出：

(-1, -1, 0)
(-1, 0, -1)
(-1, -1, 0)
(-1, 0, -1)
(0, -1, -1)
(0, -1, -1)
(-1, 0, 1)
(-1, 1, 0)
(0, -1, 1)
(0, 1, -1)
(1, -1, 0)
(1, 0, -1)
(0, 1, 1)
(0, 1, 1)
(1, 0, 1)
(1, 1, 0)
(1, 0, 1)
(1, 1, 0)