Увеличение массива уникальных чисел в порядке возрастания

Question

Итак, у меня есть этот массив, который содержит только уникальные числа и где число в индексе 0 самое низкое, а число в конце массива самое высокое.

Например, [1,2,3,4]

Теперь я увеличиваю каждый раз число сзади на 1. Но когда любой из чисел достигает определенной высоты, он должен увеличивать число слева.

Например, скажеммаксимальная высота будет 8.

[1,2,3,8] -> [1,2,4,5]

Теперь, пока здесь не работает мой код.Но когда последние 2 числа достигли максимальной высоты, третье больше не будет увеличиваться.

EG [1,2,7,8] -> [1,3,4,5]

Код, который я написал, является рекурсивным.

//Position is the index in the array of which element should be incremented by 1
public int[] increaseArray(int[] index, int maxIndex, int position) {
        int tmp = index[position];
        if (tmp < maxIndex) {
            index[position] = tmp + 1;
            return index;
        } else {
            if (positie != 0 && index[position - 1] + 2 <= maxIndex) {
                index[position] = index[position - 1] + 2;
                return increaseArray(index, maxIndex, position - 1);
            } else {
                return null;
            }
        }
    }

---

РЕДАКТИРОВАТЬ 1:

Полученный массив содержит только уникальные числа, так что да, int [2] максимально равно 7здесь.

Также я отредактировал код.Я чувствую, что я почти там, хотя последний номер все еще прослушивается ...

public int[] increaseIndex(int[] index, int maxIndex, int position) {
    int tmp = index[position];
    if (tmp < maxIndex + position - 2) {
        index[position] = tmp + 1;
        return index;
    } else {
        if (position > 0) {
                            //The following line of code is the problem...
            index[position] = index[position - 1] + 2;
            return increaseIndex(index, maxIndex, position - 1);
        } else {
            return null;
        }
    }
}

---

РЕДАКТИРОВАТЬ 2:

Действительно близко сейчас.Я исправил maxIndex, как сказал.Теперь есть небольшая ошибка, когда нужно увеличить более 2 чисел.

Код

public int[] increaseIndex(int[] index, int maxIndex, int position) {
    int size = index.length;
    int tmp = index[position];
    if (tmp < maxIndex - (size-position-1)) {
        index[position] = tmp + 1;
        return index;
    } else {
        if (position > 0) {
            //The following line is the problem i think...
            index[position] = index[position - 1] + 2;
            return increaseIndex(index, maxIndex, position - 1);
        } else {
            return null;
        }
    }
}

Это даст мне следующий вывод, например, с maxIndex 8, когда я использую следующий исполняемый код

int[] index = new int[] {1,2,3,4};
index = increaseIndex(index, row.length - 1, k - 2);
    while (index != null) {
        printArray(index);
        index = increaseIndex(index, row.length - 1, k - 2);
    }

---

[1, 2, 3, 4]
[1, 2, 3, 5]
[1, 2, 3, 6]
[1, 2, 3, 7]
[1, 2, 3, 8]
[1, 2, 4, 5]
[1, 2, 4, 6]
[1, 2, 4, 7]
[1, 2, 4, 8]
[1, 2, 5, 6]
[1, 2, 5, 7]
[1, 2, 5, 8]
[1, 2, 6, 7]
[1, 2, 6, 8]
[1, 2, 7, 8]
[1, 3, 4, 9] //wrong
[1, 3, 5, 6]
[1, 3, 5, 7]
[1, 3, 5, 8]
[1, 3, 6, 7]
[1, 3, 6, 8]
[1, 3, 7, 8]
[1, 4, 5, 9] //wrong
[1, 4, 6, 7]
[1, 4, 6, 8]
[1, 4, 7, 8]
[1, 5, 6, 9] //wrong
[1, 5, 7, 8]
[1, 6, 7, 9] //wrong
[2, 3, 8, 9] //wrong
[2, 4, 5, 10]//wrong
[2, 4, 6, 7]
[2, 4, 6, 8]
[2, 4, 7, 8]
[2, 5, 6, 9] //wrong
[2, 5, 7, 8]
[2, 6, 7, 9] //wrong
[3, 4, 8, 9] //wrong
[3, 5, 6, 10]//wrong
[3, 5, 7, 8]
[3, 6, 7, 9] //wrong
[4, 5, 8, 9] //wrong
[4, 6, 7, 10]//wrong
[5, 6, 8, 9] //wrong

Answer 1

Здесь другой подход без рекурсии.Он пробует все комбинации и отфильтровывает те, которые не являются уникальными.

Этот подход может быть легко адаптирован к ряду требований.

public static void main(String... args) {
    uniqueCombinations(4, 8);
}

private static void uniqueCombinations(int depth, int maxValue) {
    int[] ints = new int[depth];
    long combinations = (long) Math.pow(maxValue, depth);
    LOOP:
    for (long l = 0; l < combinations; l++) {
        long l2 = l;
        // create a combination.
        for (int i = ints.length - 1; i >= 0; i--) {
            ints[i] = (int) (l2 % maxValue + 1);
            l2 /= maxValue;
        }
        // check the combination.
        for (int i = 0; i < ints.length; i++)
            for (int j = i + 1; j < ints.length; j++)
                if (ints[i] == ints[j]) continue LOOP;
        // print a result.
        System.out.println(Arrays.toString(ints));
    }
}

отпечатки

[1, 2, 3, 4]
[1, 2, 3, 5]
[1, 2, 3, 6]
[1, 2, 3, 7]
[1, 2, 3, 8]
[1, 2, 4, 3]
.....
[8, 7, 5, 6]
[8, 7, 6, 1]
[8, 7, 6, 2]
[8, 7, 6, 3]
[8, 7, 6, 4]
[8, 7, 6, 5]

Answer 2

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

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

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

Что он делает на этом этапе, так или иначе, увеличивает его.

Возможно, вы захотите пропустить все позиции, которые уже находятся в maxIndex (или выше) с чем-то вроде:

while (position >= 0 && index[position] >= maxIndex) position--; 
if (position == -1) return; //in case all positions are already at maximum value

Answer 3

Вот оно в питоне:

def choose_iter(elements, length):
    for i in xrange(len(elements)):
        if length == 1:
            yield (elements[i],)
        else:
            for next in choose_iter(elements[i+1:len(elements)], length-1):
                yield (elements[i],) + next

выход:

>>> for res in choose_iter([1, 2, 3, 4, 5, 6, 7, 8], 4):
        print res


(1, 2, 3, 4)
(1, 2, 3, 5)
(1, 2, 3, 6)
(1, 2, 3, 7)
(1, 2, 3, 8)
(1, 2, 4, 5)
(1, 2, 4, 6)
(1, 2, 4, 7)
(1, 2, 4, 8)
(1, 2, 5, 6)
(1, 2, 5, 7)
(1, 2, 5, 8)
(1, 2, 6, 7)
(1, 2, 6, 8)
(1, 2, 7, 8)
(1, 3, 4, 5)
(1, 3, 4, 6)
(1, 3, 4, 7)
(1, 3, 4, 8)
(1, 3, 5, 6)
(1, 3, 5, 7)
(1, 3, 5, 8)
(1, 3, 6, 7)
(1, 3, 6, 8)
(1, 3, 7, 8)
(1, 4, 5, 6)
(1, 4, 5, 7)
(1, 4, 5, 8)
(1, 4, 6, 7)
(1, 4, 6, 8)
(1, 4, 7, 8)
(1, 5, 6, 7)
(1, 5, 6, 8)
(1, 5, 7, 8)
(1, 6, 7, 8)
(2, 3, 4, 5)
(2, 3, 4, 6)
(2, 3, 4, 7)
(2, 3, 4, 8)
(2, 3, 5, 6)
(2, 3, 5, 7)
(2, 3, 5, 8)
(2, 3, 6, 7)
(2, 3, 6, 8)
(2, 3, 7, 8)
(2, 4, 5, 6)
(2, 4, 5, 7)
(2, 4, 5, 8)
(2, 4, 6, 7)
(2, 4, 6, 8)
(2, 4, 7, 8)
(2, 5, 6, 7)
(2, 5, 6, 8)
(2, 5, 7, 8)
(2, 6, 7, 8)
(3, 4, 5, 6)
(3, 4, 5, 7)
(3, 4, 5, 8)
(3, 4, 6, 7)
(3, 4, 6, 8)
(3, 4, 7, 8)
(3, 5, 6, 7)
(3, 5, 6, 8)
(3, 5, 7, 8)
(3, 6, 7, 8)
(4, 5, 6, 7)
(4, 5, 6, 8)
(4, 5, 7, 8)
(4, 6, 7, 8)
(5, 6, 7, 8)

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