不分配内存的重复排列

Question

我正在寻找一种算法来生成列表中重复 4 个元素（长度 2-1000）的所有排列。

Java实现

问题在于上面链接中的算法分配了太多内存用于计算。它创建一个具有所有可能组合长度的数组。例如我的例子是 4^1000。所以我得到了堆空间异常。

谢谢

Answer 1

用于延迟评估生成一组选择 Y 的长度 X 的所有排列（具有重复）的通用算法：

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 2

如果 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 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;
}