Colecciones: Guayaba límite de tamaño de permutación

Question

El uso de guayaba 12 Collections2.permutations(), me pregunto si es posible limitar el tamaño de las permutaciones?

Más precisamente, me gustaría obtener una lista de permutaciones de tamaño k dentro de una lista de n elementos, en lugar de obtener una lista de todas las permutaciones n-sized.

Actualmente, si paso una lista de 4 frutas, permutaciones() actualmente se devolverá una lista de las 24 permutaciones de 4 tamaño, aunque sólo estoy interesado en la recuperación de, por ejemplo, los 4 tamaño único 3 permutaciones .

Decir que tengo una lista de 4 frutas:

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

Si estoy interesado sólo en tamaño 3 permutaciones, me gustaría que el siguiente regresaron:

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

Podría alguien por favor provea ¿Algún consejo para una solución? Gracias !

Answer 1

Este código resuelve las variaciones, luego ejecuta las permutaciones en cada conjunto único de 3.

es decir, para "A", "B", "C", "D" las posibilidades son [[A, B, C], [A, B, D], [A, C, D], [B, DISCOS COMPACTOS]]. Luego calculamos las permutaciones en cada trío (o n-some) y anexamos las posibilidades a una lista.

PermutationsOfN.processSubsets (lista configurado, int k) devuelve: [[A, B, C], [A, B, D], [A, C, D], [B, C, D ]]

Adelantándolo un poco más PermutationsOfN.permutaciones (lista de lista, tamaño int) devuelve:
[[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 a, 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; 
    } 
} 

Una mención especial va a meriton cuya respuesta here me ayudó a trabajar a cabo.

Answer 2

No existe una función incorporada de guayaba que lo haga, aunque podría submit a feature request.

Si estuviera escribiendo una aplicación, lo que la forma más sencilla sería la de iterar a través de combinaciones (con Gosper's hack), y luego permutaciones de los que tienen Collections2.permutations.

Alternativamente, parece que bastan algunas modificaciones menores al algoritmo de generación de permutación normal, basado en this Python code.

Answer 3

Una respuesta directa a su pregunta sería la siguiente:

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

y luego:

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

Pero se tarda sólo las primeras, y no un conjunto definido específicamente, su probablemente mejor siguiente Consejo de Louis