重複排列而不分配內存

Question

我正在尋找一種算法來生成列表中所有重複4個元素（長度2-1000）的排列。

Java implementation

的問題是，從上方alocates過多內存的鏈接計算的算法。它創建一個具有所有可能組合長度的數組。對於我的例子，例如4^1000。所以我得到了堆空間異常。

謝謝

Answer 1

如果沒有用於重複長度限制你的4個符號有一個非常簡單的算法，它會給你你想要的。只需將您的字符串編碼爲二進制數字，其中所有2位模式都對四個符號中的一個進行編碼。要獲得所有可能的重複排列，你只需要枚舉所有可能的數字。這可能會很長（超過宇宙年齡），因爲1000個符號的長度將是2000個比特。它真的是你想要做的嗎？堆溢出可能不是唯一的限制...

下面是一個簡單的C實現，枚舉所有重複的長度正好n（n限制在16000與32位無符號）沒有分配內存。我給讀者留下了列舉至多長度爲n的所有重複的練習。

#include <stdio.h> 

typedef unsigned char cell; 
cell a[1000]; 
int npack = sizeof(cell)*4; 

void decode(cell * a, int nbsym) 
{ 
    unsigned i; 
    for (i=0; i < nbsym; i++){ 
     printf("%c", "GATC"[a[i/npack]>>((i%npack)*2)&3]); 
    } 
    printf("\n"); 
} 

void enumerate(cell * a, int nbsym) 
{ 
    unsigned i, j; 
    for (i = 0; i < 1000; i++){ 
     a[i] = 0; 
    } 
    while (j <= (nbsym/npack)){ 
     j = 0; 
     decode(a, nbsym); 
     while (!++a[j]){ 
      j++; 
     } 
     if ((j == (nbsym/npack)) 
     && ((a[j] >> ((nbsym-1)%npack)*2)&4)){ 
      break; 
     } 
    } 
} 

int main(){ 
    enumerate(a, 5); 
} 

Answer 2

通用算法惰性計算世代長度X的所有排列（含重複）的一組選擇的Y：

for I = 0 to (Y^X - 1): 
    list_of_digits = calculate the digits of I in base Y 
    a_set_of_choices = possible_choices[D] for each digit D in list_of_digits 
    yield a_set_of_choices 

Answer 3

你知道如何計算：加1到那些地方，如果你去了9跳回到0，加1到幾十等。

所以，如果你有一個列表長度N在每個點K項目：

int[] permutations = new int[N]; 
boolean addOne() { // Returns true when it advances, false _once_ when finished 
    int i = 0; 
    permutations[i]++; 
    while (permutations[i] >= K) { 
    permutations[i] = 0; 
    i += 1; 
    if (i>=N) return false; 
    permutations[i]++; 
    } 
    return true; 
}