6

guava 12 Collections2.permutations()を使用して、順列のサイズを制限できるかどうか疑問に思っていますか?

より正確には、すべての n サイズの順列のリストを取得するのではなく、n 個の要素のリスト内で k サイズの順列のリストを取得したいと考えています。

現在、4 つの果物のリストを渡すと、permutations()は現在、24 個の 4 サイズの順列のリストを返しますが、たとえば、4 つの一意のサイズ 3 の順列を取得することにのみ関心があります。

4 つの果物のリストがあるとします。

["Banana", "Apple", "Orange", "Peach"]

サイズ 3 の順列のみに関心がある場合は、次のものが返されます。

["Banana", "Apple", "Orange"]
["Banana", "Apple", "Peach"]
["Banana", "Orange", "Peach"]
["Apple", "Orange", "Peach"]

誰か解決策のヒントを教えてください。ありがとう ！

4

3 に答える 3

9

このコードはバリエーションを計算し、3 つの一意のセットごとに順列を実行します。

つまり、"A"、"B"、"C"、"D" の場合、可能性は [[A, B, C], [A, B, D], [A, C, D], [B, C, D]]。次に、各 threesome (または n-some) の順列を計算し、可能性をリストに追加します。

PermutationsOfN.processSubsets( List set, int k )戻り値: [[A, B, C], [A, B, D], [A, C, D], [B, C, D]]

もう少しPermutationsOfN.permutations( List list, int size )は次を返します:
[[A, B, C], [A, C, B], [C, A, B], [C, B, A], [B, C, A], [B, A, C], [A, B, D], [A, D, B], [D, A, B], [D, B, A], [B 、D、A]、[B、A、D]、[A、C、D]、[A、D、C]、[D、A、C]、[D、C、A]、[C、D] 、A]、[C、A、D]、[B、C、D]、[B、D、C]、[D、B、C]、[D、C、B]、[C、D、B] ]、[C、B、D]]

import java.util.Collection;
import java.util.List;

import com.google.common.collect.Collections2;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Lists;

public class PermutationsOfN<T> {
  public static void main( String[] args ) {
    List<String> f = Lists.newArrayList( "A", "B", "C", "D" );
    PermutationsOfN<String> g = new PermutationsOfN<String>();
    System.out.println( String.format( "n=1 subsets %s", g.processSubsets( f, 1 ) ) );
    System.out.println( String.format( "n=1 permutations %s", g.permutations( f, 1 ) ) );
    System.out.println( String.format( "n=2 subsets %s", g.processSubsets( f, 2 ) ) );
    System.out.println( String.format( "n=2 permutations %s", g.permutations( f, 2 ) ) );
    System.out.println( String.format( "n=3 subsets %s", g.processSubsets( f, 3 ) ) );
    System.out.println( String.format( "n=3 permutations %s", g.permutations( f, 3 ) ) );
    System.out.println( String.format( "n=4 subsets %s", g.processSubsets( f, 4 ) ) );
    System.out.println( String.format( "n=4 permutations %s", g.permutations( f, 4 ) ) );
    System.out.println( String.format( "n=5 subsets %s", g.processSubsets( f, 5 ) ) );
    System.out.println( String.format( "n=5 permutations %s", g.permutations( f, 5 ) ) );
  }

  public List<List<T>> processSubsets( List<T> set, int k ) {
    if ( k > set.size() ) {
      k = set.size();
    }
    List<List<T>> result = Lists.newArrayList();
    List<T> subset = Lists.newArrayListWithCapacity( k );
    for ( int i = 0; i < k; i++ ) {
      subset.add( null );
    }
    return processLargerSubsets( result, set, subset, 0, 0 );
  }

  private List<List<T>> processLargerSubsets( List<List<T>> result, List<T> set, List<T> subset, int subsetSize, int nextIndex ) {
    if ( subsetSize == subset.size() ) {
      result.add( ImmutableList.copyOf( subset ) );
    } else {
      for ( int j = nextIndex; j < set.size(); j++ ) {
        subset.set( subsetSize, set.get( j ) );
        processLargerSubsets( result, set, subset, subsetSize + 1, j + 1 );
      }
    }
    return result;
  }

  public Collection<List<T>> permutations( List<T> list, int size ) {
    Collection<List<T>> all = Lists.newArrayList();
    if ( list.size() < size ) {
      size = list.size();
    }
    if ( list.size() == size ) {
      all.addAll( Collections2.permutations( list ) );
    } else {
      for ( List<T> p : processSubsets( list, size ) ) {
        all.addAll( Collections2.permutations( p ) );
      }
    }
    return all;
  }
}

特別な言及は、ここでの答えが私がそれを解決するのに役立ったメリットンに行きます.

于 2012-06-20T16:26:14.253 に答える
7

機能要求を送信することはできますが、これを行う組み込みの Guava 機能はありません。

私が実装を書いている場合、最も簡単な方法は、( Gosper の hackを使用して) 組み合わせを反復処理し、次に Collections2.permutations を使用してそれらの順列を反復することだと思います。

あるいは、この Python コードに基づいて、通常の順列生成アルゴリズムを少し変更するだけで十分のようです。

于 2012-06-20T14:19:05.927 に答える
1

あなたの質問に対する直接的な答えは次のようになります。

public static <X> List<List<X>> test(List<X> input, final int n, final int m) {
    int x = 0;

    List<List<X>> newPerm = Lists.newArrayList();
    Collection<List<X>> perm = Collections2.permutations(input);
    for (Iterator<List<X>> it = perm.iterator(); it.hasNext(); x++) {
        if (x >= n) {
            break;
        }

        List<X> list = it.next();
        newPerm.add(Lists.partition(list, m).get(0));
    }

    return newPerm;
}

その後：

    List<String> list = Lists.newArrayList("Banana", "Apple", "Orange", "Peach");
    List<List<String>> answer = test(list, 4, 3);
    for (List<String> list1 : answer) {
        System.out.println(list1);
    }

ただし、特に定義されたセットではなく、最初のもののみが必要です。おそらく、ルイスのアドバイスに従う方がよいでしょう

于 2012-06-20T14:28:25.183 に答える