이 루프에서 순열 대칭성을 이용하는 방법은 무엇입니까?

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) 있습니다. 작품 아래에이 코드 (파이썬/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) 

실행 시간을 절반으로 줄였다. 그러나 지난 대칭 나는 시도 : 작동하지만,이 속도 증가의 또 다른 요인 근처에 저를 포기하지 않습니다

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.

or이 중복되는 주 소스처럼 보입니다. 허용 범위가 너무 넓습니다. 그러나 (a >= b) and (c >= d)은 너무 제한적입니다.

그러나 a + c >= b + d을 비교할 수 있습니다. 당신이 제 3 루프 내에서 ac으로 a + c을 절약 할 수있다 (어떤 경우) 몇 밀리 초 얻으려면 :

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