このループで順列対称性を利用する方法は？

Question

は、私は完全に4D配列を移入するためにそれを使用してい

f(a,b,c,d) = f(c,d,a,b) = -f(b,a,d,c) = -f(d,c,b,a)

次順列対称性を持つスカラー関数f(a,b,c,d)を持っています。作品の下にこのコード（のpython/numpyのを使用して）：

A = np.zeros((N,N,N,N)) 
for a in range(N): 
    for b in range(N): 
     for c in range(N): 
      for d in range(N): 
       A[a,b,c,d] = f(a,b,c,d) 

しかし、明らかに、私はこのコードのセクションの実行時間を削減するために対称性を利用したいと思います。私は試しました：

A = np.zeros((N,N,N,N)) 
ab = 0 
for a in range(N): 
    for b in range(N): 
     ab += 1 
     cd = 0 
     for c in range(N): 
      for d in range(N): 
       cd += 1 
       if ab >= cd: 
        A[a,b,c,d] = A[c,d,a,b] = f(a,b,c,d) 

実行時間を半分に短縮します。しかし、最後の対称性のために私が試した：動作しますが、2スピードアップのもう一つの要因に近い私を与えるものではありません

A = np.zeros((N,N,N,N)) 
ab = 0 
for a in range(N): 
    for b in range(N): 
     ab += 1 
     cd = 0 
     for c in range(N): 
      for d in range(N): 
       cd += 1 
       if ab >= cd: 
        if ((a >= b) or (c >= d)): 
         A[a,b,c,d] = A[c,d,a,b] = f(a,b,c,d) 
         A[b,a,d,c] = A[d,c,b,a] = -A[a,b,c,d] 

を。私は正当な理由でそれが正しいとは思わないが、理由を見ることはできない。

ここで、この特定の順列対称性をより良く活用するにはどうすればよいですか？

Answer 1

面白い問題！

N=3の場合、4つの要素で81の組み合わせが存在する必要があります。 あなたのループでは、あなたは156を作成します。

(a >= b) or (c >= d)にorが重複の主なソースのように見えますが、それはあまりにも許容的です。しかし、(a >= b) and (c >= d)はあまりにも制限的です。

でも、a + c >= b + dと比較できます。 、あなたは第三ループ内acとしてa + cを救うことができる（どちらかといえば）数msを得るために：

A = np.zeros((N,N,N,N)) 
ab = 0 
for a in range(N): 
    for b in range(N): 
     ab += 1 
     cd = 0 
     for c in range(N): 
      ac = a + c 
      for d in range(N): 
       cd += 1 
       if (ab >= cd and ac >= b+d): 
        A[a,b,c,d] = A[c,d,a,b] = f(a,b,c,d) 
        A[b,a,d,c] = A[d,c,b,a] = -A[a,b,c,d] 

このコードでは、我々は112個の組み合わせを作成するので、あなたの方法に比べて少ない重複がありますが、そこに可能性がありますいくつかの最適化が残っています。

更新

は、ここに私が作成した組み合わせの数を計算するために使用されるコードがあります：and not (a==b and c==d)で

from itertools import product 

N = 3 
ab = 0 

all_combinations = set(product(range(N), repeat=4)) 
zeroes = ((x, x, y, y) for x, y in product(range(N), repeat=2)) 
calculated = list() 

for a in range(N): 
    for b in range(N): 
     ab += 1 
     cd = 0 
     for c in range(N): 
      ac = a + c 
      for d in range(N): 
       cd += 1 
       if (ab >= cd and ac >= b + d) and not (a == b and c == d): 
        calculated.append((a, b, c, d)) 
        calculated.append((c, d, a, b)) 
        calculated.append((b, a, d, c)) 
        calculated.append((d, c, b, a)) 

missing = all_combinations - set(calculated) - set(zeroes) 

if missing: 
    print "Some sets weren't calculated :" 
    for s in missing: 
     print s 
else: 
    print "All cases were covered" 
    print len(calculated) 

、数はダウン88