Сгенерировать все подпоследовательности длины m из массива символов длины n, где n> = m на Java языке

Question

Я искал в Java оптимальный код для генерации всех подпоследовательностей длины m из символьного массива длины n, где n> = m.

Значение подпоследовательности здесь: https://en.wikipedia.org/wiki/Subsequence

Мой текущий псевдокод / ​​алгоритм ниже. Но не выглядит оптимизированным.

if (m <= 0)
    return;
for (i = 0; i < 2^n; i++) { // can use BigInteger if n > 64
    j = numberOfBitsSet(i); // assuming numberOfBitsSet is implemented
    if (j == m) {
        s = "";
        while((index = getIndexOfNextBitSet(i)) >= 0) { // assuming getIndexOfNextBitSet is implemented
            s = s + charArray[index]; // bit numbering starts from zero
        } // end of while
        System.out.println(s);
    } // end of if
} // end of for

Answer 1

Обычно решаю алгоритми c задач на C ++. Есть классная функция next_permutation, которая позволяет вам перемещаться по всем «перестановкам» последовательности. Если последовательность выглядит как «00110100», next_permutation даст вам «00111000» (оптимальным образом).

Я нашел пример реализации той же функции в java здесь .

Как это может помочь вам решить вашу проблему: инициализируйте последовательность с помощью n - m ведущих нулей, за которыми следуют m единиц. Используйте вашу генерацию основы маски. После этого выполните next_permutation. Сложность этого алгоритма n* subsequence_count. Это будет значительным улучшением, если вы знаете, что m следует определенным правилам, но снова вызовет огромное количество результатов, например, если n = 64 и m = 32.