1

Необходимо организовать полный перебор векторов длины n. Для того, чтобы на выходе было:

000
001
010
011
100
101
110
111

И так для любой длины. Чтобы были упорядочены лексикографически не обязательно. Просто чтобы был полный перебор всех вариантов.

И собственно, необходимо построить решение таким образом, чтобы это работало не только для двоичных векторов, но и для n-ичных. То есть так, чтобы на одном месте могло находиться любое число из {0,1,2,3,...,n}. Есть идеи?

9
  • 2
    Вам, вероятно, нужна будет функция перевода числа в его строковое представление в K-ичной системе счисления. Потом оборачиваете ее в цикл и получаете требуемый результат. 4 ноя 2017 в 10:58
  • @ВладимирМартьянов Это интересная идея, спасибо!
    – Kiryl A.
    4 ноя 2017 в 10:59
  • @ВладимирМартьянов Но, кстати, это сразу же накладывает ограничение на мощность перебора - не более чем 10+26, потому что тогда заканчиваются и буквы и цифры. То есть перебирать не удастся больше чем 36-ичный вектор. Быть может есть идеи по перебору без ограничения?
    – Kiryl A.
    4 ноя 2017 в 11:51
  • Способ выражения числа в K-ичной системе может быть любым и не ограничиваться буквами и цифрами 4 ноя 2017 в 11:53
  • @ВладимирМартьянов Нет, это понятно, и Ваша идея, безусловно,очень ценна. Просто в принципе эту задачу можно решить и с помощью 36 for'ов, например. По-индусски. Где каждый итератор просто принимает {0,1,..., n}. Но ведь можно же как-то эту конструкцию обратить в нормальный цикл...
    – Kiryl A.
    4 ноя 2017 в 11:55

1 ответ 1

0

Спустя два дня я нашёл ответ и быть может Вам это когда-нибудь пригодится, держите:

Покажу на примере троичных векторов (т.е. 0,1,2). Вся идея алгоритма держится на том, что мы идём итератором с правого края числа и пока нам на встретилась двойка (максимальное возможное число) инкрементируем крайнее число не равное 2. Как только крайнее число стало 2, то мы запускаем цикл, проезжаем через череду двоек и как только находим не 2, то инкрементируем это число. Разумеется, когда мы каждый раз что-то инкрементируем, то всё, что было до этого числа обнуляется.

    boolean rided = false;    //становится true если проехали через двойки
    int j = sent.size()-1;    //начинаем с последней цифры
                              //sent это ArrrayList <Integer>, в нём хранится изначально нулевой вектор нужной нам длины

    while (j >= 0) {
        sent.set(j,sent.get(j)+1);     //увеличиваем крайнюю ячейку на один

        while (j >= 0 && sent.get(j) == 2) { //поехали через череду двоек искать не двойку
            sent.set(j, 0);                  //по пути всё зануляем
            j-=1;                            //с шагом в одну цифру  
            rided = true;                    //обозначим, что мы проехали
        }

        if (rided  && j >= 0) {
            sent.set(j, sent.get(j)+1);  //и вот это первое не двоечное значение инкрементируем
              j=sent.size()-1;           //отступаем к последней цифре и поехали по новой
              rided = false;             //сбрасываем rided в false
         }
        }

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.