Алгоритм перебора выборочного пространства чисел

Я надеюсь, что это не обман, но сложно свести проблему к ключевым словам!

Это всегда то, о чем я задавался вопросом. Допустим, у вас есть черный ящик, который принимает на вход 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 приближается к двузначному числу.

Есть ли лучший способ сделать это, кроме вложенных операторов if, как я сделал?

Я знаю плохой способ сделать это, который состоит в том, чтобы случайным образом генерировать значения для каждой итерации и сохранять входные данные предыдущих итераций, чтобы вам не тыкать в черный ящик одними и теми же переменными дважды. Однако я надеялся на более быстрый метод, так как коллизии действительно сокращают время выполнения, поскольку количество уникальных вызовов черного ящика приближается к (max - min + 1) ^ n


person Catchwa    schedule 27.07.2010    source источник


Ответы (4)


Почему не используются вложенные циклы? Затем вы просто добавляете больше вложенных циклов по мере необходимости.

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

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, а не наоборот.

Редактировать:

Версия времени выполнения отличается от уже предложенной

Имре Л, кажется, попал в самую точку для версии в реальном времени, используя тот же тип языка, что и ваш вопрос (что-то вроде C), но, поскольку вы пометили это как языковой агностик, я решил попробовать что-то другое (к тому же, я сейчас изучаю Python, поэтому искал повод попрактиковаться).

Вот версия Python в реальном времени, в каждом случае x будет n-кортежем, например [1,0,3,2]. Единственное, что я скажу, это то, что это не включает max в пространство состояний (в приведенном ниже примере будет использоваться от 0 до 2 включительно, а не 3), поэтому вам придется увеличить max перед использованием.

import itertools 

min = 0
max = 3
n = 4

for x in itertools.product(range(min,max), repeat=n):
        blackBox( x )
person DMA57361    schedule 27.07.2010
comment
Вложенные циклы — хорошая идея! Я полагаю, мне было интересно, какой подход можно было бы использовать, если бы вы хотели указать во время выполнения количество переменных для итерации. Я немного перефразирую свой вопрос, чтобы отразить это. Кроме того, спасибо за исправление, я исправил свой вопрос :) - person Catchwa; 27.07.2010

Числа будут храниться в массиве 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]++;
  }
}
person Imre L    schedule 27.07.2010

Вот общее решение на 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 (поэтому вы можете использовать его для имитации счетчика в любой системе счисления и в любой «смешанной системе счисления»). Я добавил пример использования внизу.

person Eyal Schneider    schedule 27.07.2010

Вы можете думать о каждом входе в черный ящик как о n-значном числе в max - min + 1 системе счисления. . Например, если min = 3 и max = 12, то max - min + 1 == 10 и каждому входу в черный ящик соответствует n-значное число в десятичной системе. Просто переберите все числа от 0 до (max - min + 1)^n, декодируйте каждое число и передайте полученный вектор в черный ящик.

Вот реализация Java:

public static interface BlackBox {
    void consume(int... vector);
}

public static void iterateSample(int min, int max, int n, BlackBox bb) {
    int radix = max - min + 1;
    long limit = (long) Math.pow(radix, n);  /* Imprecise for larger numbers! */
    for (int i = 0; i < limit; i++) {
        int encoded = i;
        int[] decoded = new int[n];
        for (int j = 0; j < n; j++) {
            decoded[j] = min + (encoded % radix);
            encoded /= radix;
        }
        bb.consume(decoded);
    }
}
person Bolo    schedule 20.08.2011