Как перебрать все возможные векторы определенной длины в лексикографическом порядке?

Question

Допустим, у нас есть вектор длины 4, где каждый элемент может быть числом от 0 до 9. Например: <1, 8, 0, 3>

Вместо того, чтобы просто зацикливаться на всех 10 ^ 4 возможных векторах, я хочу зацикливаться в определенном порядке. Итак, я хочу начать с <0, 0, 0, 0>, перейти к <1, 0, 0, 0>, затем:

<2, 0, 0, 0>, <3, 0, 0, 0>, ..., <9, 0, 0, 0>, <0, 1, 0, 0>

и т. Д. (Обратите внимание на порядок в последних двух). Я не могу придумать способ написать это для переменной длины вектора.

Допустим, мы находимся в i-й итерации, имея i -й вектор в лексикографическом порядке, о котором я упоминал выше. Наличие вектора i необходимо для выполнения некоторого процесса в векторе (i+1). Эта схема экономит вычисления на случайном цикле по всем возможным векторам.

На самом деле я не нашел способа решения этой проблемы с помощью грубой силы и памяти. Особенно учитывая, что я должен иметь возможность поддерживать переменные длины векторов и разные диапазоны чисел для записей.

Answer 1

Таким образом, в этом случае вы можете думать о каждом элементе как о числе в базе 10. i -ый элемент - это i в основании 10 с цифрами, расположенными в обратном порядке.Например:

int[] indexToElement(int index, int base) {
    String string = Integer.toString(index, base);
    int[] element = new int[string.length()];

    for (int i = 0; i < string.length(); ++i) {
        element[i] = Character.digit(string.charAt(string.length() - i - 1), base);
    }

    return element;
}