Combination of characters in an array with formula nPr in java

Question

Can someone please tell me how to implement combination for character values stored in an array with formula nPr. For example if I have a set of {a,b,v,f} and I want to choose 2 at a time the answer should be {a,b} {a,v} {a,f} {b,v} {b,f} {v,f}.

Or any link if this problem has a solution on the web. Thanks.

These (in your example) are combinations, in permutations you would also care about order. — trutheality, Apr 22 '12 at 06:04

trutheality · Accepted Answer · 2012-04-22T17:07:27.430

Here is a general implementation:

static <T> List<List<T>> combinations( List<T> list, int n ){

    List<List<T>> result;

    if( list.size() <= n ){

        result = new ArrayList<List<T>>();
        result.add( new ArrayList<T>(list) );

    }else if( n <= 0 ){

        result = new ArrayList<List<T>>();
        result.add( new ArrayList<T>() );

    }else{

        List<T> sublist = list.subList( 1, list.size() );

        result = combinations( sublist, n );

        for( List<T> alist : combinations( sublist, n-1 ) ){
            List<T> thelist = new ArrayList<T>( alist );
            thelist.add( list.get(0) );
            result.add( thelist );
        }
    }

    return result;
}

Use it like this:

List<Character> list = new ArrayList<Character>();
list.add('a');
list.add('b');
list.add('c');
list.add('d');

List<List<Character>> combos = combinations( list, 2 );

Here's an ideone.

Maybe I'm doing something wrong, but your solution is not working well for list `{ '1', '2', '3', '4', '5', '6' }` and 3. — Betlista, Apr 22 '12 at 09:21
@Betlista sorry... that had a few bugs... that's what happens when you write out an algorithm without debugging it with a real compiler. Fixed. — trutheality, Apr 22 '12 at 17:10

Betlista · Answer 2 · 2012-04-22T09:40:58.953

According to your example I'm printing combinations:

public class PrintCombinations {

    public static void main( final String[] args ) {
        // testing input 1
        int n = 2;
        char[] a = { 'a', 'b', 'v', 'f' };
        solve( n, a );

        // testing input 2
        n = 3;
        a = new char[] { '1', '2', '3', '4', '5' };
        solve( n, a );

    }

    private static void solve( final int n, final char[] a ) {
        final int[] selected = new int[n];
        print( n, a, 0, selected );
    }

    // need to know how many items are selected - n, input array - a
    // item which can be selected next - from and already selected items
    private static void print( final int n, final char[] a, final int from, final int[] selected ) {
        if ( n == 0 ) { // all selected, just print them
            for ( int i = 0; i < selected.length; ++i ) {
                System.out.print( a[ selected[ i ] ] + " " );
            }
            System.out.println();
            return;
        }
        // select one and use recursion for others
        for ( int i = from; i < a.length; ++i ) {
            selected[ selected.length - n ] = i;
            print( n - 1, a, i + 1, selected );
        }
    }
}

But you have to realize, that number of combinations is n over k is n!/k!*(n-k)! , so it is quite big number for example 26 over 13 is 10400600 and printout 10 milions arrays will take a while...

Combination of characters in an array with formula nPr in java

2 Answers2