How do I create a decent simple combination algorithm?

Vote count:

0

I am having a hard time implementing a combination algorithm that returns all possible combinations from a given List. So far I did this:

public static <T> Set< Set<T> > getAllCombinations( List<T> list ) {
        int k = 2;
        List<T> branch = new ArrayList<T>( list.size() );
        combine( list, k, 0, branch, 0 );
        return new HashSet< Set<T> >();
    }
    private static <T> void combine( List<T> arr, int k, int startId, List<T> branch, int numElem ) {
        if ( numElem == k ) {
            System.out.println( branch );
            return;
        }
        for ( int i = startId; i < arr.size(); ++i ) {
            branch.add( numElem++, arr.get( i ) );
            combine( arr, k, ++startId, branch, numElem );
            --numElem;
        }
    }

I am trying to implement in order that the test below passes, but I am failing to do so:

@Test
    public void should_get_3_levels_combinations() {
        List<Integer> list = new ArrayList<Integer>() {{
            add( 1 );
            add( 2 );
            add( 3 );
        }};
        Set< Set<Integer> > result = CollectionUtils.getAllCombinations( list );

        Assert.assertFalse( "Should not get 4 levels", contains( result, 1, 2, 3, 4 ) );
        Assert.assertTrue( "Should get 3 levels", contains( result, 1, 2, 3 ) );
    }

@SafeVarargs
    private final <T> boolean contains( Set< Set<T> > combinations, T... elements ) {
        for ( Set<T> combination : combinations ) {
            int matches = 0;
            for ( T element : elements ) {
                if ( combination.contains( element ) ) {
                    matches++;
                } else {
                    matches--;
                }
            }
            if ( matches == combination.size() ) {
                return true;
            }
        }
        return false;
    }

Needless to say, but I am very bad handling low level algorithms. The idea here is to make it as simple as possible.

Do you know how to make the tests pass (make it return a Set< Set<T> >)?

asked 17 secs ago

Fagner Brack

490

How do I create a decent simple combination algorithm?