代码之家 › 专栏 › 技术社区 › Catchwa

数字样本空间的迭代算法

iteration numbers language-agnostic algorithm

Catchwa · 技术社区 · 14 年前

我希望这不是一个骗局,但它很难归结为关键字的问题!

这一直是我想知道的事情。假设你有一个黑盒子 n 整数作为输入(其中 &燃气轮机;1). 假设整数值有一个边界,你将如何编写一个算法来推动整个样本空间通过黑盒(如果在运行时可以指定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

4 回复 | 直到 14 年前

DMA57361 14 年前

为什么不使用嵌套循环?然后根据需要添加更多嵌套循环。

整个的

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,因此正在寻找练习的借口)。

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 )

Imre L 14 年前

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]++;
  }
}

Eyal Schneider 14 年前

以下是一个通用的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(因此您可以使用它来模拟任何基数和任何“混合基数”中的计数器)。我在底部添加了一个用法示例。

Bolo 13 年前

您可以将黑盒中的每个输入看作 n -a中的数字 max - min + 1 radix 系统。例如,如果 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);
    }
}