C++ algorithm for 2 lines with same length

Question

I can't find good way to solve such a problem: we have 5 <= k <= 50 segments with length from 1 to 1000 units. Program has to build two pillars with the same length from these segments. Program has to find a maximum possible length of the pillars.

For example: 5 segments with length: 1 5 2 3 4 correct solution is: 1st pillar 2+5=7 and 2nd pillar 3+4=7.

How would you deal with that?

This is not the right way to ask a question here. But hint: For every digit, get the sum of it with _all the rest, individually_. You will get a matrix. Find max in the whole matrix. check if you have the founded max somewhere else, if not, take the **2nd** max of the whole matrix and recheck for it; till you find a "match" — Khalil Khalaf, Jul 18 '16 at 13:10
Do you sum just two numbers, or more? More would make the problem real hard I think. Typical school exercise :) — Sven Nilsson, Jul 18 '16 at 13:11
Honestly sounds like repeated application of subset sum problem. May be NP-Complete. — AndyG, Jul 18 '16 at 13:16
Yes, you can take more than two segments. In this case: 1 2 3 4 5 6 7 8 9, the correct solution can be: 1st: 4+8+9=21 and 2nd: 3+5+6+7=21 — neutrino, Jul 18 '16 at 13:17
@FirstStep: Doesn't that assume a pillar will only consist of 2 segments? — AndyG, Jul 18 '16 at 13:17
In the case of 1 2 3 4 5 6 7 8 9, you can leave out 1 and reach 22 with 2 3 8 9 and 4 5 6 7. This is easy to find because the numbers are consecutive. — Lorenzo Gatti, Jul 18 '16 at 13:21
@neutrino: Likely this is a class exercise and there is some information you are omitting that would make this problem a bit easier to solve asymptotically. A brute force solution would take O(2^N), and with N = 50, that may take quite some time. Is there anything you left out? — AndyG, Jul 18 '16 at 13:21
Ok, but this is only the example. Numbers are random (from 1 to 1000 units). This is all information I got, sorry. — neutrino, Jul 18 '16 at 13:22
@LorenzoGatti: Sorted numbers that increase by 1 would indeed make the problem easier, but we cannot assume such things unless the OP edits the question to say as much :-) — AndyG, Jul 18 '16 at 13:22
https://en.wikipedia.org/wiki/Partition_problem sounds like what you are wanting to do. The Wikipedia article has a couple of algorithms. Also https://www.quora.com/Dynamic-Programming-DP-Where-can-I-find-a-good-link-to-understand-the-subset-sum-problem has some additional answers on subset sum. — Richard Chambers, Jul 18 '16 at 13:24

score 1 · Answer 1 · edited May 23 '17 at 12:08

Wikipedia has an article on the Partition Problem in Computer Science whose lead sounds like what you are wanting to do.

In computer science, the partition problem (or number partitioning1) is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2. Although the partition problem is NP-complete, there is a pseudo-polynomial time dynamic programming solution, and there are heuristics that solve the problem in many instances, either optimally or approximately. For this reason, it has been called "the easiest NP-hard problem".

There are references to several different algorithms to provide solutions.

See also the following.

Is partitioning an array into halves with equal sums P or NP?

3-PARTITION problem

custom partition problem

C++ Elegant solution to partition problem

xinaiz · Answer 2 · 2016-07-18T15:23:17.697

It's some bizarre code, but does it's job. (Note, no optimizations were applied to this code, might run slow, works best for small sets - x! complexity)

template<template<typename...> class Set = std::vector,
         template<typename...> class Pair = std::pair,
         template<typename...> class Cont,
         typename... Ts>
inline Set<Cont<Pair<typename Cont<Ts...>::value_type, size_t>>> all_subsets(const Cont<Ts...>& cont)
{
    Set<Cont<Pair<typename Cont<Ts...>::value_type, size_t>>> all_subsets;
    Cont<Pair<typename Cont<Ts...>::value_type, size_t>> empty;
    all_subsets.push_back(empty);

    for(auto it1 = cont.begin(); it1 != cont.end(); ++it1)
    {
        Set<Cont<Pair<typename Cont<Ts...>::value_type, size_t>>> temp_subset = all_subsets;
        for(auto& it2 : temp_subset)
            it2.push_back({*it1, std::distance(cont.begin(), it1)});
        for(const auto& it2 : temp_subset)
            all_subsets.push_back(it2);
    }
    return all_subsets;
}

template<template<typename...> class Cont,
         typename... Ts>
inline bool intersects_by_second(const Cont<Ts...>& first,  const Cont<Ts...>& second)
{
    for(auto it1 : first)
        for(auto it2 : second)
            if(it1 == it2)
                return true;
    return false;
}

template<template<typename...> class Cont,
         typename... Ts>
inline Cont<typename Cont<Ts...>::value_type::first_type> make_vector_of_firsts(const Cont<Ts...> cont)
{
    Cont<typename Cont<Ts...>::value_type::first_type> result;
    for(const auto& it : cont)
        result.push_back(it.first);
    return result;
}

template<template<typename...> class Cont,
         typename... Ts>
inline Cont<typename Cont<Ts...>::value_type::second_type> make_vector_of_seconds(const Cont<Ts...> cont)
{
    Cont<typename Cont<Ts...>::value_type::second_type> result;
    for(const auto& it : cont)
        result.push_back(it.second);
    return result;
}

template<template<typename...> class Bag = std::vector,
         template<typename...> class Pair = std::pair,
         template<typename...> class Cont,
         typename... Ts>
inline Bag<Pair<Cont<Ts...>, Cont<Ts...>>> full_sum_partition(const Cont<Ts...>& cont)
{
    auto subsets = all_subsets(cont);

    Bag<Pair<Cont<Ts...>, Cont<Ts...>>> result;

    for(auto it1 : subsets)
        for(auto it2 : subsets)
        {
            auto it1_firsts = make_vector_of_firsts(it1);
            auto it2_firsts = make_vector_of_firsts(it2);
            if(std::accumulate(it1_firsts.begin(), it1_firsts.end(), 0)
               ==
               std::accumulate(it2_firsts.begin(), it2_firsts.end(), 0))
            {
                if(intersects_by_second(it1, it2)
                   ||
                   it1.size() != it2.size())
                    continue;
                result.push_back(Pair<Cont<Ts...>, Cont<Ts...>>
                                 (it1_firsts,
                                  it2_firsts));
            }
        }
    return result;
}



int main()
{
    std::vector<int> vec{1,4,9,16,25,36,49,64};
    auto result = full_sum_partition(vec);

    for(const auto& x : result)
        std::cout << x << " with sum " << std::accumulate(x.first.begin(),
                                                          x.first.end(),
                                                          0) << std::endl;
}

Output:

([], []) with sum 0
([1, 25, 36], [4, 9, 49]) with sum 62
([16, 25, 36], [4, 9, 64]) with sum 77
([4, 9, 49], [1, 25, 36]) with sum 62
([16, 49], [1, 64]) with sum 65
([4, 36, 49], [9, 16, 64]) with sum 89
([1, 16, 36, 49], [4, 9, 25, 64]) with sum 102
([1, 64], [16, 49]) with sum 65
([4, 9, 64], [16, 25, 36]) with sum 77
([9, 16, 64], [4, 36, 49]) with sum 89
([4, 9, 25, 64], [1, 16, 36, 49]) with sum 102
Press <RETURN> to close this window...

Also note that I have overloaded operator << for various containers, this output will work only with my additional files. Here is version for everyone (Just printing part):

for(const auto& x : result)
{
    size_t i=0;
    std::cout << "([";
    for(i=0; i< x.first.size(); ++i)
        std::cout << x.first[i] << "],"[(i<x.first.size()-1)];
    if(i==0)
        std::cout << ']';
    std::cout << ",[";
    for(i=0; i< x.second.size(); ++i)
        std::cout << x.second[i] << "],"[(i<x.first.size()-1)];
    if(i==0)
        std::cout << ']';
    std::cout << ')'
              << " with sum " << std::accumulate(x.first.begin(),
                                                x.first.end(),
                                                0) << std::endl;
}

Factorial complexity? This would be worse than 2^n. With an input of 50, which OP might see, the universe will end before computation completes. — AndyG, Jul 18 '16 at 18:09
@AndyG True, but I don't have required theory knowledge to implement any faster version. I know that everything more complex than x^{2,3,4...} is extremely bad (like this code :) ) — xinaiz, Jul 18 '16 at 18:37
That's fair. For reference, though, a brute force solution that computes all possible combinations, and then iterates until it finds two that are the same and maximal would only be O(2^N) which is less than N!. I didn't actually parse your code, so I don't know if this is what your real complexity is. I suggest you look into Karps 21 NP-Complete problems, and maybe dig a little bit into How to prove a problem is NP-Complete by reduction if you want to learn more. — AndyG, Jul 18 '16 at 18:53

C++ algorithm for 2 lines with same length

2 Answers2