生成x個整數分區

我有一個遞歸算法，它可以生成給定數量的所有組合作爲參數。它也可以基於'k'做分區，這也可以作爲參數給出。只要我們輸入較小的數字，它就可以正常工作。但是隨着'n'的增加，計算結果需要更多的時間和空間。生成x個整數分區

是否有可能給出'x'作爲輸入，使算法只返回x分區的數量，而不是全部。下面是什麼我尋找一個例子：

輸入： N = 10， K = 4，分段N成「k'parts x = 2時，隔板的數目需要 M = 4，最大數在分區

輸出：

1）4,2,2,2

2）4,3,2,1

這裏是我使用的算法：

int h=0;  //iterator 
public ArrayList<int[]> generate_partitions(int n,int k,int max,boolean norep) 
{ 
    int korig; 
    korig = k; 
    int[] A = new int[korig+1]; 
    ArrayList<int[]> partitions = new ArrayList<int[]>(); 
    GenP(A, n, k, korig, 1,partitions,max); 
    if(norep) 
    { 
     for(int i=0; i<partitions.size(); i++) 
     { 
      if(check_repetition(partitions.get(i),max)) 
       partitions.remove(i); 
     } 
    } 
    return partitions; 
} 
boolean check_repetition(int[] a,int max) 
{ 
    boolean[] hash = new boolean[max+1]; 
    for(int i=0; i<max+1; i++) 
     hash[i]= false; 
    for(int i=0; i<a.length; i++) 
    { 
     if(hash[a[i]]==false) 
      hash[a[i]]=true; 
     else 
      return true; 
    } 
    return false; 
} 
void GenP(int[] A, int n, int k, int korig, int l, ArrayList<int[]> partitions,int max) 
{ 
    //n = number to partition 
    //korig = original k 
    //l = least number integer required in partition 
    if (k==1) // k = number of partitions 
    { 
     A[k]=n; 
     int [] temp = new int[korig]; 
     // System.out.println("size = "+korig); 
     boolean max_check = false; 
     for (int j=1; j<=korig; j++) 
     { 
      // System.out.print(A[j]+" "); 
      temp[j-1]=A[j]; 
      if(A[j]>max) 
       max_check = true; 
     } 
     if(!max_check) { 
      partitions.add(temp); 
     } 
     //System.out.println(); 
    } 
    else 
    { 
     if (k==0) 
     { 
      h=0; 
     } 
     else 
     { 
      h=n/k; 
      for (int i=l; i<=h; i++) 
      { 
       A[k]=i; 
       GenP(A, n-A[k], k-1, korig, A[k], partitions,max); 
      } 
     } 
    } 
}

來源

2014-07-20 faizanjehangir

如果您的代碼正常工作，請將其發佈在Code Review Stack Exchange上，因爲這不適用於SO社區 – ThreeFx

引入一個全局計數器（與h相同），將其初始化爲零。每次將分區添加到答案時，將計數器增加1.在對GenP進行遞歸調用後，檢查計數器是否已達到x，如果是，則立即從遞歸函數返回。

你的norep版本不會那麼容易修補。你的算法實際上是否發出重複？（你發佈的內容不是一個完整且可運行的Java代碼，所以我沒有運行它。）如果確實如此，那麼可以修補算法本身以僅發出唯一分區。有什麼確切的限制，但沒有明確說明（或者至少我一眼就看不清楚）。一旦你指定了你的問題的確切表達式，一個乾淨而高效的算法不會產生重複，這也許是一個單獨問題的話題。

來源

2014-07-20 16:51:02 Gassa

生成x個整數分區

回答

相關問題