java - 数组中字符的组合与java中的公式nPr

Question

有人可以告诉我如何使用公式 nPr 实现存储在数组中的字符值的组合。例如，如果我有一组 {a,b,v,f} 并且我想一次选择 2 个，那么答案应该是 {a,b} {a,v} {a,f} {b,v} {b,f} {v,f}。

或任何链接，如果此问题在网络上有解决方案。谢谢。

Answer 1

这是一个通用的实现：

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;
}

像这样使用它：

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 );

这是一个ideone。

Answer 2

根据您的示例，我正在打印组合：

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 );
        }
    }
}

但是你必须意识到，组合的数量是，所以它是一个相当大的数字，例如打印输出 10 百万个数组需要一段时间......