從給定數字集合中表示數字的方法

我想知道我們可以用多少種方式表示一個數字x作爲給定數字集合中的數字之和{a1.a2，a3，.. }。每個號碼可以被採取不止一次。從給定數字集合中表示數字的方法

例如，如果x = 4和A1 = 1，A2 = 2，則代表的方式X = 4：

1+1+1+1 
1+1+2 
1+2+1 
2+1+1 
2+2

因此方式= 5的數量。

我想知道是否存在公式或其他快速方法來做到這一點。我不能通過它蠻橫的力量。我想爲它編寫代碼。

注：x可以大到10^18。 a1，a2，a3，...的條數可以達到15，並且a1，a2，a3，......中的每一個也可以僅達到15.

來源

2011-11-06 Andrew

如果您只能使用每個數字一次，則此問題很難定義爲NP-Hard。我認爲對於每個號碼的無限制使用也是如此，儘管在此刻的減少不會突然出現在我的頭上 – amit

@Amit。是的，那麼它就成爲NP-Hard的子集合問題。但這不是。它與（限制）一個數字的構成有關，我想。 – Andrew

由於你想要認識到「不同」的方式，這很難。如果F（4）是3或32，那將會容易得多。 – harold

計算組合的數量可以在O(log x)中完成，不考慮在任意大小的整數上執行矩陣乘法所花費的時間。

組合的數量可以被配製爲復發。假設S(n)是通過添加集合中的數字來編號爲n的方法的數量。復發是

S(n) = a_1*S(n-1) + a_2*S(n-2) + ... + a_15*S(n-15),

其中a_ii是發生在該組的次數。另外，S（n）的n個< 0 = 0這種復發的可以以矩陣尺寸的A 15 * 15的角度來配製（或更小的在該組中的最大數量是更小）。然後，如果有一個列向量V含有

S(n-14) S(n-13) ... S(n-1) S(n),

則矩陣乘法的結果A*V將是

S(n-13) S(n-12) ... S(n) S(n+1).

的A矩陣的定義如下：

0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
a_15 a_14 a_13 a_12 a_11 a_10 a_9 a_8 a_7 a_6 a_5 a_4 a_3 a_2 a_1

其中a_i如上所定義。這個矩陣乘以S(n_14) ... S(n)向量的乘法的證明可以通過手動執行乘法立即看到;向量中的最後一個元素將等於n+1的重複的右側。非正式地，矩陣中的元素將列向量中的元素向上移動一行，並且矩陣的最後一行計算最新的項。

爲了計算復發的任意項S(n)是計算A^n * V，其中V等於

S(-14) S(-13) ... S(-1) S(0) = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1.

爲了得到運行到O(log x)，可以使用exponentiation by squaring計算A^n。

實際上，完全忽略列向量就足夠了，A^n的右下角元素包含所需值S(n)。

如果上述解釋很難遵循，我已經提供了一個C程序，它以上述方式計算組合的數量。注意它會很快溢出一個64位的整數。使用GMP可以獲得更高精度的浮點類型，但您無法得到確切的答案。

不幸的是，我看不到一個快速的方法來獲得數字的確切答案，如x=10^18，因爲答案可能比10^x大得多。

#include <stdio.h> 
typedef unsigned long long ull; 

/* highest number in set */ 
#define N 15 

/* perform the matrix multiplication out=a*b */ 
void matrixmul(ull out[N][N],ull a[N][N],ull b[N][N]) { 
    ull temp[N][N]; 
    int i,j,k; 
    for(i=0;i<N;i++) for(j=0;j<N;j++) temp[i][j]=0; 
    for(k=0;k<N;k++) for(i=0;i<N;i++) for(j=0;j<N;j++) 
    temp[i][j]+=a[i][k]*b[k][j]; 
    for(i=0;i<N;i++) for(j=0;j<N;j++) out[i][j]=temp[i][j]; 
} 

/* take the in matrix to the pow-th power, return to out */ 
void matrixpow(ull out[N][N],ull in[N][N],ull pow) { 
    ull sq[N][N],temp[N][N]; 
    int i,j; 
    for(i=0;i<N;i++) for(j=0;j<N;j++) temp[i][j]=i==j; 
    for(i=0;i<N;i++) for(j=0;j<N;j++) sq[i][j]=in[i][j]; 
    while(pow>0) { 
    if(pow&1) matrixmul(temp,temp,sq); 
    matrixmul(sq,sq,sq); 
    pow>>=1; 
    } 
    for(i=0;i<N;i++) for(j=0;j<N;j++) out[i][j]=temp[i][j]; 
} 

void solve(ull n,int *a) { 
    ull m[N][N]; 
    int i,j; 
    for(i=0;i<N;i++) for(j=0;j<N;j++) m[i][j]=0; 
    /* create matrix from a[] array above */ 
    for(i=2;i<=N;i++) m[i-2][i-1]=1; 
    for(i=1;i<=N;i++) m[N-1][N-i]=a[i-1]; 
    matrixpow(m,m,n); 
    printf("S(%llu): %llu\n",n,m[N-1][N-1]); 
} 

int main() { 
    int a[]={1,1,0,0,0,0,0,1,0,0,0,0,0,0,0}; 
    int b[]={1,1,1,1,1,0,0,0,0,0,0,0,0,0,0}; 
    solve(13,a); 
    solve(80,a); 
    solve(15,b); 
    solve(66,b); 
    return 0; 
}

來源

2011-11-07 18:29:18

非常好:-)清晰的方法和簡單的實施。 – Ante

@stubbscroll真棒男人！ – Andrew

由於訂單總數很重要，所以保留：

S(n, {a_1, ..., a_k}) = sum[ S(n - a_i, {a_1, ..., a_k}) for i in 1, ..., k ].

這對於動態編程解決方案已經足夠了。如果值S（i，set）從0到n創建，則複雜度爲O(n*k)。

編輯：只是一個想法。看一個總和爲(s_1, s_2, ..., s_m)的序列。序列的第一部分的總和將超過n/2大在一個點上，讓它成爲指數j：

s_1 + s_2 + ... + s_{j-1} < n/2, 
s_1 + s_2 + ... + s_j = S >= n/2.

最多有k不同數額S，併爲每個S最多有k可能最後元素s_j。所有的可能性(S,s_j) 3部分拆分序列和。

s_1 + s_2 + ... + s_{j-1} = L, 
s_j, 
s_{j+1} + ... + s_m = R.

它持有n/2 >= L, R > n/2 - max{a_i}。就這樣，上面公式具有更復雜的形式：

S(n, set) = sum[ S(n-L-s_j, set)*S(R, set) for all combinations of (S,s_j) ].

我不知道，但我認爲每個步驟中，將需要「創造」的 S(x,set)值範圍，其中範圍將由係數線性增長max{a_i}。

編輯2： @Andrew樣本。實施第一種方法很容易，它適用於'小'x。下面是Python代碼：

def S(x, ai_s): 
    s = [0] * (x+1) 
    s[0] = 1 
    for i in xrange(1,x+1): 
    s[i] = sum(s[i-ai] if i-ai >= 0 else 0 for ai in ai_s) 
    return s[x] 

S(13, [1,2,8]) 
S(15, [1,2,3,4,5])

此實現具有問題記憶大x（> 10^5在python）。由於只需要最後的max(a_i)值，因此可以使用循環緩衝區來實現它。

這些值增長非常快，例如， S（100000，[1,2,8]）爲〜10^21503。

來源

2011-11-06 14:31:21 Ante

我不能承受線性複雜性，因爲n可以高達10^18，我需要我的代碼在幾秒鐘內運行。不管怎麼說，多謝拉。 – Andrew

太慢解決方案 –

值得一提的是，這只是一個僞多項式解決方案.. – amit

如果你想找到所有可能的方法來表示一組數字N，那麼你應該遵循已經提出的動態規劃解決方案。

但是，如果你只是想知道方法的數量，那麼你正在處理restricted partition function problem。

受限分區函數P（N，DM）≡P（N，{D1，D2，...， DM}）是一個數字的n個分區成正整數{D1，D2的。。。，dm}，每個不大於n。

您還應該檢查關於partition function without restrictions的維基百科文章，其中沒有限制。

PS。如果負數也被允許，那麼可能有（無數）無限的方式來表示你的總和。

1+1+1+1-1+1 
1+1+1+1-1+1-1+1 
etc...

PS2。這是一個數學問題，而不是一個編程問題

來源

2011-11-06 15:38:12 pnezis

你能否給出一些具體的公式，以及一些計算洞察力。我需要編寫一個代碼。 PS：請注意，排序很重要，因此分區功能可能不足。是的，數字不能是負數 – Andrew

從給定數字集合中表示數字的方法

回答

相關問題