xor-swap을 두 개 이상의 변수로 확장 할 수 있습니까?

Question

xor-swap을 두 개 이상의 변수, 예를 들어 n 변수로 확장하려고했습니다. 그러나 나는 아무데도 가지고있어 3*(n-1)보다 낫다.

두 정수 변수의

x1 및 x2이처럼를 교환 할 수 있습니다

swap(x1,x2) { 
    x1 = x1^x2; 
    x2 = x1^x2; 
    x1 = x1^x2; 
} 

을 그래서, 당신은 값 v1 ... vn와 x1 ... xn을 가정합니다. 분명히 당신은 연속적으로 적용 스왑하여 값을 "회전"할 수 있습니다

swap(x1,x2); 
swap(x2,x3); 
swap(x3,x4); 
... 
swap(xm,xn); // with m = n-1 

당신은 x1 = v2, x2 = v3, ..., xn = v1로 끝날 것입니다.

어느 것이 든 n-1 스왑이며, 각각 3 xors이며, (n-1)*3 xors가 남습니다.

더 빠른 알고리즘은 xor 및 할당 만 사용하고 추가 변수는없는 것으로 알고 있습니까?

Answer 1

일부 결과로 N = 3,4,5에 대한 무차별 대항 검색을 시도했으며 이들 모두가 수식에 동의합니다.

파이썬 코드 :

from collections import * 

D=defaultdict(int) # Map from tuple of bitmasks to number of steps to get there 
N=5 
Q=deque() 
Q.append((tuple(1<<n for n in range(N)), 0)) 
goal = (tuple(1<<((n+1)%N) for n in range(N))) 
while Q: 
    masks,ops = Q.popleft() 
    if len(D)%10000==0: 
     print len(D),len(Q),ops 
    ops += 1 
    # Choose two to swap 
    for a in range(N): 
     for b in range(N): 
      if a==b: 
       continue 
      masks2 = list(masks) 
      masks2[a] = masks2[a]^masks2[b] 
      masks2 = tuple(masks2) 
      if masks2 in D: 
       continue 
      D[masks2] = ops 
      if masks2==goal: 
       print 'found goal in ',ops 
       raise ValueError 
      Q.append((masks2,ops))