Algorithm for splitting a list into N sublists

lists
algorithm
Tags: #<Tag:0x00007f039bba1a30> #<Tag:0x00007f039bba1850>

#1

On a page there’re 3 columns. And I have a list of objects. Every object should go one of the 3 columns in the subsequent order.

1 -> 1, 2 -> 2, 3 -> 3, 4 -> 1, 5 -> 2 and so on.

I’m trying to come up with an algorithm and have difficult to do so.

What’s the best way to do so? A high-level pointer will be fine.

update:

of put that simply: split a list into N sub-lists. The 1st sub-list might be bigger than the rest.

If I have 7 elements and I want to split them into N = 3 sub-lists, there should be created 3 sublists:

[[3 elements], [2 elements], [2 elements]] 

Namely, I want to preserve all the elements. Enum.chunk_every(…, :discard) won’t work.


#2

You might use Enum.chunk_every/2 on a collection.

iex> 1..10 |> Enum.chunk_every(3) |> IO.inspect(charlists: :as_list)
[[1, 2, 3], [4, 5, 6], [7, 8, 9], [10]]

You could also use remainder like this

iex> for x <- 1..10, do: rem x, 3
[1, 2, 0, 1, 2, 0, 1, 2, 0, 1]

#3
def split(list), do: split(list, [], [], [])

defp split([x1, x2, x3 | rest], l1, l2, l3), 
  do: split(rest, [x1 | l1], [x2 | l2], [x3 | l3])
defp split([], l1, l2, l3), 
  do: {Enum.reverse(l1), Enum.reverse(l2), Enum.reverse(l3)}
defp split([x1, x2], l1, l2, l3), 
  do: {Enum.reverse(l1, [x1]), Enum.reverse(l2, [x2]), Enum.reverse(l3)}
defp split([x1], l1, l2, l3), 
  do: {Enum.reverse(l1, [x1]), Enum.reverse(l2), Enum.reverse(l3)}
iex> Test.split(Enum.to_list(1..10))
{[1, 4, 7, 10], [2, 5, 8], [3, 6, 9]}

If your list has always length divisible by 3, you don’t need the last 2 clauses which account for uneven split.


#4

N sub-lists. N is a variable


#5

That won’t work for me because:

  1. it’ll create one additional sub-list when there’s a reminder: rem(7, 3) = 1

  2. I don’t know the size of each sub-list. N = the amount of sub-lists

If I have 7 elements and I want to split them into N = 3 sub-lists, there should be created 3 sublists:

[[3 elements], [2 elements], [2 elements]] 

Namely, I want to preserve all the elements


#6

Try this, I think its what you’re after but I suspect there is a better optimisation for the end of a non-uniform list.

defmodule Split do
  def chunk([] = l, n) do
    l
  end
  
  def chunk(list, n) when is_list(list) do
    chunk(Enum.split(list, n), n)
  end
  
  def chunk({l, t}, n) when length(t) <  n * 2 do
    [l | [t]]
  end
    
  def chunk({l, t}, n) do
    [l | chunk(t, n)]
  end
end

#7

If you don’t care about the order in which they’re put in the bins, this should work. Definitely suboptimal because of the list length and integer division at each step, though.

def chunker(list, parts), do: do_chunk(list, parts, [])

defp do_chunk(_, 0, chunks), do: chunks

defp do_chunk(to_chunk, parts, chunks) do
  chunk_length = to_chunk |> length() |> div(parts)
  {chunk, rest} = Enum.split(to_chunk, chunk_length)
  do_chunk(rest, parts - 1, [chunk | chunks])
end

iex> chunker([1, 2, 3, 4, 5, 6, 7], 4)
[[6, 7], [4, 5], [2, 3], [1]]
iex> chunker([1, 2, 3, 4, 5, 6, 7, 3)
[[5, 6, 7], [3, 4], [1, 2]]
iex> chunker([1, 2, 3, 4, 5, 6, 7, 10)
['\a', [6], [5], [4], [3], [2], [1], [], [], []]

#8

I‘d do it like this:

columns = 
  list
  |> Enum.with_index()
  |> Enum.map(fn {_, i} -> rem(i, 3) end)

Enum.zip(list, columns)