c++ - 将值均匀分布到数组中

Question

我有一个大小为 8 的固定大小的 bool 数组。数组中所有元素的默认值为 false。 1-8之间会有多个真值需要填充。

我希望分布的真值尽可能远离彼此。我也希望能够随机化配置。在这种情况下，数组环绕，因此位置 7 位于数组中位置 0 的“旁边”。

这里有一些填充值的例子。我没有包括所有可能性，但希望它能理解我的观点。

1: [1, 0, 0, 0, 0, 0, 0, 0] 或 [0, 1, 0, 0, 0, 0, 0, 0]

2: [1, 0, 0, 0, 1, 0, 0, 0] 或 [0, 1, 0, 0, 0, 1, 0, 0]

3: [1, 0, 0, 1, 0, 0, 1, 0] 或 [0, 1, 0, 0, 1, 0, 0, 1]

4: [1, 0, 1, 0, 1, 0, 1, 0] 或 [0, 1, 0, 1, 0, 1, 0, 1]

5: [1, 1, 0, 1, 1, 0, 1, 0]

6: [1, 1, 0, 1, 1, 1, 0, 1]

7: [1, 1, 1, 1, 1, 1, 1, 0]

8: [1, 1, 1, 1, 1, 1, 1, 1]

到目前为止我想出的最接近的解决方案并没有完全产生我正在寻找的结果......

我试图用 C++ 编写它，但到目前为止，这是我的算法的一些伪代码...不太明白我想要什么

truths = randBetween(1, 8)
values = [0,0,0,0,0,0,0,0]
startPosition = randBetween(0, 7) //starting index
distance = 4

for(i = 0; i < truths; i++) {
    pos = i + startPosition + (i * distance)
    values[pos % 8] = 1
}

这是我当前代码的示例输出。那些标有星号的是不正确的。

[0, 0, 0, 0, 1, 0, 0, 0]
[0, 1, 0, 0, 1, 0, 0, 0]*
[0, 1, 0, 0, 1, 0, 1, 0]
[0, 1, 0, 1, 1, 0, 1, 0]*
[1, 1, 0, 1, 1, 0, 1, 0]
[1, 1, 0, 1, 1, 1, 1, 0]*
[1, 1, 1, 1, 1, 1, 1, 0]
[1, 1, 1, 1, 1, 1, 1, 1]

我正在寻找一种简单的方法来在整个数组中均匀分布真值，而无需为特殊情况编写代码。

Answer 1

检查一下:

#include <cassert>
#include <vector>
#include <iostream>
#include <iomanip>

/**
 * Generate an even spaced pattern of ones
 * @param arr destination vector of ints
 * @param onescnt the requested number of ones
 */
static inline
void gen(std::vector<int>& arr, size_t onescnt) {
    const size_t len = arr.size();
    const size_t zeroscnt = len - onescnt;
    size_t ones = 1;
    size_t zeros = 1;

    for (size_t i = 0; i < len; ++i) {
        if (ones * zeroscnt < zeros * onescnt) {
            ones++;
            arr[i] = 1;
        } else {
            zeros++;
            arr[i] = 0;
        }
    }
}

static inline
size_t count(const std::vector<int>& arr, int el) {
    size_t cnt = 0;
    for (size_t i = 0; i < arr.size(); ++i) {
        cnt += arr[i] == el;
    }
    return cnt;
}

static inline
void gen_print(size_t len, size_t onescnt) {
    std::vector<int> arr(len);
    gen(arr, onescnt);
    std::cout << "gen_printf(" << std::setw(2) << len << ", " << std::setw(2) << onescnt << ") = {";
    for (size_t i = 0; i < len; ++i) {
        std::cout << arr[i] << ",";
    }
    std::cout << "}\n";
    assert(count(arr, 1) == onescnt);

}

int main() {
    for (int i = 0; i <= 8; ++i) {
        gen_print(8, i);
    }
    for (int i = 0; i <= 30; ++i) {
        gen_print(30, i);
    }
    return 0;
}

生成:

gen_printf( 8,  0) = {0,0,0,0,0,0,0,0,}
gen_printf( 8,  1) = {0,0,0,0,0,0,0,1,}
gen_printf( 8,  2) = {0,0,0,1,0,0,0,1,}
gen_printf( 8,  3) = {0,1,0,0,1,0,0,1,}
gen_printf( 8,  4) = {0,1,0,1,0,1,0,1,}
gen_printf( 8,  5) = {1,0,1,1,0,1,0,1,}
gen_printf( 8,  6) = {1,1,0,1,1,1,0,1,}
gen_printf( 8,  7) = {1,1,1,1,1,1,0,1,}
gen_printf( 8,  8) = {1,1,1,1,1,1,1,1,}
gen_printf(30,  0) = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,}
gen_printf(30,  1) = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,}
gen_printf(30,  2) = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,}
gen_printf(30,  3) = {0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,}
gen_printf(30,  4) = {0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,}
gen_printf(30,  5) = {0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,}
gen_printf(30,  6) = {0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,}
gen_printf(30,  7) = {0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,1,}
gen_printf(30,  8) = {0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,}
gen_printf(30,  9) = {0,0,1,0,0,1,0,0,0,1,0,0,1,0,0,1,0,0,0,1,0,0,1,0,0,1,0,0,0,1,}
gen_printf(30, 10) = {0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,}
gen_printf(30, 11) = {0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,}
gen_printf(30, 12) = {0,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1,}
gen_printf(30, 13) = {0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,}
gen_printf(30, 14) = {0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,}
gen_printf(30, 15) = {0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,}
gen_printf(30, 16) = {1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,}
gen_printf(30, 17) = {1,0,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,0,1,0,1,}
gen_printf(30, 18) = {1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,}
gen_printf(30, 19) = {1,0,1,1,0,1,1,0,1,0,1,1,0,1,1,0,1,1,0,1,0,1,1,0,1,1,0,1,0,1,}
gen_printf(30, 20) = {1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,}
gen_printf(30, 21) = {1,1,0,1,1,0,1,1,0,1,1,1,0,1,1,0,1,1,0,1,1,1,0,1,1,0,1,1,0,1,}
gen_printf(30, 22) = {1,1,0,1,1,1,0,1,1,1,0,1,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,0,1,}
gen_printf(30, 23) = {1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,}
gen_printf(30, 24) = {1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,}
gen_printf(30, 25) = {1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,}
gen_printf(30, 26) = {1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,}
gen_printf(30, 27) = {1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,}
gen_printf(30, 28) = {1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,}
gen_printf(30, 29) = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,}
gen_printf(30, 30) = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,}

@edit - 更好的均匀间隔图案。

解释:

所以让我们采用 8 整数数组，我们希望有 5 个整数。在具有 8 个元素和 5 个元素的序列中，(一/零)的理想比率应该是 (5/3)。我们永远不会接近这样的比例，但我们可以尝试。

想法是循环遍历数组并记住我们在数组中写入的 1 和 0 的数量。如果 (written ones/written zeros) 的比率低于我们想要达到的目标比率 (ones/zeros)，我们需要将 1 放入序列中。否则我们将零放入序列中。比率发生变化，我们下次再做决定。这个想法是在阵列的每个切片中追求理想的 1/0 比率。