Многоразрядный счётчик из цифр по любому основанию (Java), как сделать?

Question

[Wan-Derer]

На вход мне прилетает целое положительное N
Мне надо сделать N разрядов, каждый из которых может принимать значения 0...(N-1) и перебрать их все.
Пример:
N=3
комбинации:
0 0 1
0 0 2
0 1 0
.......
2 2 2

N - это не обязательно цифра, это м.б., например, 27. Значит 27 разрядов, в каждом разряде 0...26.
Идея похожа на 16-ричные числа, но основание не 16, а произвольное. В Java есть Biginteger, который можно представлять по основаниям вплоть до 36. В принципе, неплохо, но хотелось бы более общее решение.

Т.е. беру младший разряд, щёлкаю его вверх, как только он достигает N - его обнуляю и щёлкаю вверх следующий разряд. Подозреваю что надо использовать рекурсию, но что-то не соображу как именно :) Подскажите алгоритм кто знает :)

Так же подозреваю что полный перебор сочетаний это стандартная задача, но в математике я довольно безграмотный :(

ЗЫ: вообще исходная задача проще (сложнее): комбинации д.б. не все, а только уникальных элементов, т.е. для N = 3 будет:
0
1
2
0 1 (1 0 это та же комбинация, поэтому не включаем)
0 2
1 2
0 1 2
но как сделать это имея полный перебор я (вроде) знаю - сделать Set>, комбинацию закидывать TreeSet, а готовые TreeSet уже в Set, вроде должно получиться то что надо.
Но если есть способ без полного перебора - поделитесь, буду благодарен :)

Answer 1

[Wan-Derer]

В общем, от идеи полного перебора пришлось отказаться - считает слишком долго. Пробовал и с рекурсией, и с представлением BigInteger по основанию N (штатным и самодельным) - не дождаться :)

Основную задачу решаю так. Допустим, N = 5. Тогда "максимальная" комбинация будет:
0, 1, 2, 3, 4
Все остальные будут получаться из неё выкидыванием элементов.
Сначала выкидываем по одному, потом по два и т.д. Т.е. мне надо перебрать не сами элементы, а их позиции. Я сделал что-то вроде двоичной маски, в которой "1" - оставляем элемент, "0" - выкидываем. Например:

0, 1, 2, 3, 4 - исходная комбинация
0, 1, 0, 1, 0 - маска

-, 1, -, 3, -> 1, 3 - результат

Осталось пройти по всем вариантам маски, а это просто инкремент целого - и все комбинации получены! Тоже небыстро, но гораздо быстрее полного перебора! Если кто-то знает как ещё можно ускорить - поделитесь :)
И да, собрать все комбинации в массив - тоже дохлая затея: память кончается очень быстро :) Приходится каждую комбинацию обрабатывать "на месте".

котт:

public class Part {
    public static void main(String[] args) {
        int numberOfThings = 41;
        long top = ((long) Math.pow(2, numberOfThings + 1));
        long bottom = ((long) Math.pow(2, numberOfThings)) + 1;

        int[] things = new int[numberOfThings];
        for (int i = 0; i < numberOfThings; i++) {
            things[i] = i;
        }

        while (bottom != top) {
            char[] mask = Long.toBinaryString(bottom++).toCharArray();

            List<Integer> comb = new ArrayList<>();
            for (int i = 0; i < numberOfThings; i++) {
                if (mask[i + 1] == '1') comb.add(things[i]);
            }

            // Обработка комбинации
            System.out.println(comb);
        }

    }
}