排列与重复不分配内存 [英] Permutation with repetition without allocate memory

问题描述

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

I'm looking for an algorithm to generate all permutations with repetition of 4 elements in list(length 2-1000).

Java实现

的问题是，该算法从上方alocates过多内存进行计算的链接。它创建了所有可能的组合长度的数组。例如4 ^ 1000我的例子。所以我就堆空间异常。

The problem is that the algorithm from the link above alocates too much memory for calculation. It creates an array with length of all possible combination. E.g 4^1000 for my example. So i got heap space exception.

感谢您

推荐答案

如果没有长度限制为您4个符号的重复有一个非常简单的算法，会给你你想要的东西。只需连接$ C C的字符串作为一个二进制数$，所有2位模式连接code四个标志之一。为了获得具有重复所有可能的排列，你只需要枚举算所有可能的数字。这可能很长（超过了宇宙的年龄）为1000的符号将是2000位。是不是真的，你想做什么？堆溢出可能不是唯一的限制...

If there is not length limit for repetition of your 4 symbols there is a very simple algorithm that will give you what you want. Just encode your string as a binary number where all 2 bits pattern encode one of the four symbol. To get all possible permutations with repetitions you just have to enumerate "count" all possible numbers. That can be quite long (more than the age of the universe) as a 1000 symbols will be 2000 bits long. Is it really what you want to do ? The heap overflow may not be the only limit...

下面是一个简单的C语言实现，列举长度的所有重复恰好N（N限制在16000与32位无符号）不分配内存。我留给读者列举的所有重复最多长度为n的exercice。

Below is a trivial C implementation that enumerates all repetitions of length exactly n (n limited to 16000 with 32 bits unsigned) without allocating memory. I leave to the reader the exercice of enumerating all repetitions of at most length 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);
}

这篇关于排列与重复不分配内存的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！