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

Question

Приведенный ниже код перебирает все представленные символы, помещает их в строковый массив и затем после их хеширования проверяет введенный хешированный пароль. Эта логика прекрасно работает для паролей длиной до 5 символов, однако, когда я получаю до 6 символов, число перестановок (36 ^ 6) настолько велико, что возникает исключение из-за слишком большого размера массива.

Поэтому я пытаюсь изменить его, используя только строку, а не массив, чтобы остановить эту проблему с памятью, но не могу заставить ее работать, какие-либо очевидные предложения?

Answer 1

В дополнение к ответу Тобиаса.

Вот способ, которым вы можете использовать указанный алфавит , чтобы пройти через все его возможные комбинации, вплоть до определенной длины, и работать с каждой из них, не сохраняя их, если вы не обнаружите, что это совпадение .

// Depth first combinations
private static void combineRecurse(String base, char[] alphabet, int maxLen,
        Consumer<String> consumer) {
    if (base.length() < maxLen - 1) {
        for (int i = 0; i < alphabet.length; i++) {
            String newPermutation = base + alphabet[i];
            consumer.accept(newPermutation);
            combineRecurse(newPermutation, alphabet, maxLen, consumer);
        }
    } else {
        // the new permutiation will be the maxlength
        for (int i = 0; i < alphabet.length; i++) {
            consumer.accept(base + alphabet[i]);
        }
    }
}

public static void forEachCombination(char[] alphabet, int maxLen, Consumer<String> consumer) {
    if(alphabet == null || consumer == null || maxLen < 1) return;
    combineRecurse("", alphabet, maxLen, consumer);
}

public static void main(String[] args) {

    char[] alphabet = { ... };
    final String hashedPassword = SHA1(password);
    final int maxlen = 16;

    List<String> possiblePasswords = new ArrayList<>();
    forEachCombination(alphabet, maxlen, s -> {
        // System.out.println(s);
        if (SHA1(s).equals(hashedPassword)) {
            possiblePasswords.add(s);
        }
    });
}

Возможно, лучше сделать эту итеративную, нежели рекурсивную, но сейчас рекурсив прост в реализации и, вероятно, более понятен для новичка.

Answer 2

Вы можете просто перечислить все возможные пароли, содержащие буквы и цифры, считая от 0 до бесконечности и конвертируя число toString с основанием 36.

long k = 0;
while (true) {
    String pwd = Long.toString(k++, 36);
    if (SHA1(pwd).equals(hashedPassword)) {
        System.out.println(pwd);
    }
}

Здесь toString работает для базы до 36, используя [0-9a-z], т.е. она работает в вашем случае, но если вы хотите включить специальные символы, вам придется создать свою собственную функцию числа-пароля ( думаю деление и по модулю), но остальное остается прежним.

Таким образом, требование к памяти составляет O (1), но, конечно, сложность по-прежнему составляет O (36 ⁿ ) для паролей длиной до n символов.

---

Одна из проблем этого подхода заключается в том, что, как и во всех представлениях чисел, ведущие нули будут опущены, поэтому Long.toString никогда не выдаст пароль, начинающийся с 0 (кроме самого 0). Чтобы противостоять этому, вы можете использовать два вложенных цикла: внешний цикл, повторяющий число цифр в пароле, и внутренний цикл, повторяющий числа до 36 ^d и дополняющий строку начальными нулями, или цикл от 36 ^d до 2 * 36 ^d и обрежьте первую (ненулевую) цифру. Это может показаться намного более трудоемким, чем раньше, но на самом деле это просто вдвое больше паролей.

for (int d = 1; d < 3; d++) {
    long p = pow(36, d);
    for (long n = p; n < 2 * p; n++) {
        String pwd = Long.toString(n, 36).substring(1);
        System.out.println(n + " " + pwd);
    }
}

Выход:

0
1
...
z
00
01
...
zz