гуавы Коллекции: предел размера перестановки

Question

Использование гуавы 12 Collections2.permutations(), я задаюсь вопросом, если это возможно, чтобы ограничить размер перестановок?

Точнее, я хотел бы получить список k-размерных перестановок внутри списка из n элементов, вместо того, чтобы получать список всех n-размерных перестановок.

В настоящее время, если я передаю список из 4 фруктов, перестановок() будет в настоящее время возвращает список из 24 4 размера перестановок, хотя я заинтересован только в получении, скажем, перестановки 4 уникального размера 3 ,

Скажем, у меня есть список из 4 фруктов:

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

Если я заинтересован только в 3-х размерных перестановок, я хотел бы следующее вернулся:

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

Может кто-нибудь пожалуйста, предоставьте любые намеки на решение? Благодаря !

Answer 1

Этот код разрабатывает варианты, затем запускает перестановки для каждого уникального набора из 3.

т. Е. Для «A», «B», «C», «D» возможны [[A, B, C], [A, B, D], [A, C, D], [B, CD]]. Затем мы вычисляем перестановки в каждой тройке (или n-some) и добавляем возможности к списку.

PermutationsOfN.processSubsets (Список набор, Int к) возвращает: [[A, B, C], [А, В, D], [А, С, D], [B, C, D ]]

Принимая это немного далее ПерестановкиОф.перестановки (список списка, размер int) возвращает:
[[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; 
    } 
} 

Особого упоминания идет к meriton, ответ here помог мне решить это.

Answer 2

Нет встроенной функции Guava, которая делает это, хотя вы можете submit a feature request.

Если бы я писал реализацию, я думаю самый простой способ будет перебирать комбинации (с Gosper's hack), а затем перестановки тех, с Collections2.permutations.

В качестве альтернативы, похоже, некоторые незначительные модификации алгоритма генерации нормальных подстановок достаточно на основе this Python code.

Answer 3

Прямой ответ на ваш вопрос будет такой:

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

Но это занимает только первые из них, а не специально определенного набора, ваши, вероятно, лучше следующие Совет Луи