अमरूद संग्रह: सीमा क्रमचय आकार

Question

अमरूद 12 Collections2.permutations(), मैं सोच रहा हूँ अगर यह क्रमपरिवर्तन के आकार को सीमित करने के लिए संभव है का उपयोग करते हुए?

अधिक सटीक, मैं सभी एन-आकार के क्रमपरिवर्तनों की सूची प्राप्त करने के बजाय एन तत्वों की सूची में के-आकार के क्रमपरिवर्तनों की एक सूची प्राप्त करना चाहता हूं।

वर्तमान में, अगर मैं 4 फल, क्रमपरिवर्तन() की एक सूची पारित वर्तमान में 24 4 आकार के क्रमपरिवर्तन की एक सूची प्रदान करेगा, हालांकि मैं केवल पुन: प्राप्त करने, कहते हैं में दिलचस्पी रखता हूँ, 4 अद्वितीय आकार 3 क्रमपरिवर्तन । मैं चाहता लौटे निम्नलिखित

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

यदि मैं केवल आकार 3 क्रमपरिवर्तन में दिलचस्पी रखता हूँ,:

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

किसी को भी कृपया प्रदान कर सके

मैं 4 फल की एक सूची है कहो समाधान के लिए कोई संकेत? धन्यवाद !

Answer 1

यह कोड विविधताएं काम करता है, फिर प्रत्येक अद्वितीय सेट पर क्रमपरिवर्तन चलाता है।

यानी "ए", "बी", "सी", "डी" के लिए संभावनाएं हैं [[ए, बी, सी], [ए, बी, डी], [ए, सी, डी], [बी, सी, डी]]। फिर हम प्रत्येक त्रिगुट (या एन-कुछ) पर क्रमपरिवर्तन की गणना करते हैं और संभावनाओं को एक सूची में जोड़ते हैं।

PermutationsOfN.processSubsets (सूची सेट, पूर्णांक ट) रिटर्न: [[ए, बी, सी], [ए, बी, डी], [ए, सी, डी], [बी, सी, डी ]]

इसे थोड़ा और आगे लेना PermutationsOfN।क्रमपरिवर्तन (सूची सूची, int आकार) रिटर्न:
[[ए, बी, सी], [ए, सी, बी], [सी, ए, बी], [सी, बी, ए], [बी, सी , ए], [बी, ए, सी], [ए, बी, डी], [ए, डी, बी], [डी, ए, बी], [डी, बी, ए], [बी, डी, ए ], [बी, ए, डी], [ए, सी, डी], [ए, डी, सी], [डी, ए, सी], [डी, सी, ए], [सी, डी, ए], [सी, ए, डी], [बी, सी, डी], [बी, डी, सी], [डी, बी, सी], [डी, सी, बी], [सी, डी, बी], [सी , बी, डी]]

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

एक विशेष उल्लेख जिसका जवाब here मुझे इस पर काम में मदद की meriton को जाता है।

Answer 2

कोई अंतर्निहित गुवा सुविधा नहीं है जो ऐसा करता है, हालांकि आप 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); 
    } 

लेकिन यह केवल पहले लोगों को एक विशेष रूप से परिभाषित सेट अपने शायद निम्नलिखित से बेहतर लगता है और नहीं, लुई की सलाह