Алгоритм для итерации через выборочное пространство чисел
Я надеюсь, что это не простофиля, но трудно изложить проблему кратко в ключевые слова!
Это всегда - что-то, о чем я задался вопросом. Скажем, у Вас есть черный квадрат, который берет n целые числа в качестве входа (где n> 1). Учитывая, что существует границы на целочисленных значениях, как Вы пошли бы о записи алгоритма, который продвинет все выборочное пространство через черный квадрат? (бонусные очки, если n может быть указан во времени выполнения),
Моя попытка, когда n = 2 следующие:
int min = 0;
int max = 9;
int a = min;
int b = min;
while(a <= max && b <= max)
{
blackBox(a, b);
a++;
if(a > max)
{
a = min;
b++;
}
}
Вышеупомянутый код хорошо для двух переменных, но как Вы могли бы предположить, мой алгоритм становится действительно ужасным, когда n приближается к двузначным цифрам.
Существует ли лучший способ сделать это кроме вложения, если операторы как я сделал?
Я знаю плохой способ сделать это, который должен был бы случайным образом генерировать значения для каждого повторения и сохранить исходные данные предыдущих повторений, таким образом, Вы не вводите черный квадрат по абсолютному адресу с теми же переменными дважды. Однако я надеялся на более быстрый метод, поскольку коллизии действительно повреждают время выполнения как количество уникальных подходов вызовов черного квадрата (макс. - минута + 1) ^ n
3 ответа
Почему не используются вложенные циклы? Затем вы просто добавляете дополнительные вложенные циклы по мере необходимости.
Возможно, это не слишком эффективно, но вы указали, что вам нужно покрыть все пространство выборки , поэтому вам придется заранее запускать все возможные комбинации значений входных переменных - так что я сомневаюсь вы можете многое сделать с эффективностью, если только невозможно оценить только часть пространства состояний.
int min = 0;
int max = 9;
for( int a = min ; a <= max ; ++a )
for( int b = min ; b <= max ; ++b )
blackBox( a , b );
Кроме того, я думаю, вы обнаружите, что количество уникальных вызовов равно (max - min + 1) ^ n , а не наоборот.
Редактировать:
Версия времени выполнения, отличная от уже предложенной
Имре L , похоже, попала в точку для версии в реальном времени, использующей тот же тип языка, что и ваш вопрос ( что-то вроде C), но, поскольку вы отметили это как языково-независимый, я решил попробовать что-то другое (к тому же я сейчас изучаю Python, поэтому искал повод попрактиковаться).
Вот версия Python для реального времени, в каждом случае x будет кортежем из n, например [1,0,3,2] . Единственное, что я скажу, это не включает max в пространство состояний (в приведенном ниже примере он будет использовать от 0 до 2 включительно, а не 3), поэтому вам придется увеличьте макс перед использованием.
import itertools
min = 0
max = 3
n = 4
for x in itertools.product(range(min,max), repeat=n):
blackBox( x )
Вот общее решение на Java:
public class Counter implements Iterator<int[]> {
private int[] max;
private int[] vector;
public Counter(int[] maxValues) {
this.max = maxValues;
this.vector = new int[maxValues.length];
}
public int[] next() {
if (!hasNext())
throw new NoSuchElementException();
int[] res = vector.clone();
int i = 0;
while (i < vector.length && vector[i] == max[i]) {
vector[i] = 0;
i++;
}
if (i == vector.length)
vector = null;
else
vector[i]++;
return res;
}
@Override
public boolean hasNext() {
return (vector != null);
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
public static void main(String[] args) {
Counter c = new Counter(new int[]{3});
while (c.hasNext()) {
System.out.println(Arrays.toString(c.next()));
}
}
}
Конструктор получает максимальные значения для каждой позиции. Минимум всегда равен 0 (поэтому вы можете использовать его для моделирования счетчика с любым основанием системы счисления и с любым "смешанным основанием"). Я добавил пример использования внизу.
Числа будут храниться в массиве a , который будет устанавливаться динамически, например: int a [] = new int [n]
Если blackBox не может быть изменен для получения образца в виде массива, тогда вы можете либо написать уродливую функцию-оболочку для ее вызова с другим количеством параметров, либо вам сильно не повезло с тем, что вы делаете это динамически.
(Процедурный) Псевдокод:
int min = 0;
int max = 9;
int a[] = array();
int count = length(a);
setToMinValue(a);
while(a[count-1] <= max)
{
blackBox(a); // or bb(a[0],a[1],...)
a[0]++;
//while next number needs to be increased
for (int i = 0; a[i] > max && i < count-1; i++) {
a[i] = min;
a[i+1]++;
}
}