将值均匀分布到数组中

Question

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

我想将真值分布得尽可能远。我也希望能够随机化配置。在这种情况下，数组环绕，因此位置 7 是数组中的 "next to" 位置 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 比率。

Answer 2

您需要动态计算距离。一个元素是明确的，可以驻留在任意位置

2个元素也清楚了，距离需要4个。
4个元素需要2的距离
8 个元素距离为 1

更难的是不划分数组的数字：

3 需要 2.66 的距离。
5需要1.6的距离
7需要0.875的距离

Errm...一般来说，如果你有 X.Y 的距离，你将不得不将一些元素放置在 [=31= 的距离处]X 和一些距离 X + 1。 X很简单，就是整除的结果：8 / numberOfElements。余数将决定您必须切换到 X + 1: 8 % numberOfElements 的频率。对于 3，这也将导致 2，因此您将有 1x 距离 2 和 2x 距离 3:

[ 1 0 1 0 0 1 0 0 ]
    2    3     3 (distance to very first 1)

对于 5，您将得到：8/5 = 1、8%5 = 3，因此：1 的 2 倍距离、2 的 3 倍距离

[ 1 1 1 0 1 0 1 0 ]
   1 1  2   2   2

对于 7 你会得到：8/7 = 1，8%7 = 1，所以：1 的 7 倍距离，2 的 1 倍距离

[ 1 1 1 1 1 1 1 0 ]
   1 1 1 1 1 1  2

这适用于任意长度的数组 L:

L/n   = minimum distance
L%n   = number of times to apply minimum distance
L-L%n = number of times to apply minimum distance + 1

数学指标不会揭示首先应用所有较小距离然后应用所有较大距离之间的任何差异，但人类的审美感觉可能更喜欢尽可能频繁地在较大和较小之间交替 – 或者您应用算法递归地（对于更大的数组长度），得到类似 2x2、3x3、2x2、3x3 而不是 4x2 和 6x3 的东西。

Answer 3

一个简单的方法是将理想的小数位置四舍五入。

truths = randBetween(1, 8)
values = [0,0,0,0,0,0,0,0]
offset = randBetween(0, 8 * truths - 1)
for(i = 0; i < truths; i++) {
    pos = (offset + (i * 8)) / truths
    values[pos % 8] = 1
}

Answer 4

这是Bresenham's line-drawing algorithm的一个应用。我使用它不是因为它在旧硬件上速度很快，而是它准确地放置了真实值。

#include <iostream>
#include <stdexcept>
#include <string>
#include <random>

int main(int argc, char **argv) {
    try {
        // Read the argument.
        if(argc != 2) throw std::invalid_argument("one argument");
        int dy = std::stoi(argv[1]);
        if(dy < 0 || dy > 8) throw std::out_of_range("[0..8]");
        int values[8] = {0};

        // https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
        int dx = 8;
        int delta = 2 * dy - dx; // Balance the line. Permute it up later.
        for(int x = 0; x < dx; x++) {
            if(delta > 0) {
                values[x] = 1;
                delta -= 2 * dx;
            }
            delta += 2 * dy;
        }
        for(int x = 0; x < dx; x++)
            std::cout << (x ? ", " : "") << values[x];
        std::cout << std::endl;

        // Rotate the number by a random amount.
        // I'm sure there is an easier way to do this.
        // 
        std::random_device rd; // obtain a random number from hardware
        std::mt19937 eng(rd()); // seed the generator
        std::uniform_int_distribution<> distr(0, dx - 1);
        int rotate = distr(eng);
        bool first = true;
        int x = rotate;
        do {
            std::cout << (first ? "" : ", ") << values[x];
            first = false;
            x = (x + 1) % dx;
        } while(x != rotate);
        std::cout << std::endl;

    } catch(const std::exception &e) {
        std::cerr << "Something went wrong: " << e.what() << std::endl;
        return 1;
    }
    return 0;
}

获得精确解后，随机旋转它。

0, 1, 0, 0, 1, 0, 1, 0
1, 0, 0, 1, 0, 0, 1, 0

将值均匀分布到数组中

Evenly distribute values into array

c++

arrays

algorithm

distribution