Перестановка с повторением без выделения памяти

Я ищу алгоритм для генерации всех перестановок с повторением 4 элементов в списке (длина 2-1000).

Реализация Java

Проблема в том, что алгоритм из ссылки выше выделяет слишком много памяти для вычислений. Он создает массив с длиной всех возможных комбинаций. Например, 4 ^ 1000 для моего примера. Итак, я получил исключение для кучи.

Спасибо


algorithm permutation
person user12384512    schedule 16.10.2010    source источник
comment
Не кажется ли вам, что попытка сгенерировать 4 ^ 1000 комбинаций займет проблематичное количество времени, даже если ваш алгоритм работает в постоянном пространстве?   -  person Reid Barton    schedule 17.10.2010

Ответы (3)


arrow_upward
2
arrow_downward

Если для повторения ваших 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);
}
person kriss    schedule 16.10.2010

arrow_upward
3
arrow_downward

Обобщенный алгоритм генерации с ленивой оценкой всех перестановок (с повторением) длины 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
person Amber    schedule 16.10.2010

arrow_upward
0
arrow_downward

Вы умеете считать: прибавьте 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;
}
person Rex Kerr    schedule 17.10.2010