Dividing Elements of a Ruby Array into an Exact Number of (Nearly) Equal-Sized Sub-Arrays

Dividing elements of a ruby array into an exact number of (nearly) equal-sized sub-arrays

You're looking for Enumerable#each_slice

a = [0, 1, 2, 3, 4, 5, 6, 7]
a.each_slice(3) # => #<Enumerator: [0, 1, 2, 3, 4, 5, 6, 7]:each_slice(3)>
a.each_slice(3).to_a # => [[0, 1, 2], [3, 4, 5], [6, 7]]

How to split (chunk) a Ruby array into parts of X elements?

Take a look at Enumerable#each_slice:

foo.each_slice(3).to_a
#=> [["1", "2", "3"], ["4", "5", "6"], ["7", "8", "9"], ["10"]]

How to split an array into n equal or close to equal arrays?

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

a.group_by.with_index{|_, i| i % 2}.values
# => [[1, 3, 5, 7, 9], [2, 4, 6, 8, 10]]

a.group_by.with_index{|_, i| i % 3}.values
# => [[1, 4, 7, 10], [2, 5, 8], [3, 6, 9]]

a.group_by.with_index{|_, i| i % 4}.values
# => [[1, 5, 9], [2, 6, 10], [3, 7], [4, 8]]

a.group_by.with_index{|_, i| i % 5}.values
# => [[1, 6], [2, 7], [3, 8], [4, 9], [5, 10]]

a.group_by.with_index{|_, i| i % 6}.values
# => [[1, 7], [2, 8], [3, 9], [4, 10], [5], [6]]

How to chunk an array in Ruby

Use each_slice:

require 'enumerator' # only needed in ruby 1.8.6 and before
userids.each_slice(100) do |a|
  # do something with a
end

Split number into equal parts or what's closest to that

You can use this cool one-liner. It should work dividing by any amount of pieces you want:

def split_into n, p
    [n/p + 1] * (n%p) + [n/p] * (p - n%p)
end

print (split_into 32, 3) # => [11, 11, 10]

It basically divides the number into equal parts and splits the remainder by the first ones (1 for each). That and the fact that you can multiply and add arrays together, like so:

[1] * 3     # => [1, 1, 1]
[1] + [2]   # => [1, 2]

EDIT: Considering the rule that each piece should be smaller than 20, you can calculate the ideal amount of pieces as suggested by @Cary Swoveland:

p = (n / 20.0).ceil

How to get even groups in ruby?

I assume:

• the elements are to be kept in order;
• l-s is to be minimized, where l is the size of the largest group and s is the size of the smallest group; and
• group sizes are non-increasing.

l-s will be at most 1.

def group_em(arr, ngroups)
  n_per_group, left_over = arr.size.divmod(ngroups)
  cum_off = 0
  ngroups.times.map do |i|
    n = n_per_group + (i < left_over ? 1 : 0)
    a = arr[cum_off, n]
    cum_off += n
    a     
  end
end

arr = [1, 2, 3, 4, 5, 6, 7]
(1..7).each { |m| puts "ngroups=#{m}: #{group_em(arr, m)}" }
ngroups=1: [[1, 2, 3, 4, 5, 6, 7]]
ngroups=2: [[1, 2, 3, 4], [5, 6, 7]]
ngroups=3: [[1, 2, 3], [4, 5], [6, 7]]
ngroups=4: [[1, 2], [3, 4], [5, 6], [7]]
ngroups=5: [[1, 2], [3, 4], [5], [6], [7]]
ngroups=6: [[1, 2], [3], [4], [5], [6], [7]]
ngroups=7: [[1], [2], [3], [4], [5], [6], [7]]

Multiplying with divide and conquer

I am not familiar with the divide and conquer algorithm but i don't think it contains parts you can't do in Ruby.

Here is a quick attempt:

def multiplb(a,b)
  #Break recursion when a or b has one digit
  if a < 10 || b < 10
    a * b
  else
    #Max number of digits of a and b
    n = [a.to_s.length, b.to_s.length].max

    # Steps to split numbers to high and low digits sub-numbers
    # (1) to_s.split('') => Converting digits to string then arrays to ease splitting numbers digits 
    # (2) each_slice => Splitting both numbers to high(left) and low(right) digits groups
    # (3) to_a , map, join, to_i => Simply returning digits to numbers
    al, ar = a.to_s.split('').each_slice(n/2).to_a.map(&:join).map(&:to_i)
    bl, br = b.to_s.split('').each_slice(n/2).to_a.map(&:join).map(&:to_i) 

    #Recursion
    p1 = multiplb(al, bl)
    p2 = multiplb(al + ar, bl + br)
    p3 = multiplb(ar, br)

    p1 * (10**n) + (p2 - p1 - p3) * (10**(n/2)) + p3
  end

end
#Test
puts multiplb(1980, 2315)
# => 4583700  yeah that's correct :)

Here are some references to further explain part of the code:

1. Finding max of numbers => How do you find a min / max with Ruby?

2. Spliting an array to half => Splitting an array into equal parts in ruby

3. Turning a fixnum into array => Turning long fixed number to array Ruby

Hope it hepls !

Dividing array into chunks of almost equal sum

We can first try to divide an array into 2 parts such that their sum is almost equal.

Then once we have the 2 sets, we can further apply the same process on each of them to get 2*2 = 4 sets of equal sum.

The algorithm to divide an array into 2 parts of approximately equal sum is as follows:

• Initialize 2 empty sets to hold our answer.
• Sort the array in reverse order.
• While maintaining the sum of the 2 sets, iterate over all the elements from array and append them into the set which has the lesser sum.
• Note that this is just an approximate algorithm. If we want to find the exactly optimal answer, then we can model this problem as the subset sum problem, and find if we can divide the array into 2 parts, where one of the set has the sum sum/2 or sum/2 - 1 or sum/2 - 2 ... 0 (trying each of them in that order). This is significantly slower compared to our approximate solution.

def divide_almost_equally_into_2(arr):
    set1 = []
    set2 = []
    sum1 = sum2 = arr_idx = 0
    while arr_idx < len(arr):
        if sum1 < sum2:
            set1.append(arr[arr_idx])
            sum1 += arr[arr_idx]
        else:
            set2.append(arr[arr_idx])
            sum2 += arr[arr_idx]
        arr_idx += 1
    return set1, set2


def divide_almost_equally_into_4(arr):
    arr.sort(reverse=True)
    set1, set2 = divide_almost_equally_into_2(arr)
    set11, set12 = divide_almost_equally_into_2(set1)
    set21, set22 = divide_almost_equally_into_2(set2)
    return [set11, set12, set21, set22]


def main():
    arr = [11,20,2,4,8,13,16,0,1,0,3,6]
    set1, set2, set3, set4 = divide_almost_equally_into_4(arr)
    print(f"{arr}   {sum(arr)}\n")
    print(f"{set1}   {sum(set1)}")
    print(f"{set2}   {sum(set2)}")
    print(f"{set3}   {sum(set3)}")
    print(f"{set4}   {sum(set4)}")


main()

Output:

[20, 16, 13, 11, 8, 6, 4, 3, 2, 1, 0, 0]   84

[13, 8]   21
[16, 3, 2]   21
[11, 6, 4]   21
[20, 1, 0, 0]   21

EDIT:

To generalize the same algorithm to 'n' number of splits, we can use a heap:

• Create a min-heap of size 'n', where each element is a tuple of the form (current_sum_of_set_i, i).
• So, initially heap will contain elements (0, 0), (0, 1) ... (0, n-1).
• Now iterate over the reverse-sorted array, and assign each element to the set present at the top of the heap.
• Update the heap element of the set with the new sum of the element added to it.

import heapq


def divide_almost_equally(arr, num_chunks):
    arr = sorted(arr, reverse=True)
    heap = [(0, idx) for idx in range(num_chunks)]
    heapq.heapify(heap)
    sets = {}
    for i in range(num_chunks):
        sets[i] = []
    arr_idx = 0
    while arr_idx < len(arr):
        set_sum, set_idx = heapq.heappop(heap)
        sets[set_idx].append(arr[arr_idx])
        set_sum += arr[arr_idx]
        heapq.heappush(heap, (set_sum, set_idx))
        arr_idx += 1
    return sets.values()


def main():
    arr = [11,20,2,4,8,13,16,0,1,0,3,6]
    set1, set2, set3, set4 = divide_almost_equally(arr, 4)
    print(f"{sorted(arr, reverse=True)}   {sum(arr)}\n")
    print(f"{set1}   {sum(set1)}")
    print(f"{set2}   {sum(set2)}")
    print(f"{set3}   {sum(set3)}")
    print(f"{set4}   {sum(set4)}")


main()

Output:

[20, 16, 13, 11, 8, 6, 4, 3, 2, 1, 0, 0]   84

[20, 1]   21
[16, 4, 0, 0]   20
[13, 6, 3]   22
[11, 8, 2]   21

How do I convert Int/Decimal to float in C#?

You can just do a cast

int val1 = 1;
float val2 = (float)val1;

or

decimal val3 = 3;
float val4 = (float)val3;

---

Related Topics