logo标签列表

平均分配数值到数组中

c++arraysalgorithmdistribution
3
我有一个大小为8的固定大小布尔数组。数组中所有元素的默认值都是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]

我正在寻找一种简单的方法，可以将真值平均分配到数组中，而不需要编写特殊情况的代码。
1
对于只有两个值的情况，它们之间的距离是不是只有 [1, 0, 0, 0, 0, 0, 0, 1]？哦，你是在假设数组会自动环绕计算距离吗？ - KamilCuk
好像数组是环绕的。我应该指定...这样它们在位置之间会有3个0，例如[1, 0, 0, 0, 1, 0, 0,0 ]或[0, 1, 0, 0, 0, 1, 0, 0]或[0, 0, 1, 0, 0, 0, 1, 0]，对于2个真值。 - Shawn Pacarar
如果您想要精确地分割空格，请参考https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm。 - Neil
4个回答
3

看看这个：

#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,}

@编辑 - 更好的均匀排列模式。

说明：

假设我们有一个包含 8 个整数的数组，我们想在其中有 5 个为1。在具有8个元素和5个1的序列中，理想比率 (1/0) 应该是 (5/3)。我们永远无法接近这种比率，但我们可以尝试。

想法是循环遍历数组并记住我们已经写入数组中的1和0的数量。如果 (已写入1的数量 / 已写入0的数量) 比我们想要达到的目标比率 (1/0) 低，则需要将1放入序列中。否则，我们将在序列中放入0。比率发生变化，并且我们下一次作出决策。目标是追求每个数组片段中的1与0的理想比率。

与我的方法相同的数学基础，但实现更简单 - 我很喜欢它... - Aconcagua
你的解决方案对我有效，但似乎我需要偏移起始位置。我会接受这个答案并继续尝试，但我想要偏移分布，以便在不同配置中拥有相同数量的真值。 - Shawn Pacarar
1
@ShawnPacarar 如果你想从任意位置开始，只需要进行轻微修改：arr[i + startIndex % arr.size()] = ... - Aconcagua
非常完美，我犯了一个错误，在创建它们时将它们打印出来，导致它们看起来是按相同顺序排列的，而实际上它们已经偏移了。解决方案和评论正是我正在寻找的，非常感谢！ - Shawn Pacarar
1
一个简单的方法是将理想的小数位置四舍五入。
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
}
1
这是布雷森汉姆直线绘制算法的一个应用。我使用它并不是因为它在旧硬件上速度快，而是它可以精确地放置真实值。
#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.
        // https://dev59.com/K2sz5IYBdhLWcg3w8Mgb
        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
0

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

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

更困难的是不能整除数组的数字：

  • 3需要距离为2.66。
  • 5需要距离为1.6
  • 7需要距离为0.875

如果您有一个距离为X.Y，则必须将一些元素放置在距离为X的位置，将另一些元素放置在距离为X + 1的位置。 X很简单，它将是整数除法的结果：8 / numberOfElements。余数将确定您将不得不多少次切换到X + 1：8％numberOfElements。对于3，这也将导致2，因此您将有1个距离为2和2个距离为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，因此：7x距离为1，1x距离为2

[ 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的结果。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接