Evenly distribute values into array

Question

I have a fixed size boolean array of size 8. The default value of all elements in the array is false. There will be a number of truth values to fill between 1-8.

I want to distribute the truth values as far away from one another as possible. I also wish to be able to randomize the configuration. In this scenario the array wraps around so position 7 is "next to" position 0 in the array.

here are some examples for fill values. I didn't include all possibilities, but hopefully it gets my point across.

1: [1, 0, 0, 0, 0, 0, 0, 0] or [0, 1, 0, 0, 0, 0, 0, 0]

2: [1, 0, 0, 0, 1, 0, 0, 0] or [0, 1, 0, 0, 0, 1, 0, 0]

3: [1, 0, 0, 1, 0, 0, 1, 0] or [0, 1, 0, 0, 1, 0, 0, 1]

4: [1, 0, 1, 0, 1, 0, 1, 0] or [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]

The closest solution I have come up with so far hasn't quite produced the results I'm looking for...

I seek to write it in c++ but here is a little pseudo-code of my algorithm so far... not quite working out how I wanted

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
}

this is an example output from my current code. those marked with a star are incorrect.

[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]

I'm looking for a simple way to distribute the truth values evenly throughout the array without having to code for special cases.

Answer 1

Check this out:

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

Generates:

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 - better evenly spaced pattern.

Explanation:

So let's take an array of 8 ints and we want to have 5 ones. The ideal ratio of (ones / zeros) in a sequence with 8 elements and 5 ones, well would be (5 / 3). We will never approach such ratio, but we can try.

The idea is to loop through the array and remember the number of ones and zeros we have written in the array. If the ratio of (written ones / written zeros) is lower then the destination ratio (ones / zeros) we want to achieve, we need to put a one to the sequence. Otherwise we put zero in the sequence. The ratio changes and we make the decision next time. The idea is to pursue the ideal ratio of ones per zeros in each slice of the array.

Answer 2

A simple way to do this would be to round the ideal fractional positions.

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 3

This is an application of Bresenham's line-drawing algorithm. I use it not because it's fast on old hardware, but it places true values exactly.

#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://stackoverflow.com/questions/7560114/random-number-c-in-some-range
        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;
}

Once you have an exact solution, rotate it by a random amount.

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

Answer 4

You need to calculate distance dynamically. One element is clear, that can reside at arbitrary location

• 2 elements is clear, too, distance needs to be 4.
• 4 elements need a distance of 2
• 8 elements a distance of 1

More difficult are numbers that don't divide the array:

• 3 requires a distance of 2.66.
• 5 requires a distance of 1.6
• 7 requires a distance of 0.875

Errm... In general, if you have a distance of X.Y, you will have to place some of the elements at distances of X and some at distances of X + 1. X is simple, it will be the result of an integer division: 8 / numberOfElements. The remainder will determine how often you will have to switch to X + 1: 8 % numberOfElements. For 3, this will result in 2, too, so you will have 1x distance of 2 and 2x distance of 3:

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

For 5, you'll get: 8/5 = 1, 8%5 = 3, so: 2x distance of 1, 3x distance of 2

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

For 7 you'll get: 8/7 = 1, 8%7 = 1, so: 7x distance of 1, 1x distance of 2

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

That will work for arbitrary array length 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

Mathematical metrics won't reveal any difference between first applying all smaller distances then all larger ones, human sense for aesthetics, though, might prefer if you alternate between larger and smaller as often as possible – or you apply the algorithm recursively (for larger array length), to get something like 2x2, 3x3, 2x2, 3x3 instead of 4x2 and 6x3.