Guava Kollektionen: limit Permutation Größe

Question

Mit Guave 12 Collections2.permutations(), ich frage mich, ob es möglich ist, die Größe der Permutationen zu begrenzen?

Genauer gesagt möchte ich eine Liste von k-dimensionalen Permutationen innerhalb einer Liste von n Elementen erhalten, anstatt eine Liste aller n-dimensionalen Permutationen zu erhalten.

Derzeit wenn ich eine Liste von 4 Früchte, Permutationen() übergeben wird derzeit eine Liste von 24 4-sized Permutationen zurückkehren, obwohl ich in das Abrufen nur daran interessiert bin, sagen wir, die 4 einzigartige Größe 3 Permutationen .

sagen, dass ich eine Liste von 4 Früchte haben:

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

Wenn ich in der Größe 3 Permutationen nur daran interessiert bin, ich das zurück folgenden möchten:

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

Könnte jemand bitte geben irgendwelche Hinweise auf eine Lösung? Vielen Dank !

Answer 1

Dieser Code arbeitet die Variationen aus, dann führt die Permutationen auf jedem eindeutigen Satz von 3.

dh für "A", "B", "C", "D" sind die Möglichkeiten [[A, B, C], [A, B, D], [A, C, D], [B, C, D]]. Wir berechnen dann die Permutationen für jeden Dreier (oder n-einige) und fügen die Möglichkeiten an eine Liste an.

PermutationsOfN.processSubsets (List gesetzt, int k) Rückkehr: [[A, B, C], [A, B, D], [A, C, D], [B, C, D ]]

Noch etwas weiter gehen PermutationsOfN.Permutationen (Listenliste, int-Größe) gibt:
[[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; 
    } 
} 

Eine besondere Erwähnung geht an meriton deren Antwort here half mir, es funktioniert.

Answer 2

Es gibt keine integrierte Guava-Funktion, die das tut, obwohl Sie submit a feature request könnten.

Wenn ich eine Implementierung geschrieben hat, denke ich die einfachste Art und Weise (mit Gosper's hack) und dann Permutationen von denen mit Collections2.permutations durch Kombinationen zu durchlaufen wäre.

Alternativ dazu sieht es aus, als ob geringfügige Änderungen am normalen Permutationsgenerierungsalgorithmus basierend auf this Python code ausreichen.

Answer 3

Eine direkte Antwort auf Ihre Frage wäre dies:

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

und dann:

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

Aber es braucht nur die ersten, und nicht eine spezifisch definierte Menge, Sie wahrscheinlich besser dran folgenden Louis 'Rat