Number distribution

Question

Problem: We have x checkboxes and we want to check y of them evenly.

Example 1: select 50 checkboxes of 100 total.

[-]
[x]
[-]
[x]
...

Example 2: select 33 checkboxes of 100 total.

[-]
[-]
[x]
[-]
[-]
[x]
...

Example 3: select 66 checkboxes of 100 total:

[-]
[x]
[x]
[-]
[x]
[x]
...

But we're having trouble to come up with a formula to check them in code, especially once you go 11/111 or something similar. Anyone has an idea?

Answer 1

Let's first assume y is divisible by x. Then we denote p = y/x and the solution is simple. Go through the list, every p elements, mark 1 of them.

Now, let's say r = y%x is non zero. Still p = y/x where / is integer devision. So, you need to:

• In the first p-r elements, mark 1 elements
• In the last r elements, mark 2 elements

Note: This depends on how you define evenly distributed. You might want to spread the r sections withx+1 elements in between p-r sections with x elements, which indeed is again the same problem and could be solved recursively.

Alright so it wasn't actually correct. I think this would do though:

Regardless of divisibility:

• if y > 2*x, then mark 1 element every p = y/x elements, x times.
• if y < 2*x, then mark all, and do the previous step unmarking y-x out of y checkboxes (so like in the previous case, but x is replaced by y-x)

Note: This depends on how you define evenly distributed. You might want to change between p and p+1 elements for example to distribute them better.

Answer 2

Here's a straightforward solution using integer arithmetic:

void check(char boxes[], int total_count, int check_count)
{
    int i;

    for (i = 0; i < total_count; i++)
        boxes[i] = '-';

    for (i = 0; i < check_count; i++)
        boxes[i * total_count / check_count] = 'x';
}

total_count is the total number of boxes, and check_count is the number of boxes to check.

First, it sets every box to unchecked. Then, it checks check_count boxes, scaling the counter to the number of boxes.

Caveat: this is left-biased rather than right-biased like in your examples. That is, it prints x--x-- rather than --x--x. You can turn it around by replacing

        boxes[i * total_count / check_count] = 'x';

with:

        boxes[total_count - (i * total_count / check_count) - 1] = 'x';

Correctness

Assuming 0 <= check_count <= total_count, and that boxes has space for at least total_count items, we can prove that:

• No check marks will overlap. i * total_count / check_count increments by at least one on every iteration, because total_count >= check_count.

• This will not overflow the buffer. The subscript i * total_count / check_count

  • Will be >= 0. i, total_count, and check_count will all be >= 0.

  • Will be < total_count. When n > 0 and d > 0:

    (n * d - 1) / d < n
    

    In other words, if we take n * d / d, and nudge the numerator down, the quotient will go down, too.

    Therefore, (check_count - 1) * total_count / check_count will be less than total_count, with the assumptions made above. A division by zero won't happen because if check_count is 0, the loop in question will have zero iterations.

Answer 3

Say number of checkboxes is C and the number of Xes is N.

You example states that having C=111 and N=11 is your most troublesome case.

Try this: divide C/N. Call it D. Have index in the array as double number I. Have another variable as counter, M.

double D = (double)C / (double)N;
double I = 0.0;
int M = N;
while (M > 0) {
    if (checkboxes[Round(I)].Checked) { //  if we selected it, skip to next
        I += 1.0;
        continue;
    }
    checkboxes[Round(I)].Checked = true;
    M --;
    I += D;
    if (Round(I) >= C) { //  wrap around the end
        I -= C;
    }
}

Please note that Round(x) should return nearest integer value for x.

This one could work for you.

Answer 4

I think the key is to keep count of how many boxes you expect to have per check.

Say you want 33 checks in 100 boxes. 100 / 33 = 3.030303..., so you expect to have one check every 3.030303... boxes. That means every 3.030303... boxes, you need to add a check. 66 checks in 100 boxes would mean one check every 1.51515... boxes, 11 checks in 111 boxes would mean one check every 10.090909... boxes, and so on.

double count = 0;
for (int i = 0; i < boxes; i++) {
    count += 1;
    if (count >= boxes/checks) {
        checkboxes[i] = true;
        count -= count.truncate(); // so 1.6 becomes 0.6 - resetting the count but keeping the decimal part to keep track of "partial boxes" so far
    }
}

You might rather use decimal as opposed to double for count, or there's a slight chance the last box will get skipped due to rounding errors.

Answer 5

Bresenham-like algorithm is suitable to distribute checkboxes evenly. Output of 'x' corresponds to Y-coordinate change. It is possible to choose initial err as random value in range [0..places) to avoid biasing.

def Distribute(places, stars):
err = places // 2
res = ''
for i in range(0, places):
    err = err - stars
    if err < 0 :
        res = res + 'x'
        err = err + places
    else:
        res = res + '-'
print(res)

Distribute(24,17)
Distribute(24,12)
Distribute(24,5)

output:

x-xxx-xx-xx-xxx-xx-xxx-x

-x-x-x-x-x-x-x-x-x-x-x-x

--x----x----x---x----x--

Answer 6

Quick html/javascript solution:

<html>
<body>
<div id='container'></div>
<script>
var cbCount = 111;
var cbCheckCount = 11;
var cbRatio = cbCount / cbCheckCount;
var buildCheckCount = 0;

var c = document.getElementById('container');

for (var i=1; i <= cbCount; i++) {
  // make a checkbox
  var cb = document.createElement('input');
  cb.type = 'checkbox';

  test = i / cbRatio - buildCheckCount;
  if (test >= 1) {
    // check the checkbox we just made
    cb.checked = 'checked';
    buildCheckCount++;
  }

  c.appendChild(cb);
  c.appendChild(document.createElement('br'));
}
</script>
</body></html>

Answer 7

Adapt code from one question's answer or another answer from earlier this month. Set N = x = number of checkboxes and M = y = number to be checked and apply formula (N*i+N)/M - (N*i)/M for section sizes. (Also see Joey Adams' answer.)

In python, the adapted code is:

  N=100; M=33; p=0;
  for i in range(M):
     k = (N+N*i)/M
     for j in range(p,k-1): print "-",
     print "x",
     p=k

which produces
- - x - - x - - x - - x - - [...] x - - x - - - x
where [...] represents 25 --x repetitions. With M=66 the code gives
x - x x - x x - x x - x x - [...] x x - x x - x - x
where [...] represents mostly xx- repetitions, with one x- in the middle.

Note, in C or java:
Substitute for (i=0; i<M; ++i) in place of for i in range(M):.
Substitute for (j=p; j<k-1; ++j) in place of for j in range(p,k-1):.

Correctness: Note that M = x boxes get checked because print "x", is executed M times.

Answer 8

What about using Fisher–Yates shuffle ?

Make array, shuffle and pick first n elements. You do not need to shuffle all of them, just first n of array. Shuffling can be find in most language libraries.