使用遞歸來獲得具有某些參數的集合的所有組合

Question

我想找到一種方法來使用遞歸來從具有幾個參數的集合中生成所有元素的獨特組合... 1）我想能夠定義單個組合的大小。 2）我希望能夠從集合中提供我自己的元素（小於提供的大小）以生成包含我提供的元素的所有組合。

由於可能已經令人困惑的輸入是這樣...

輸入：（組元素中，單個組合的大小，提供元素（從0到大小-1）

輸出：所有可能組合的集合（順序無關）

例如，假設我有字母az作爲我提供的元素的集合，我們還要說我希望組合的大小爲5.讓我們也說我爲該方法提供「FG」。

getCombos(Set<V> collection, int size, Set<V> provided) 

return Set<Set<V>> combos 

下面是它會如何看待與輸入，

getCombos(alphabet, 5, myChars) 

這個方法應該返回24 * 23 * 22（12144）獨特的5字母組合，其中包括F和G

這裏是我的嘗試，我覺得這可能是失敗的。

public static <V> HashSet<HashSet<V>> getCombos(HashSet<V> base, HashSet<V> elements, int size) { 
    HashSet<HashSet<V>> combos = new HashSet<HashSet<V>>(); 
    HashSet<V> curr = new HashSet<V>(base); 
    recur(curr, combos, base, elements, size); 
    return combos; 

} 

public static <V> void recur(HashSet<V> curr, HashSet<HashSet<V>> combos, HashSet<V> base, HashSet<V> elements, int size) { 
    if (curr.size() == size) 
     combos.add(curr); 
    else 
     for (V v : elements) { 
      curr.add(v); 
      recur(curr, combos, base, elements, size); 
      // This part below is where i feel like i'm going wrong and i'm not sure what to do 
      curr = dupe(base); 
      break; 
     } 
} 

Answer 1

你的想法幾乎是正確的，你只是在那裏有一些邏輯錯誤。這種希望應該工作，你希望它的方式：

public static <V> HashSet<HashSet<V>> getCombos(HashSet<V> base, HashSet<V> elements, int size) { 
    HashSet<HashSet<V>> combos = new HashSet<HashSet<V>>(); 
    HashSet<V> inner = dupe(base); 
    inner.removeAll(elements); 
    recur(elements, combos, inner, size); 
    return combos; 

} 

public static <V> HashSet<V> dupe(HashSet<V> orig) { 
    return new HashSet<V>(orig); 
} 

public static <V> void recur(HashSet<V> curr, HashSet<HashSet<V>> combos, HashSet<V> base, int size) { 
    if (curr.size() == size) { 
     combos.add(dupe(curr)); 
    } else { 
     HashSet<V> inner = dupe(base); 
     for (V v : base) { 
      inner.remove(v); 
      curr.add(v); 
      recur(curr, combos, inner, size); 
      curr.remove(v); 
     } 
    } 
} 

對於你所給出的示例的字母，它會給正確2024，因爲你的12144號碼包含每種組合的三個字母加到FG的6重排序。