0

式nPrを使用して配列に格納されている文字値の組み合わせを実装する方法を教えてもらえますか?たとえば、{a、b、v、f}のセットがあり、一度に2つを選択したい場合、答えは{a、b} {a、v} {a、f} {b、v}になります。 {b、f} {v、f}。

または、この問題がWeb上で解決策を持っている場合は、任意のリンク。ありがとう。

4

2 に答える 2

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

ここにイデオンがあります。

于 2012-04-22T06:38:40.470 に答える
0

あなたの例によると、私は組み合わせを印刷しています:

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

ただし、組み合わせの数はk 上の n は n!/k!*(nk)! です。であるため、たとえば非常に大きな数で26 オーバー 13 は 10400600あり、1,000 万の配列を出力するにはしばらく時間がかかることに注意してください...

于 2012-04-22T06:29:59.050 に答える