Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Well, when I buy gifts for my two wives, I want them to feel equally important to me, but it's hard to go shopping with fixed budgets. Instead, I buy a bunch of stuff and divide them into two groups with as equal value as possible. Then I buy a bunch of chocolates to fix the rest.

But I don't want do all the hard lifting when my computer can do it. And you don't either. So solve this problem so that the next time you need to divide gifts among your wives, you know it would be easy.

Input

1 array of (N*2) elements where N*2 is specified in the 1st line.
The elements of the array in the following line.

Output

2 array of N elements each such that:
Difference of (Sum of elements of array 1) and (Sum of elements of array 2) is as close as possible to 0.

Example

Input

4
1 2 3 4 

Output

1 4
2 3
diff=0

Disclaimer: I don't have two wives. The story is fictional. But when I feel bad, I imagine having two wives. And suddenly, I am thankful and happy that I don't have two. :D

share|improve this question
2  
As it stands, "2 array of N element each" forces the groups to be also equal in size. Is this intended? For example at the moment for input group 1 1 1 1 1 5 the correct answer would be 1 1 1 | 1 1 5, while 1 1 1 1 1 | 5 would make more sense. –  shiona Mar 8 at 9:36
    
Guess the problem also applies to twins and probably to other children-constellations, too. Christmas today is mostly a 'he got more than me'-event... –  TheConstructor Mar 8 at 9:42
1  
@shiona , yes, the equal size is intended. @ TheConstructor , dividing among children is not as funny as dividing among two wives. :D –  rahulroy9202 Mar 8 at 9:45
    
The tag code-challenge requires an objective winning criterion. Also it is closely related to the subset sum problem which was asked here before. –  Howard Mar 8 at 10:38
    
@Howard there are important differences to subset sum: you need to build two equally size lists (not just equally valued), you need to use all elements, ... –  TheConstructor Mar 8 at 12:18

8 Answers 8

Java

Trying to solve this problem in two phases:

  1. Build two equally sized lists by adding the remaining biggest to the currently smaller list and the next to the other. Repeat.
  2. Identify items from both lists that can be switched to reduce the difference in value

Input like

8
1 2 3 4 5 6 7 8

is already solved after phase 1 as e.g.

2 3 5 8
1 4 6 7
diff=0

and input like

6
1 4 5 6 7 8

will need both phases so that

1 5 8
4 6 7
diff=3

(after phase one) becomes the result of

1 6 8
4 5 7
diff=1

While I can guarantee this attempt will always provide a solution, I can not prove that a optimal solution is found in all cases. With the restriction of equally sized lists it however feels quite realistic that there are no corner cases left behind. Prove me wrong ;-)

Program on ideone.com

import java.util.*;

/**
 * Created to solve http://codegolf.stackexchange.com/q/23461/16293 .
 */
public class EqualSums {

    public static void main(String[] args) {
        final Scanner s = new Scanner(System.in);
        // Read number of elements to divide
        final int count = s.nextInt();
        if (count % 2 == 1) {
            throw new IllegalStateException(count + " can not be divided by 2. Consider adding a 0 value.");
        }
        // Read the elements to divide
        final SortedList valueStack = new SortedList(count);
        for (int i = 0; i < count; i++) {
            valueStack.add(s.nextLong());
        }

        final SortedList targetOne = new SortedList(count / 2);
        final SortedList targetTwo = new SortedList(count / 2);
        // Divide elements into two groups
        addInPairs(targetOne, targetTwo, valueStack);
        // Try to ensure groups have equal value
        retaliate(targetOne, targetTwo);

        // Output result
        System.out.println(targetOne);
        System.out.println(targetTwo);
        System.out.println("diff=" + Math.abs(targetOne.getSum() - targetTwo.getSum()));
    }

    private static void addInPairs(SortedList targetOne, SortedList targetTwo, SortedList valueStack) {
        SortedList smallerTarget = targetOne;
        SortedList biggerTarget = targetTwo;
        while (!valueStack.isEmpty()) {
            // Add biggest remaining value to small target
            smallerTarget.add(valueStack.removeLast());

            // Add second biggest remaining value to big target
            biggerTarget.add(valueStack.removeLast());

            // Flip targets if roles have changed
            if (smallerTarget.getSum() > biggerTarget.getSum()) {
                final SortedList temp = smallerTarget;
                smallerTarget = biggerTarget;
                biggerTarget = temp;
            }
        }

    }

    private static void retaliate(SortedList targetOne, SortedList targetTwo) {
        long difference;
        boolean changed;
        outer:
        do {
            difference = Math.abs(targetOne.getSum() - targetTwo.getSum());
            if (difference == 0) {
                return;
            }
            changed = false;
            // Try to find two values, that reduce the difference by changing them between targets
            for (Long valueOne : targetOne) {
                for (Long valueTwo : targetTwo) {
                    final Long tempOne = targetOne.getSum() + valueTwo - valueOne;
                    final Long tempTwo = targetTwo.getSum() - valueTwo + valueOne;
                    if (Math.abs(tempOne - tempTwo) < difference) {
                        targetOne.remove(valueOne);
                        targetTwo.add(valueOne);
                        targetTwo.remove(valueTwo);
                        targetOne.add(valueTwo);
                        changed = true;
                        continue outer;
                    }
                }
            }
        } while (changed);
    }

    public static class SortedList extends AbstractList<Long> {

        private final ArrayList<Long> list;
        private long sum = 0;

        public SortedList(int count) {
            list = new ArrayList<>(count);
        }

        // the next functions access list-field directly
        @Override
        public Long get(int index) {
            return list.get(index);
        }

        @Override
        public boolean add(final Long t) {
            final int i = Collections.binarySearch(list, t);
            if (i < 0) {
                // No equal element present
                list.add(-i - 1, t);
            } else {
                list.add(afterLastEqual(i, t), t);
            }
            sum += t;
            return true;
        }

        @Override
        public Long remove(int index) {
            final Long old = list.remove(index);
            sum -= old;
            return old;
        }

        @Override
        public int size() {
            return list.size();
        }

        // the next functions access list-field only through the functions above this point
        // to ensure the sum is well kept

        public long getSum() {
            return sum;
        }

        private int afterLastEqual(final int start, Object o) {
            int found = start;
            while (found < size() && o.equals(get(found))) {
                found++;
            }
            return found;
        }

        private int beforeFirstEqual(final int start, final Object o) {
            int found = start;
            while (found >= 0 && o.equals(get(found))) {
                found--;
            }
            return found;
        }

        @Override
        public int indexOf(Object o) {
            try {
                final int i = Collections.binarySearch(this, (Long) o);
                if (i >= 0) {
                    return beforeFirstEqual(i, o) + 1;
                }
            } catch (ClassCastException e) {
                // Object was not instance of Long
            }
            return -1;
        }

        @Override
        public int lastIndexOf(Object o) {
            try {
                final int i = Collections.binarySearch(this, (Long) o);
                if (i >= 0) {
                    return afterLastEqual(i, o) - 1;
                }
            } catch (ClassCastException e) {
                // Object was not instance of Long
            }
            return -1;
        }

        @Override
        public boolean remove(Object o) {
            if (o == null) {
                return false;
            }
            final int i = indexOf(o);
            if (i >= 0) {
                remove(i);
                return true;
            }
            return false;
        }

        public Long removeLast() {
            return remove(size() - 1);
        }

        public Long removeFirst() {
            return remove(0);
        }

        @Override
        public String toString() {
            Iterator<Long> it = iterator();
            if (!it.hasNext()) {
                return "";
            }

            StringBuilder sb = new StringBuilder();
            for (; ; ) {
                Long e = it.next();
                sb.append(e);
                if (!it.hasNext()) {
                    return sb.toString();
                }
                sb.append(' ');
            }
        }
    }
}
share|improve this answer

Mathematica

Input forms

The input string is to be taken through STDIN. assets refers to the amounts to be distributed among the wives (or twins). length is the number of assets.

assets=ToExpression[Rest[s=StringSplit[input]]]
length=ToExpression[First[s]]

For the present purposes we will assume that the assets consist of the integers from 1 through 20.

assets=Range[20];
length=Length[Range[20]]

Processing

(* find all possible distributions to one wife; the other presumably gets the remaining assets *)
r=Subsets[assets,{length/2}];

(*order them according to the difference with respect to the total of half of the assets. 
Remove the first set of assets.  One wife will get these.*)
s=SortBy[r/.{{a__Integer}:> {{a},Abs[Tr[Range[20]/2]-Tr[{a}]]}},Last][[1]];

(*The other wife's assets will be the complement.  The difference is carried over from the sorting routine. *)
Grid[{{Grid[{s[[1]],Complement[assets,s[[1]]]}]},{"difference = "<>ToString[s[[2]]]}}]

r20


Is the distribution unfair? So, choose another.

@The Constructor notes that wife 2 may contest the fact that wife 1 got all the best assets. So the following produces all of the "fair" (difference = lowest difference) shares for wife 1; wife 2 gets the remaining assets; the zero refers to the difference in assets for the wives. There are 5448 ways to distribute assets weighted 1 through 20. Only a few lines are displayed.

The format is

s=SortBy[r/.{{a__Integer}:> {{a},Abs[Tr[Range[20]/2]-Tr[{a}]]}},Last];
z=Cases[s,{_List,x_}/;x==s[[1,2]]];
Short[z,10]
Length[z]

{{{1,2,3,4,5,16,17,18,19,20},0},{{1,2,3,4,6,15,17,18,19,20},0},{{1,2,3,4,7,14,17,18,19,20},0},{{1,2,3,4,7,15,16,18,19,20},0},{{1,2,3,4,8,13,17,18,19,20},0},{{1,2,3,4,8,14,16,18,19,20},0},{{1,2,3,4,8,15,16,17,19,20},0},{{1,2,3,4,9,12,17,18,19,20},0},{{1,2,3,4,9,13,16,18,19,20},0},{{1,2,3,4,9,14,15,18,19,20},0},{{1,2,3,4,9,14,16,17,19,20},0},{{1,2,3,4,9,15,16,17,18,20},0},{{1,2,3,4,10,11,17,18,19,20},0},{{1,2,3,4,10,12,16,18,19,20},0}, <<5420>>, {{5,6,7,8,9,11,13,14,15,17},0},{{5,6,7,8,9,12,13,14,15,16},0},{{5,6,7,8,10,11,12,13,14,19},0},{{5,6,7,8,10,11,12,13,15,18},0},{{5,6,7,8,10,11,12,13,16,17},0},{{5,6,7,8,10,11,12,14,15,17},0},{{5,6,7,8,10,11,13,14,15,16},0},{{5,6,7,9,10,11,12,13,14,18},0},{{5,6,7,9,10,11,12,13,15,17},0},{{5,6,7,9,10,11,12,14,15,16},0},{{5,6,8,9,10,11,12,13,14,17},0},{{5,6,8,9,10,11,12,13,15,16},0},{{5,7,8,9,10,11,12,13,14,16},0},{{6,7,8,9,10,11,12,13,14,15},0}}

5448


The prior submission can be found among the edits. It is far more inefficient, relying as it does on Permutations.

share|improve this answer
    
Mathematica seems beautiful for such a task. One last thing is that real wives probably would argue as the 5 most valuable items are all on one stack. (Yeah granted, with 1 to 20 there is no solution without room for arguments) –  TheConstructor Mar 8 at 18:48
    
@Actually, there are quite a few ways to distribute the assets. I listed some of the ways in an addendum. Note: Only one wife's assets are listed; the other gets the complement. –  David Carraher Mar 8 at 20:02
    
That's one of the reasons I choose to build my inital stacks as I do: so normally the two most valuable things are not on the same stack. Your initial solution proves that there are 10 pairs of numbers with a sum of 21; you implicitly choose consecutive pairs. –  TheConstructor Mar 8 at 20:11
    
Yes, I appreciate the logic of your approach. –  David Carraher Mar 8 at 21:14

J

There's a cheat sheet of all the J primitives at this link, in case you want to follow along at home. Remember: J is generally read from right to left, so that 3*2+1 is 7, not 9. Every verb (J for function) is either monadic, so in front like f y, or dyadic, so in between like x f y.

N =: (". 1!:1 ] 1) % 2          NB. number of items per wife
S =: ". 1!:1 ] 1                NB. list of items to distribute

bins =: #: i. 2 ^ 2*N           NB. all binary strings of length 2n
even =: bins #~ N = +/"1 bins   NB. select those with row-sum 1

NB. all distributions of equal numbers of items to each wife
NB. resultant shape: a list of 2xN matrices
NB. this /. adverb is where all the magic happens, see below
dist =: even ]/."1 S

diff =: | -/"1 +/"1 dist        NB. difference in wives' values
idx  =: (i. <./) diff           NB. index of the lowest difference

1!:2&2 idx { dist               NB. print the winning distribution of items
1!:2&2 'diff=', idx { diff      NB. and the difference of that distribution

Notes and explanations:

  • u/ means "fold u over", so perform the binary operation over each element in the list. So for example: +/ means Fold Plus, or Sum; <. is Lesser Of, so <./ means Fold Lesser Of, or Minimum.

  • u"1 means "perform u on 1-dimensional cells", i.e. over every row. Normally the verbs in J are either atomic, or apply to the whole argument. This applies to both arguments if the verb is used dyadically (with two arguments). Consider the following:

       i. 2 3        NB. just a 2x3 matrix of numbers
    0 1 2
    3 4 5
       +/   i. 2 3   NB. Sum the items
    3 5 7
       +/"1 i. 2 3   NB. Sum the items of each row
    3 12
    
  • #: is a verb that expands a number into its binary representation. When you use it on a list with more than one element, it will also align all the numbers properly, so that #:i.2^n will get you every binary string of length n.

  • /., when used dyadically, is called Key. It uses the elements of the list on the left side as keys, and those on the right side as values. It groups together each set of values that share a key, and then performs some operation on them.

    In the case of ]/., the operation is just the identity verb, so nothing altogether special is happening there, but the fact that /. will partition up the list for us is the important bit. This is why we create the binary lists: so that for each list ("1), we can divvy up the gifts for the wives in all possible ways.

  • 1!:1]1 and 1!:2&2 are the read-in and write-out operations, respectively. The 1!:n part is the verb and the other number is the file handle. 1 is console in, 2 is console out, and 3 4 5 are stdin, stdout, and stderr. We also use ". when reading so that we convert the input strings to numbers.

share|improve this answer
    
+1 for submitting an answer in J and AT LEAST TRYING to make it understandable. –  steveverrill Mar 9 at 17:15

Clojure

(defn divide [n]
 (loop [lv [] rv [] d (reverse (sort n))]
  (if (empty? d)
   [lv rv]
   (if (> (reduce + lv) (reduce + rv))
     (if (>= (count lv ) (count rv))
       (recur lv (conj rv (first d)) (into [] (rest d)))
       (recur (conj lv (last d)) rv (pop d))) 
     (if (<= (count lv ) (count rv))
       (recur (conj lv (first d)) rv (into [] (rest d)) )
       (recur lv (conj rv (last d)) (pop d)))))))


 (defn display [[f s]]
   (println f)
   (println s)
   (println (str "Diff " (- (reduce + f) (reduce + s)))))

Test

 (->> 
 [5 1 89 36 2 -4 20 7]
 divide 
 display)


 =: [89 -4 1 2]
    [36 20 7 5]
    Diff 20
share|improve this answer
    
Result sets should be of equal size and the difference between the values inside each set should be printed. Judging by the results of a quick test on ideone you may have missed both points –  TheConstructor Mar 8 at 21:38
    
add display method to print result. –  Mamun Mar 8 at 21:54
    
Result set now equal size –  Mamun Mar 8 at 23:14
    
For [1 4 5 6 7 8] your program calculated [8 5 4] [7 6 1] Diff 3 where clearly solutions with a difference of 1 exist. –  TheConstructor Mar 9 at 7:39

MATLAB

Here is my solution:

%input array
presents=zeros(2,8);
presents(1,1)=8; %number of presents
presents(2,:)=[1 2 7 4 5 3 2 8]; %list of presents

%calculate the cumulative sum of all permutations
%its all about the gift values
how_many=presents(1,1);
options=perms(presents(2,:);
subtotals=cumsum(options,2);

%find the first index where the difference between the two parts is minimal
%makes both wives happy!!
[~, double_happiness] = min(abs(sum(presents(2,:))/2-subtotals(:,how_many/2)));

%create the present lists for Jennifer and Kate :)
for_jennifer=options(double_happiness,1:how_many/2)
for_kate=options(double_happiness,how_many/2+1:end)

For example the present list in my source code results in:

for_jennifer =

     8     2     5     1


for_kate =

     4     7     2     3

which is both 16.

If I golf my code, which is less fun I get a very unoptimised 132 chars. Beat that ;)

function f(p);o=perms(p(:,2));s=cumsum(o,2);[~,d]=min(abs(sum(p(:,2))/2-s(:,p(1,1)/2)));a={o(d,1:p(1,1)/2);o(d,p(1,1)/2+1:end)};a{:}
share|improve this answer
    
The input array must be square. –  David Carraher Mar 8 at 14:35
    
No, not square? But now I see the number of items should be in the first row. I'll change it. –  mmumboss Mar 8 at 14:50

PHP

Warning: Very dirty code
It tries every possible permutation of the input array.

Ideone sample for 4/1 2 3 4: http://ideone.com/gIi174

<?php
// Discard the first input line! It's useless :)
fgets(STDIN);
$numbers = explode(' ', rtrim(fgets(STDIN)));
$valuePerWife = array_sum($numbers) / 2;

// Taken from here: http://stackoverflow.com/a/13194803/603003
// Credits to dAngelov: http://stackoverflow.com/users/955185/dangelov
function pc_permute($items, $perms = array( )) {
    if (empty($items)) {
        $return = array($perms);
    }  else {
        $return = array();
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
         list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             $return = array_merge($return, pc_permute($newitems, $newperms));
         }
    }
    return $return;
}


foreach (pc_permute($numbers) as $permutation) {
    $sum = 0;
    $rest = [];

    for ($i=0; $i<count($permutation); $i++) {
        $sum += $permutation[$i];
        if ($sum == $valuePerWife) {
            $rest = array_slice($permutation, $i + 1);
            break;
        }
    }

    if (array_sum($rest) == $valuePerWife) {
        echo implode(' ', array_slice($permutation, 0, $i + 1)), "\n";
        echo implode(' ', array_slice($permutation, $i + 1)), "\n";
        echo 'diff=0';
        exit;
    }
}
exit('DIDNT FOUND ANY COMBINATION!');
share|improve this answer

Python:

import itertools as t
raw_input()
a=[int(i) for i in raw_input().split()]
a=list(t.permutations(a))
b=len(a[0])/2
c=[(d[b:],d[:b]) for d in a]
d=[abs(sum(d[b:])-sum(d[:b])) for d in a]
e=zip(d,c)
e.sort()
print " ".join([str(i) for i in e[0][1][0]])
print " ".join([str(i) for i in e[0][1][1]])
print "diff",e[0][0]

or a bit golfified:

import itertools as t
b=int(raw_input())/2
e=[(abs(sum(d[b:])-sum(d[:b])),(d[b:],d[:b])) for d in t.permutations([int(i) for i in raw_input().split()])]
e.sort()
f=e[0]
g=f[1]
print " ".join([str(i) for i in g[0]]),"\n"," ".join([str(i) for i in g[1]]),"\n","diff=",f[0]

Or even further golfified, since half the lines is just makeup. (assuming I can just dump the raw internal array, since this isn't specified in the op) You can leave away the print in (for example) the interactive shell, and add a [::-1] (on the very end, after [0]) if you really want the diff last.

import itertools as t
b=int(raw_input())/2
print sorted([(abs(sum(d[b:])-sum(d[:b])),(d[b:],d[:b])) for d in t.permutations([int(i) for i in raw_input().split()])])[0]

(results in (0, ((1, 2, 7, 8), (3, 4, 5, 6))))

This, however, is just bruteforcing all posible combinations, and shouldn't be considered remotely efficient. However, if the list being equal lengths doesn't matter, this would also work (on large arrays):

raw_input()
a,b=[],[]
for i in sorted([int(i) for i in raw_input().split()])[::-1]:
    b.append(i)
    if sum(b)>sum(a): b,a=a,b
print a,b,abs(sum(b)-sum(a))

With the code under this for example, it runs with barely a difference at all: 500k on 10^10 max value isn't a lot, so to say. This is also a lot faster: where the other code probably wouldn't finish in under a year (and that's very optimistic), this runs in about half a second, even though your milage may vary.

def raw_input():
    import random
    return " ".join([str(random.randint(1,10**10)) for _ in range(10000)])

raw_input()
a,b=[],[]
for i in sorted([int(i) for i in raw_input().split()])[::-1]:
    b.append(i)
    if sum(b)>sum(a): b,a=a,b
print a,b,abs(sum(b)-sum(a))
share|improve this answer

Literate Haskell

> import Data.List
> import Data.Function

I made use of the list monad to split it up.

> divide []=return ([], [])
> divide (x:xs)=do
>   (w1, w2) <- divide xs
>   [(x:w1, w2), (w1, x:w2)]

Then we make a rater.

> rating (w1, w2)=abs $ (sum w1) - (sum w2)

And then a function that will minimize the difference.

> best = minimumBy (compare `on` rating) . filter (\(x,y)->length x == length y)

And something that combines them all.

> bestDivison=best . divide

Next a parser.

> parse::String->[Int]
> parse=fmap read . words

And an output formatter.

> output (w1,w2)=unlines [unwords (map show w1)
>                        , unwords ( map show w2)
>                        , "diff="++(show $ abs $ (sum w1) - (sum w2))]

And now the program

> main = do
>   getLine --Ignored, I don't need the arrays length
>   input <- fmap parse getLine
>   putStrLn "" --For readability
>   putStrLn $ output $ bestDivison input

Example:

λ <*Main>: main
8
5 1 89 36 2 -4 20 7

5 36 20 7
1 89 2 -4
diff=20
share|improve this answer
    
Result sets should be of equal size –  TheConstructor Mar 8 at 21:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.