蟒蛇解決矩陣的限制

Question

這裏的問題是：我有兩個向量A（1Xn）和B（1Xm），其中n> m。我正在尋找矩陣T（nXm），這樣AT = B。 T具有以下屬性：T的所有元素都是1或0。 T中每一行中的元素總和爲1.理想情況下，如果沒有完美的解決方案，我希望程序返回AT-B = 0中的許多元素的最佳解決方案。

下面是一個例子：

import numpy as np 

A = np.array([-1.051, 1.069, 0.132, -0.003, -0.001, 0.066, -0.28, 
       -0.121, 0.075, 0.006, 0.229, -0.018, -0.213, -0.11]) 
B = np.array([-1.051, 1.201, -0.003, -0.001, 0.066, -0.121, 0.075, 
       -0.045,-0.231, -0.11]) 

T = np.array([[1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
       [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
       [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
       [0, 0, 1, 0, 0, 0, 0, 0, 0, 0], 
       [0, 0, 0, 1, 0, 0, 0, 0, 0, 0], 
       [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
       [0, 0, 0, 0, 0, 0, 0, 1, 0, 0], 
       [0, 0, 0, 0, 0, 1, 0, 0, 0, 0], 
       [0, 0, 0, 0, 0, 0, 1, 0, 0, 0], 
       [0, 0, 0, 0, 0, 0, 0, 1, 0, 0], 
       [0, 0, 0, 0, 0, 0, 0, 1, 0, 0], 
       [0, 0, 0, 0, 0, 0, 0, 0, 1, 0], 
       [0, 0, 0, 0, 0, 0, 0, 0, 1, 0], 
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 1]]) 

# This should equal a vector of 0's 
print A.dot(T)-B 

Answer 1

我來的東西，但我不認爲這是完全滿意的。我寧願不必走這條路，因爲它很笨重。我首先嚐試1對1映射，因爲這是許多映射的常見解決方案。任何遺留下來的東西我都會重複所有的可能性。這有點凌亂。你也會注意到我對numpy來說相當陌生。我很感激任何有關如何改善這一點的反饋。謝謝。

def solver(B,A): 

    m=B.size 
    n=A.size 

    start=np.ones((1,n)) 
    start=np.concatenate((start,np.zeros((m-1,n))),axis=0).astype(np.int) 

    for i in xrange(0,m): 
     T=np.roll(start,i,axis=0) 
     test=B.dot(T)-A 
     if i==0: 
      matches=np.absolute(test)<.0001 
     else: 
      matches=np.vstack((matches,np.absolute(test)<.0001)) 

    rA=(A-B.dot(matches))[np.absolute(A-B.dot(matches))>.0001] 
    Amissing=A-B.dot(matches) 
    rB=(B-B*np.sum(matches,axis=1))[np.absolute(B-B*np.sum(matches,axis=1))>.0001] 
    Bmissing=B-B*np.sum(matches,axis=1) 

    rm=rB.size 
    rn=rA.size 

    rmxrn = np.arange(rm*rn).reshape(rm,rn) 
    dif=np.absolute(rA) 
    best=np.zeros(shape=(rm,rn)) 
    for i in xrange(0, 2**(rm*rn)): 
     arr = (i >> rmxrn) % 2 
     if np.amax(np.sum(arr,axis=1))>1 or np.sum(arr)>rm: 
      continue 
     else: 
      diftemp=rB.dot(arr)-rA 
      besttemp=arr 
      if np.sum(np.absolute(diftemp))<np.sum(np.absolute(dif)):    
       dif=diftemp 
       best=besttemp 
      if np.sum(np.absolute(dif)<.0001)==rn: 
       break 

    best=best.astype(np.bool) 
    matchesT=matches.T 
    bestT=best.T 

    newbestT=np.zeros(shape=(m,rn)).astype(np.bool).T 

    for x in xrange(0,rn): 
     counter=0 
     for i, value in enumerate(Bmissing): 
      if abs(Bmissing[i])>.0001: 
       newbestT[x,i]=bestT[x,counter] 
       counter=counter+1 

    for x in xrange(0,rn): 
     counter=0 
     for i, value in enumerate(Amissing): 
      if abs(Amissing[i])>.0001: 
       matchesT[i]=newbestT[counter] 
       counter=counter+1 

    return(matchesT.T) 

A=np.array([-1.051,1.201,-0.003,-0.001,0.066,-0.121,0.075,-0.045,-0.231,-0.11])    
B=np.array([-1.051,1.069,0.132,-0.003,-0.001,0.066,-0.28,-0.121,0.075,0.006,0.229,-0.018,-0.213,-0.11]) 

print solver(B,A)