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

Допустим, у нас есть вектор длины 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-й итерации, имея вектор ith в лексикографическом порядке, который я упомянул выше. Наличие вектора ith необходимо для выполнения некоторого процесса в векторе (i+1)th. Эта схема экономит вычислительные ресурсы за счет случайного перебора всех возможных векторов.

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


java loops nested-loops lexicographic
person Vicarious    schedule 15.05.2019    source источник
comment
Проблема не ясна. Не могли бы вы быть немного более конкретным? Можете ли вы опубликовать код, если он у вас есть? Например, код нескольких реальных векторов, над которыми вы хотели бы работать.   -  person Jeremy Then    schedule 15.05.2019
comment
@JeremyThen у меня нет кодов. Но векторы, которые я упомянул в вопросе, — это именно те, над которыми я хочу работать. Единственная разница заключается в длине вектора и базе, которая может быть числом, отличным от 10.   -  person Vicarious    schedule 15.05.2019

Ответы (1)


arrow_upward
1
arrow_downward

Таким образом, в этом случае вы можете думать о каждом элементе как о числе по основанию 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;
}
person jspcal    schedule 15.05.2019
comment
Спасибо за ответ. Можете ли вы дать мне подсказку о реализации этого для какой-либо другой базы в Java? - person Vicarious; 15.05.2019
comment
Возможно, использовать Integer.toString(i, radix) для обработки разных баз? - person jspcal; 15.05.2019