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

Question

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

Реализация Java

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

Спасибо

Answer 1

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

Если нет ограничения по длине для повторения ваших 4 символов, есть очень простой алгоритм, который даст вам то, что вы хотите. Просто закодируйте вашу строку в виде двоичного числа, где все 2-битные комбинации кодируют один из четырех символов. Чтобы получить все возможные перестановки с повторениями, вам просто нужно перечислить «подсчитать» все возможные числа. Это может быть довольно долго (больше, чем возраст вселенной), поскольку 1000 символов будут иметь длину 2000 бит. Это действительно то, что вы хотите сделать? Переполнение кучи может быть не единственным ограничением ...

Ниже приведена тривиальная реализация C, которая перечисляет все повторения длиной ровно n (n ограничено 16000 с 32-битным беззнаковым) без выделения памяти. Я оставляю читателю возможность перечислять все повторения не более длины п.

#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;
}