[Week Seventeen] Programming Contest - Integer Combinations

General Discussion Off Topic
1

Welcome back to the weekly programming contests! If you are new to the contest or need a refresher don’t forget to read up on the rules and information Posted Here

This week’s challenge is to write a method that takes in an array of integers and returns a two dimensional array containing all possible Combinations of the given array with all possible sizes.

Examples (order doesn’t matter):

c([]) -> [[]]
c([3]) -> [[], [3]]
c([2, 7]) -> [[], [2], [7], [2, 7]]
c([7, 7, 7]) -> [[], [7], [7, 7], [7, 7, 7]]
c([0, 3, 3] -> [[], [0], [3], [0, 3], [3, 3], [0, 3, 3]]
c([1, 2, 3] -> [[], [1], [2], [3], [1, 2], [2, 3], [1, 3], [1, 2, 3]]
c([3, 1, 2] -> [[], [1], [2], [3], [1, 2], [2, 3], [1, 3], [1, 2, 3]]

Also, if you like these weekly programming problems, please make some suggestions for the contest or specific challenges (in the main thread)! This takes time out of my Sunday and its not always fun! Using suggested challenges makes it a lot faster and easier for me.

Imports are allowed for this challenge!

Challenge Closes: Sunday 2/28/16

Good luck!

2

Imports are allowed for this challenge!

The power of Guava…

Just the method:

public static Set c(Set b){return Sets.powerSet(b);}

That’s a whooping 52 characters!
Full class:

import com.google.common.collect.Sets;import java.util.Set;class WeeklyProgrammingCompetition{Set c(Set b){return Sets.powerSet(b);}}

That’s 133 characters.

NOTE: Due to the nature of powerSet, it includes an extra empty set in the beginning.

Expanded:
https://gist.github.com/20zinnm/a67693fc32f553169237

3

I’m pretty sure I said somewhere that only imports from standard Java packages are allowed… Or else I feel like someone else would have done that already after seventeen challenges.

Also you didn’t even follow the challenge.

Regardless, I updated the rules once again to make everything more clear.

4

They previously only said that only imports from java.lang were allowed if not specified. Nothing about external imports, I read a few times :stuck_out_tongue:

5

Perhaps in one of the challenge threads then…

Either way that still isn’t a solution to the problem and since the rules are now updated you gotta follow them for any revisions you make :stuck_out_tongue:

6

I decided to reread the challenge, and I looked up the algorithm(s) for a Power Set. Here’s the new code (309 characters):

public static<T>Set<Set<T>>a(Set<T>b){Set<Set<T>>c=new HashSet<>();if(b.isEmpty()){c.add(new HashSet());return c;}List<T>d=new ArrayList(b);T e=d.get(0);Set<T>f=new HashSet(d.subList(1,d.size()));a(f).forEach((g)->{Set<T>newSet=new HashSet();newSet.add(e);newSet.addAll(g);c.add(newSet);c.add(g);});return c;}

Which comes out to be like:

public static <T> Set<Set<T>> a(Set<T> b) {
        Set<Set<T>> c = new HashSet<>();
        if (b.isEmpty()) {
            c.add(new HashSet());
            return c;
        }
        List<T> d = new ArrayList(b);
        T e = d.get(0);
        Set<T> f = new HashSet(d.subList(1, d.size()));
        a(f).forEach((g) -> {
            Set<T> newSet = new HashSet();
            newSet.add(e);
            newSet.addAll(g);
            c.add(newSet);
            c.add(g);
        });
        return c;
    }

It essentially uses recursion to go through the Power Set. More reading here (Power set - Wikipedia). Good luck to the other contenders!

I used Sets so that it could sort any object. It works for Integer, thus being a solution.

7

What about the empty Combination? It is excluded in all of your examples but the first, but I believe it is one of the possible combinations.

8

True. Updated examples.

9

Think this one’s missing [3,3]?
Also, the returned array doesn’t have to be in any particular order does it?

10

Order doesn’t matter.

I fixed the example as well.

11

I edited my submission.

12

Minified (329 chars)

public static int[][]c(int[]a){Map<Object,Object>r=new TreeMap<>();for(int l=0;l<=a.length;)c(a,new int[l],l++,0,r);return r.values().toArray(new int[r.size()][]);}static void c(int[]a,int[]v,int l,int i,Map<Object,Object>r){if(l<1)r.put(Arrays.hashCode(v),v.clone());else for(;i<=a.length-1;c(a,v,l-1,i,r))v[v.length-l]=a[i++];}
  • plus 7 chars ('public ') if the second method needs to be public
  • plus 15 chars ('Arrays.sort(a);') if the input array may not necessarily be numerically ordered
    (So worst case 351)

Readable

public static int[][] combinations(int[] input)
{
    Arrays.sort(input); //not needed if input is already ordered
    Map<Object,Object> result = new TreeMap<>();
    for (int l = 0 ; l <= input.length; l++)
    {
        combinations(input, new int[l], l, 0, result);
    }
    return result.values().toArray(new int[result.size()][]);
}

public static void combinations(int[] in, int[] val, int length, int pos, Map<Object,Object> result)
{
    if (length == 0)
    {
        result.put(Arrays.hashCode(val), val.clone()); //avoid duplicates
        return;
    }
    for (;pos <= in.length - length; combinations(in, val, length - 1, pos, result))
    {
        val[val.length - length] = in[pos++];
    }
}
```
<sub>Don't know what's up with the code formatting/colouring</sub>
13

Congratulations to @dags for winning week seventeen because he was the only one to post a valid solution!

I will post the next challenge shortly.

1 Like