Guava Collections: Swapping Constraints

Question

Using guava 12 Collections2.permutations () , I wonder if it is possible to limit the size of permutations?

More precisely, I would like to get a list of k-dimensional permutations in a list of n elements, rather than getting a list of all n-dimensional permutations.

Currently, if I pass a list of 4 fruits, permutations () will currently return a list of 24 4-dimensional permutations, although I am only interested in getting, say, 4 unique sizes of 3.

Let's say I have a list of 4 fruits:

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

If I'm only interested in size 3 permutations, I would like to return the following:

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

Can anyone point out any hints of a solution? Thanks!

Answer 1

This code performs the variations, then triggers permutations on each unique set of 3.

i.e. for "A", "B", "C", "D" possible [[A, B, C], [A, B, D], [A, C, D], [B, C, D]] . Then we calculate the permutations on each triple (or n-some) and add features to the list.

PermutationsOfN.processSubsets (set of lists, int k) returns: [[A, B, C], [A, B, D], [A, C, D], [B, C, D]]

Taking it a little further 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; } } 

A special mention goes to meriton , whose answer here helped me figure it out.

Answer 2

There is no built-in Guava function that does this, although you can send a function request .

If I were writing an implementation, I think that the easiest way would be to iterate over combinations (with Gosper hack ), and then rearrange those with Collections2.permutations.

Alternatively, it seems that some minor changes to the normal permutation generation algorithm are sufficient based on this Python code .

Answer 3

The direct answer to your question will be as follows:

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

and then:

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

But this requires only the first, and not a specific set, most likely, it is better to follow Louis's advice.