Thuật toán để lặp qua không gian mẫu số

Question

Tôi hy vọng đây không phải là sự lừa đảo, nhưng thật khó để giải quyết vấn đề thành từ khóa!

Đây luôn là điều mà tôi đã tự hỏi. Giả sử bạn có một hộp đen mất n số nguyên làm đầu vào (trong đó n> 1). Cho rằng có một giới hạn về các giá trị số nguyên, làm thế nào bạn sẽ đi về viết một thuật toán sẽ đẩy toàn bộ không gian mẫu thông qua hộp đen? (Điểm thưởng nếu n có thể được quy định tại thời gian chạy)

nỗ lực của tôi khi n = 2 như sau:

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

Đoạn mã trên là tốt cho hai biến, nhưng như bạn có thể đoán, tôi thuật toán trở nên thực sự xấu khi các phương pháp n tiếp cận hai chữ số.

Có cách nào tốt hơn để làm điều này ngoài làm tổ nếu các câu như tôi đã làm không?

Tôi biết một cách xấu để thực hiện, sẽ tạo ngẫu nhiên các giá trị cho mỗi lần lặp và lưu các yếu tố đầu vào của các lần lặp trước, do đó bạn không poke hộp đen với cùng một biến hai lần. Tuy nhiên, tôi đã hy vọng cho một phương pháp nhanh hơn khi va chạm thực sự làm tổn thương thời gian thực hiện khi số lượng cuộc gọi hộp đen duy nhất đến gần (tối đa - min + 1)^n

Answer 1

Tại sao không sử dụng vòng lồng nhau? Sau đó, bạn chỉ cần thêm nhiều vòng lồng nhau khi cần thiết.

Có thể không quá hiệu quả nhưng bạn đã cho biết bạn cần che phủ không gian mẫu toàn bộ, vì vậy bạn sẽ phải chạy mọi kết hợp có thể có của các giá trị của biến đầu vào. có thể làm về hiệu quả trừ khi có thể chỉ đánh giá một phần không gian của tiểu bang.

int min = 0; 
int max = 9; 
for(int a = min ; a <= max ; ++a) 
    for(int b = min ; b <= max ; ++b) 
     blackBox(a , b); 

Ngoài ra, tôi nghĩ bạn sẽ tìm thấy số lượng cuộc gọi duy nhất là (max - min + 1)^n, không phải theo cách khác.

Edit:

Một thời gian chạy phiên bản khác nhau để đó đã gợi ý

Imre L dường như đã nhấn đinh trên đầu cho một phiên bản thời gian thực bằng cách sử dụng loại ngôn ngữ cùng như câu hỏi của bạn (một cái gì đó giống như C), nhưng vì bạn đã gắn thẻ này là ngôn ngữ bất khả tri, tôi đã quyết định thử một cái gì đó khác biệt (ngoài ra, tôi đang học Python vào lúc này vì vậy đang tìm kiếm một cái cớ để thực hành).

Đây là phiên bản theo thời gian thực của Python, trong mỗi trường hợp x sẽ là một bộ n, như [1,0,3,2]. Điều duy nhất tôi sẽ nói là điều này không không bao gồm max trong trạng thái không gian (trong ví dụ bên dưới nó sẽ sử dụng từ 0 đến 2, không phải 3) vì vậy bạn phải tăng max trước khi sử dụng.

import itertools 

min = 0 
max = 3 
n = 4 

for x in itertools.product(range(min,max), repeat=n): 
     blackBox(x) 

Answer 2

Dưới đây là một giải pháp chung chung, trong 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())); 
     } 
    } 
} 

Các nhà xây dựng nhận được giá trị tối đa cho mỗi vị trí. Giá trị tối thiểu luôn là 0 (do đó bạn có thể sử dụng nó để mô phỏng một bộ đếm trong bất kỳ cơ số nào và trong bất kỳ "hỗn hợp nào"). Tôi đã thêm một ví dụ sử dụng ở phía dưới.

Answer 3

Những con số sẽ được tổ chức trong mảng a sẽ được thiết lập tự động ví dụ như: int a[] = new int[n]

Nếu blackBox không thể được sửa đổi để có một mẫu như mảng sau đó bạn có thể viết một chức năng bao bọc xấu xí để gọi nó với nhau đếm các tham số hoặc bạn khá nhiều may mắn khi làm nó một cách linh hoạt.

mã (thủ tục) Pseudo:

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

Answer 4

Bạn có thể nghĩ của mỗi đầu vào cho các hộp đen như một số -digit n trong một hệ thống max - min + 1radix. Ví dụ: nếu min = 3 và max = 12, thì max - min + 1 == 10 và mỗi đầu vào vào hộp đen tương ứng với một số có chữ số n trong hệ thập phân. Chỉ cần lặp qua tất cả các số từ 0 đến (max - min + 1)^n, giải mã từng số và nạp véc-tơ kết quả vào hộp đen.

Dưới đây là một thực hiệ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); 
    } 
}