-2

長さ n のリストを生成する必要があります。

  1. ドメイン [-1, 0, 1] の要素を持つ
  2. ちょうど k 個の非ゼロ要素を持つ

私の要素は [-1, 0, 1] の外積のサブセットになることを理解していますが、 iterables パッケージを使用して外積を生成し、「間違った」ものを削除することはできません。 n が 10 より大きい場合はタイムリーに。

実行可能な方法があるかどうか疑問に思っていますか？

注: 文脈上、問題は検索アルゴリズムを使用して円形計量マトリックスを生成することです。概念的な問題への洞察も高く評価されます。

4

3 に答える 3

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]
于 2013-03-28T18:54:44.290 に答える
0

大きなリストを作成して何かを削除しようとする代わりに、下からそれを構築しようとすることができます. 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]
于 2013-03-28T18:48:11.467 に答える
0

これはどうですか: 必要な数の -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)
于 2013-03-28T18:51:48.243 に答える