CODEWITHSUNDEEP
algorithm
Marijus
Marijus

Reputation: 4375

How to divide an integer n <= 12 to an array of 12 elements so that I could divide this array to as equal as possbile periods

I'm trying to divide an integer N <= 12, which is a number of work days, to 12 months, so that if I divide 12 months into periods of 1, 2, 3, 4 or 6 months, the number of days in these periods should be as equal as possible.

For example:

If N = 6, the array should look like this :

1 0 1 0 1 0 1 0 1 0 1 0 or 0 1 0 1 0 1 0 1 0 1 0

N = 4

1 0 0 1 0 0 1 0 0 1 0 0

N = 3

1 0 0 1 0 0 1 0 0 0 0 0

N = 2

1 0 0 0 0 0 1 0 0 0 0 0

edit:

what I mean by "as equal as possible" is that when I divide this array into periods, the number of work days in these periods shouldn't differ by more than 1.

Upvotes: 3

Views: 266

Answers (5)

huon
huon

Reputation: 102216

The average length of each interval is 12/N (in mathematical terms, not integer division). To enforce the differ-by-one rule, the only options are ceil(12/N) ("long") and floor(12/N) ("short"). The number of each required is 12 % N and N - (12 % N). i.e. in Python

def allocate_intervals(N):
    short = 12 // N # integer division
    long = short + 1

    # lists of [1,0, ..., 0] lists
    short_intervals = [[1] + [0] * (short - 1)] * (N - (12 % N))
    long_intervals =  [[1] + [0] * (long - 1)] * (12 % N)

    # concatenate to get [1, 0, ..., 1, 0, ...]
    return sum(short_intervals + long_intervals, [])

The above code creates the appropriate number of each interval and then concatenates.

(This method is fully general, one can replace the 12s by any positive integer.)

A slightly different implementation of the above in C/C++ etc.

// array is [0, 0, ..., 0] with 12 elements. It is modified in-place.
void allocate_intervals(int N, int array[12]) {
   // length of each interval
   int len_short = 12 / N, len_long = len_short + 1;

   // number of each interval
   int num_long = 12 % N, num_short = N - num_long;

   int step = 0;
   for (int i = 0; i < num_long; i++) {
      array[step] = 1;
      step += len_long;
   }
   for (int i = 0; i < num_short; i++) {
      array[step] = 1;
      step += len_short;
   }
}

Upvotes: 3

Dunes
Dunes

Reputation: 40778

def alloc(N, length=12):

    result = zeros(length) # preinitialise an array with zeros

    short_gap = length // N # where // is integer division
    long_gap = short_gap + 1

    change_over_index = (N - (length % N)) * (length // N)

    result[0:change_over_index:short_gap] = 1
    result[change_over_index:length:long_gap] = 1
    # above two lines of code is called slicing. arr[x:y:z] = 1 means:
    # set all indexes from x to y by increments of z to be 1... eg.
    # for (int i = x; i < y; i += z) arr[i] = 1;

    return result

Upvotes: 0

Rym
Rym

Reputation: 650

EDIT -- Improved for the general case, assumed you were only asking for 1,2,3,4,6 as in question!

What you want is to modulate N by a given period. (My terminology is likely entirely wrong :D Should probably go read up on my high school physics again!)

Have some Ruby..

def spread_it(n)
  d = 12.0 / n
  (0..11).map do |index|
    (12.0 - (index % d) > 11.0) ? '1' : '0'
  end
end

(1..12).each do |n|
  puts "N=#{n} - #{spread_it n}"
end

Output is:

N=1 - ["1", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0"]
N=2 - ["1", "0", "0", "0", "0", "0", "1", "0", "0", "0", "0", "0"]
N=3 - ["1", "0", "0", "0", "1", "0", "0", "0", "1", "0", "0", "0"]
N=4 - ["1", "0", "0", "1", "0", "0", "1", "0", "0", "1", "0", "0"]
N=5 - ["1", "0", "0", "1", "0", "1", "0", "0", "1", "0", "1", "0"]
N=6 - ["1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0"]
N=7 - ["1", "0", "1", "0", "1", "0", "1", "1", "0", "1", "0", "1"]
N=8 - ["1", "0", "1", "1", "0", "1", "1", "0", "1", "1", "0", "1"]
N=9 - ["1", "0", "1", "1", "1", "0", "1", "1", "1", "0", "1", "1"]
N=10 - ["1", "0", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1"]
N=11 - ["1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"]
N=12 - ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"]

Better now? :)

Upvotes: 3

Ankush
Ankush

Reputation: 2554

The idea is int n = 12 / N gives the period.

Updated code. This will work for all cases from 1 to 12. Cases beyond 6 use symmetry property to avoid continuous 1's

public int[] Splitter(int N, int max) // max = 12 for above problem.
{
    if (max < 1 || N < 1 || N > max)
    {
        throw new ArgumentException();
    }

    if (N != max && N > max / 2)
    {
        return Splitter(max - N, max).Select(s => s == 1 ? 0 : 1).ToArray();
    }

    int[] a = new int[max];
    int n = max / N;
    int count = 0;

    for (int i = 0; i < max; i++)
    {
        if (i % n == 0 && count < N)
        {
            a[i] = 1;
            count++;
        }
        else
        {
            a[i] = 0;
        }
    }

    return a;
}

old code:

int n = 12 / N;
for(int i = 0; i < 12; i++)
{
  if (i % n == 0)
  {
    a[i] = 1;
  }
  else
  {
    a[i] = 0;
  }
}

Upvotes: 0

user586399
user586399

Reputation:

If all what are you having is an array of 12 elements, then you can use brute-force recursive backtracking:

Arr = [ ] // holds best solution
tempArr = [ ] // temproray

function rec( i, n )
     if n == 0
        return
     if i == Arr.length
        checkBest(Arr, tempArr) // copies tempArr to Arr if it is better solution
        return
     tempArr[i] = 1
     rec(i + 1, n - 1)
     tempArr[i] = 0
     rec(i + 1, n)

Usage: rec(0, 1234)

Upvotes: 0

Related Questions