Algorithm challenge: the Partition Problem

dimitarvp

Hey community,

Lately I needed to calculate the total of the sizes of all my external HDDs, SSDs and USB flash sticks lying around so I can make a mirrored RAID setup for my NAS. Say I had disks that are 1TB, 2TB, 3TB and 4TB, then I’d have usable storage of 5TB, mirrored in two groups of disks: (a) 1TB+4TB and (b) 2TB+3TB.

This led me to rediscover the Partition problem and I went ahead and made a small project here:

https://github.com/dimitarvp/partition-problem-elixir

This project is an invitation for everyone who wants to try implementing the algorithm through PRs.

I already included automatic unit and property test harness. All you have to do is add one function adhering to a spec (described in the project’s README) to a module and then just run mix test (shout out to @LostKobrakai for helping me with the code that generates the tests) . If your algorithm fails you’ll see the broken tests prefixed with impl_<YOUR_NAME> which could help iterating on it.

I also plan to add benchmarking code if anyone contributes an alternative algorithm. Mine was about 15 years old Java class that I adapted to Elixir (and discovered an almost complete clone of it online in the meantime).

PRs for other hardcoded values for the unit tests, or additional property tests, are welcome as well.

Would love to see your ideas, folks!

8 comments

#algorithm

6 1826 8

2022-02-07 15:35:39 UTC

First Post!

Show Best Posts
Show All (oldest first)
Show All (newest first)

dimitarvp

Encouraged by the success of this thread – Can you improve this? Zipping two lists, the result must be same size as the first list – I figured I’ll bump this one in case people are interested.

Post #1

Most Liked

lud

This problem has a well known solution, you just keep track of each partition size and add the biggest remaining part to the smallest size. The basic implementation with recursive functions will already be optimized.

You can add streams and stuff but it will only be slower.

I propose to change the tests with a more generic specification, that is asking for a number of partitions instead of always having two partitions.

I tested with the code below for two partitions, but this is failing the tests as the tests expects the specific results of your implementation. I would pass if the tests only asserted the expected sums but not lists items.

  def impl_lud(list) when is_list(list) do
    # solve the problem
    result = impl_lud(list, 2)

    # comply with the shape expected from the test
    [{left_list, left_sum}, {right_list, right_sum}] = Enum.sort_by(result, &(-1 * elem(&1, 1)))
    {left_list, right_list, left_sum, right_sum}
  end

  defp impl_lud(list, parts) do
    partitions = List.duplicate({[], 0}, parts)

    list
    |> Enum.sort(:desc)
    |> Enum.reduce(partitions, &impl_lud_reducer/2)
  end

  defp impl_lud_reducer(x, [{partition, size} | partitions]) do
    impl_lud_insert({[x | partition], size + x}, partitions)
  end

  defp impl_lud_insert({_, size} = p, [{_, smaller} = candidate | rest]) when smaller < size do
    [candidate | impl_lud_insert(p, rest)]
  end

  defp impl_lud_insert(p, rest) do
    [p | rest]
  end

With those errors:


  1) test impl_lud: [1, 3, 4, 5, 7, 8, 9, 11, 65, 74, 83, 100] (PPTest)
     test/pp_test.exs:35
     Assertion with == failed
     code:  assert {[4, 7, 9, 65, 100], [1, 3, 5, 8, 11, 74, 83], 185, 185} ==
              PP.impl_lud([1, 3, 4, 5, 7, 8, 9, 11, 65, 74, 83, 100])
     left:  {[4, 7, 9, 65, 100], [1, 3, 5, 8, 11, 74, 83], 185, 185}
     right: {[1, 3, 7, 9, 65, 100], [4, 5, 8, 11, 74, 83], 185, 185}
     stacktrace:
       test/pp_test.exs:36: (test)

.....

  2) test impl_lud: [2, 3, 10, 5, 8, 9, 7, 3, 5, 2] (PPTest)
     test/pp_test.exs:35
     Assertion with == failed
     code:  assert {[2, 3, 5, 7, 10], [2, 3, 5, 8, 9], 27, 27} == PP.impl_lud([2, 3, 10, 5, 8, 9, 7, 3, 5, 2])
     left:  {[2, 3, 5, 7, 10], [2, 3, 5, 8, 9], 27, 27}
     right: {[2, 3, 5, 8, 9], [2, 3, 5, 7, 10], 27, 27}
     stacktrace:
       test/pp_test.exs:36: (test)

..

  3) test impl_lud: [3, 1, 1, 2, 2, 1] (PPTest)
     test/pp_test.exs:35
     Assertion with == failed
     code:  assert {[1, 1, 3], [1, 2, 2], 5, 5} == PP.impl_lud([3, 1, 1, 2, 2, 1])
     left:  {[1, 1, 3], [1, 2, 2], 5, 5}
     right: {[1, 2, 2], [1, 1, 3], 5, 5}
     stacktrace:
       test/pp_test.exs:36: (test)

Post #2

lud

It depends on how much you want balanced partitions.

If you only expect partitions to be as evenly sized as possible, then no yes it’s wrong. But if you add in the requirements that the average item size in each partition should also be balanced then ~~yes~~ no it’s not wrong, it could be interesting to expect some sizes.

For instance {[2,2], [1,1,1,1]} are “sum-balanced”, but if we consider the average then the right answer should be {[2,1,1], [2,1,1]}. And even there, the test should take the list items, and sort them before comparison with the expected answer. Because some algorithms may return {[2,1,1], [1,2,1]} which is still valid.

Post #4

lud

I edited my answer because I inverted yes/no

I remembmer a hiring test from Dropbox, it had to be done in C lang IIRC. It was kind of the same problem but it was in two dimensions: given a square of N * N tiles, and a list of boxes of n*m tiles, write an algorithm that packs the most boxes into the big square.

Post #5

Last Post!

Aetherus

I implemented the solution with subset-sum and dynamic programming, though I’m not a dynamic programming expert

I’m using the process dictionary as the memo.

defmodule PP.Impls.Aetherus do
  @spec solve([pos_integer()]) ::
    {
      {partition1_sum :: non_neg_integer(), partition2_sum :: non_neg_integer()},
      {partition1_length :: non_neg_integer(), partition2_length :: non_neg_integer()},
      {partition1 :: [pos_integer()], partition2 :: [pos_integer()]}
    }
  def solve(nums) do
    sum = Enum.sum(nums)
    len = length(nums)
    sum_target = div(sum, 2)
    len_target = div(len, 2)

    {sum_diff, len_diff, partition1} =
      Task.async(fn ->
        closest_subset_sum(Enum.with_index(nums), sum_target, len_target)
      end)
      |> Task.await(:infinity)

    partition2 = nums |> List.myers_difference(partition1) |> Keyword.get_values(:del) |> List.flatten()

    {
      {sum_target + sum_diff, sum - sum_target - sum_diff},
      {len_target + len_diff, len - len_target - len_diff},
      {partition1, partition2}
    }
  end

  @spec closest_subset_sum([pos_integer()], non_neg_integer(), non_neg_integer()) ::
          {integer(), integer(), [pos_integer()]}
  defp closest_subset_sum([], sum_target, length_target) do
    {-sum_target, -length_target, []}
  end

  defp closest_subset_sum([{h, i} | t], sum_target, length_target) do
    key = {i, sum_target, length_target}

    case Process.get(key) do
      solution when solution != nil ->
        solution

      nil ->
        {sum_diff1, len_diff1, solution1} =
          closest_subset_sum(t, sum_target - h, length_target - 1)

        {sum_diff2, len_diff2, solution2} = closest_subset_sum(t, sum_target, length_target)

        cond do
          abs(sum_diff1) < abs(sum_diff2) ->
            {sum_diff1, len_diff1, [h | solution1]}

          abs(sum_diff1) > abs(sum_diff2) ->
            {sum_diff2, len_diff2, solution2}

          abs(len_diff1) <= abs(len_diff2) ->
            {sum_diff1, len_diff1, [h | solution1]}

          true ->
            {sum_diff2, len_diff2, solution2}
        end
        |> tap(fn solution -> Process.put(key, solution) end)
    end
  end
end

Tests failed:

  1) test impl_aetherus: [3, 1, 1, 2, 2, 1] (PPTest)
     test/pp_test.exs:35
     Assertion with == failed
     code:  assert {[1, 1, 3], [1, 2, 2], 5, 5} == PP.impl_aetherus([3, 1, 1, 2, 2, 1])
     left:  {[1, 1, 3], [1, 2, 2], 5, 5}
     right: {[3, 1, 1], [2, 2, 1], 5, 5}
     stacktrace:
       test/pp_test.exs:36: (test)



  2) test impl_aetherus: [2, 3, 10, 5, 8, 9, 7, 3, 5, 2] (PPTest)
     test/pp_test.exs:35
     Assertion with == failed
     code:  assert {[2, 3, 5, 7, 10], [2, 3, 5, 8, 9], 27, 27} == PP.impl_aetherus([2, 3, 10, 5, 8, 9, 7, 3, 5, 2])
     left:  {[2, 3, 5, 7, 10], [2, 3, 5, 8, 9], 27, 27}
     right: {[2, 3, 10, 5, 7], [8, 9, 3, 5, 2], 27, 27}
     stacktrace:
       test/pp_test.exs:36: (test)



  3) test impl_aetherus: [1, 3, 4, 5, 7, 8, 9, 11, 65, 74, 83, 100] (PPTest)
     test/pp_test.exs:35
     Assertion with == failed
     code:  assert {[4, 7, 9, 65, 100], [1, 3, 5, 8, 11, 74, 83], 185, 185} ==
              PP.impl_aetherus([1, 3, 4, 5, 7, 8, 9, 11, 65, 74, 83, 100])
     left:  {[4, 7, 9, 65, 100], [1, 3, 5, 8, 11, 74, 83], 185, 185}
     right: {[1, 3, 5, 11, 65, 100], [4, 7, 8, 9, 74, 83], 185, 185}
     stacktrace:
       test/pp_test.exs:36: (test)



  4) test impl_aetherus: [6000, 3000, 480, 240, 120] (PPTest)
     test/pp_test.exs:35
     Assertion with == failed
     code:  assert {[6000], [120, 240, 480, 3000], 6000, 3840} == PP.impl_aetherus([6000, 3000, 480, 240, 120])
     left:  {[6000], [120, 240, 480, 3000], 6000, 3840}
     right: {[6000], [3000, 480, 240, 120], 6000, 3840}
     stacktrace:
       test/pp_test.exs:36: (test)

.

  5) test impl_aetherus: [1, 1, 1, 1, 1, 1, 1, 50, 50, 100] (PPTest)
     test/pp_test.exs:35
     Assertion with == failed
     code:  assert {[1, 1, 1, 1, 100], [1, 1, 1, 50, 50], 104, 103} ==
              PP.impl_aetherus([1, 1, 1, 1, 1, 1, 1, 50, 50, 100])
     left:  {[1, 1, 1, 1, 100], [1, 1, 1, 50, 50], 104, 103}
     right: {[1, 1, 1, 50, 50], [1, 1, 1, 1, 100], 103, 104}
     stacktrace:
       test/pp_test.exs:36: (test)

..

  6) test impl_aetherus: [1, 2, 3, 4, 5] (PPTest)
     test/pp_test.exs:35
     Assertion with == failed
     code:  assert {[1, 2, 5], [3, 4], 8, 7} == PP.impl_aetherus([1, 2, 3, 4, 5])
     left:  {[1, 2, 5], [3, 4], 8, 7}
     right: {[2, 5], [1, 3, 4], 7, 8}
     stacktrace:
       test/pp_test.exs:36: (test)

....

Finished in 0.04 seconds (0.00s async, 0.04s sync)
14 tests, 6 failures

Post #8

Where Next?

View thread on forum (has 8 replies!)

algorithm

Home Chat & Discussions>Discussions

14 1768 8

Last post

REPLY VIEW THREAD WITH 8 POSTS

Algorithm challenge: the Partition Problem

dimitarvp

First Post! Show Best PostsShow All (oldest first)Show All (newest first)

dimitarvp

Most Liked

lud

lud

lud

Last Post!

Aetherus

Where Next?

Trending in Discussions

What Elixir related stuff are you doing?

Phoenix Storybook: a storybook-like UI interface for Phoenix components

My thoughts on Ash

Cure - a new language compiled to BEAM

Ergo - a framework for creating microservices using technologies and design patterns of Erlang/OTP in Golang

Companies that hire candidates without prior Elixir experience

Building an AI agent runtime moving from TypeScript to Elixir/OTP - can you help/compare notes?

Other Trending Topics

Gust - A task orchestration system built in Elixir

Beam Bots - Resilient Robotics on the BEAM

Xamal - Deploy Elixir releases to bare metal servers via SSH

Emerge & Solve - a GUI framework for Elixir

Corex - Accessible and unstyled UI Phoenix components

Aludel - LLM prompt evaluation workbench

Chat & Discussions>Discussions

Latest on Elixir Forum

Sponsor Spotlight

Our Sponsors

Categories:

Sub Categories:

Forums

Popular Tags

Our Sponsors

We're in Beta

Options

Thread Display Mode

Thread Preview

First Post!

Show Best Posts
Show All (oldest first)
Show All (newest first)