遞歸地生成沒有任何循環的功率集

Question

如何編寫一個遞歸方法PowerSet（String input），該方法輸出傳遞給它的字符串的所有可能組合？

例如：冪（ 「ABC」）將打印出ABC，AB，AC，BC，A，B，C

我已經看到了環路一些遞歸的解決方案，但在這種情況下，沒有循環被允許。

任何想法？

編輯：所需的方法只有一個參數，即字符串輸入。

Answer 1

的abcd的冪爲動力的套聯盟abc，abd，acd（加上一套abcd本身*）。

P(`abcd`) = {`abcd`} + P(`abc`) + P(`abd`) + P(`acd`) + P(`bcd`) 

_{*注意空集，這是P（ABCD）的成員也是P（ABC），P（ABD）的成員，...所以上述的等價保持。}

遞歸，P（abc）= {abc} + P（ab）+ P（ac），等等

的第一種方法，在僞代碼中，可以是：

powerset(string) { 
    add string to set; 
    for each char in string { 
    let substring = string excluding char, 
    add powerset(substring) to set 
    } 
    return set;  
} 

當字符串爲空時遞歸結束（因爲它永遠不會進入循環）。

如果你真的想沒有循環，你將不得不將該循環轉換爲另一個遞歸。 現在，我們想從abc

powerset(string) { 
    add string to set; 
    add powerset2(string,0) to set; 
    return set 
} 

powerset2(string,pos) { 
    if pos<length(string) then 
    let substring = (string excluding the char at pos) 
    add powerset(substring) to set 
    add powerset2(string,pos+1) to set 
    else 
    add "" to set 
    endif 
    return set 
} 

另一種方法產生ab，ac和cb實現遞歸函數P即無論是從它的參數刪除第一個字符，或沒有。 （這裏指+工會集，.意味着串聯和λ是空字符串）

P(abcd) = P(bcd) + a.P(bcd) 
P(bcd) = P(cd) + b.P(cd) 
P(cd) = P(d) + c.P(d) 
P(d) = λ+d //particular case 

然後

P(d) = λ+d 
R(cd) = P(d) + c.P(d) = λ + d + c.(λ+d) = λ + d + c + cd 
R(bcd) = P(cd) + b.P(cd) = λ + d + c + cd + b.(λ + d + c + cd) 
          = λ + d + c + cd + b + bd + bc + bcd 
P(abcd) = λ + d + c + cd + b + bd + bc + bcd 
     + aλ + ad + ac + acd + ab + abd + abc + abcd 

如果循環被允許，那麼P超出電源設置功能。否則，我們需要一個單參數loopless函數來將給定的字符連接到給定的一組字符串上（顯然是兩個的東西）。

一些TWEAK可通過用String.replace播放（如果是String結果是期望的，或通過用List替換Set（使「額外的」參數實際上是在列表中的第一個元素）是可能的。

Answer 2

那麼，如果你沒有循環，用遞歸模擬一個，使用迭代器這是非常簡單的。

public final Set<Set<Integer>> powerSet(Set<Integer> set) { 
     Set<Set<Integer>> powerSet = new HashSet<>(); 
     powerSet(set, powerSet, set.iterator()); 
     return powerSet; 
    } 
    public final void powerSet(Set<Integer> set, Set<Set<Integer>> powerSet, Iterator<Integer> iterator) { 
     if(iterator.hasNext()) { 
      Integer exlude = iterator.next(); 
      Set<Integer> powThis = new HashSet<Integer>(); 
      powThis.addAll(set); 
      powThis.remove(exlude); 
      powerSet.add(powThis); 
      powerSet(powThis, powerSet, powThis.iterator()); 
      powerSet(set, powerSet, iterator); 
     } 
    } 
//usage 
     Set<Integer> set = new HashSet<>(); 
     set.add(1); 
     set.add(2); 
     set.add(3); 
     set.add(4); 
     log.error(powerSet(set).toString()); 

Answer 3

甲遞歸版本提出的generic solution由João Silva：

public static <T> Set<Set<T>> powerSet2(Set<T> originalSet) { 
    Set<Set<T>> sets = new HashSet<Set<T>>(); 
    if (originalSet.isEmpty()) { 
     sets.add(new HashSet<T>()); 
     return sets; 
    } 
    List<T> list = new ArrayList<T>(originalSet); 
    T head = list.get(0); 
    Set<T> rest = new HashSet<T>(list.subList(1, list.size())); 
    addSets(sets, powerSet(rest), head); 
    return sets; 
} 

private static <T> void addSets(Set<Set<T>> sets, Set<Set<T>> setsToAdd, T head) { 
    Iterator<Set<T>> iterator = setsToAdd.iterator(); 
    if (iterator.hasNext()) { 
     Set<T> set = iterator.next(); 
     iterator.remove(); 
     Set<T> newSet = new HashSet<T>(); 
     newSet.add(head); 
     newSet.addAll(set); 
     sets.add(newSet); 
     sets.add(set); 
     addSets(sets, setsToAdd, head); 
    } 
} 

我提取遞歸addSets方法來改造原有for循環：

for (Set<T> set : powerSet(rest)) { 
    Set<T> newSet = new HashSet<T>(); 
    newSet.add(head); 
    newSet.addAll(set); 
    sets.add(newSet); 
    sets.add(set); 
} 

Answer 4

這也將這樣的伎倆：

var powerset = function(arr, prefix, subsets) { 
    subsets = subsets || []; 
    prefix = prefix || []; 
    if (arr.length) { 
    powerset(arr.slice(1), prefix.concat(arr[0]), subsets); 
    powerset(arr.slice(1), prefix, subsets); 
    } else { 
    subsets.push(prefix); 
    } 
    return subsets; 
}; 

powerset('abc'); 

Answer 5

void powerSet(int * ar, int *temp, int n, int level,int index) 
{ 
    if(index==n) return; 

    int i,j; 
    for(i=index;i<n;i++) 
    { 
    temp[level]=ar[i]; 

    for(j=0;j<=level;j++) 
    printf("%d ",temp[j]); 
    printf(" - - - t\n"); 

    powerSet(ar, temp, n, level+1,i+1); 
    } 
} 

int main() 
{ 
    int price[] = {1,2,3,7}; 
    int temp[4] ={0}; 

    int n = sizeof(price)/sizeof(price[0]); 

    powerSet(price, temp, n, 0,0); 


    return 0; 
} 

Answer 6

簡單的解決方案，但與窮人的時間複雜度（2^n）是如下（僅保留一件事記住，一旦我們必須避免（即0），一旦我們把它（即1）：

public HashSet<int[]> powerSet(int n) { 
    return calcPowerSet(n-1, new HashSet<int[]>(), new int[n]); 
} 

private HashSet<int[]> calcPowerSet(int n, HashSet<int[]> result, int []set) { 
    if(n < 0) { 
     result.add(set.clone()); 
     return null; 
    } 
    else { 
     set[n] = 0; 
     calcPowerSet(n-1, result, set); 
     set[n] = 1; 
     calcPowerSet(n-1, result, set); 
     return result; 
    } 
} 

Answer 7

只是爲了好玩，那不存儲在任何一組powersets一個版本LinkedList（可以很容易去除頭元素）。 Java的8流做功能部分：

static <T> LinkedList<LinkedList<T>> powerset(LinkedList<T> elements) { 
    if (elements.isEmpty()) 
    return copyWithAddedElement(new LinkedList<>(), new LinkedList<>()); 
    T first = elements.pop(); 
    LinkedList<LinkedList<T>> powersetOfRest = powerset(elements); 
    return Stream.concat(
     powersetOfRest.stream(), 
     powersetOfRest.stream().map(list -> copyWithAddedElement(list, first))) 
      .collect(Collectors.toCollection(LinkedList::new)); 
} 

static <T> LinkedList<T> copyWithAddedElement(LinkedList<T> list, T elt) { 
    list = new LinkedList<>(list); 
    list.push(elt); 
    return list; 
} 

這是由以下Common Lisp的，這表明了正確的語言可以使事情變得更簡單啓發：

(defun powerset (set) 
    (cond ((null set) '(())) 
     (t (let ((powerset-of-rest (powerset (cdr set)))) 
      (append powerset-of-rest 
        (mapcar #'(lambda (x) (cons (car set) x)) 
          powerset-of-rest)))))) 

Answer 8

基於該信息here，這裏是解決方案在C＃中。

注意：主函數中的循環只是將結果輸出到控制檯值中。 PowerSet方法中沒有使用循環。

public static void Main(string[] args) 
    { 

     string input = "abbcdd"; 


     Dictionary < string, string> resultSet = new Dictionary<string, string>(); 

     PowerSet(input, "", 0, resultSet); 

     //apply sorting 
     var resultSorted = resultSet.OrderBy(l => l.Key.Length).ThenBy(l=>l.Key); 

     //print values 
     foreach(var keyValue in resultSorted) 
     { 
      Console.Write("{{{0}}}, ",keyValue.Key); 
     } 


    } 

    /// <summary> 
    /// Computes the powerset of a string recursively 
    /// based on the Algorithm http://www.ideserve.co.in/learn/generate-all-subsets-of-a-set-recursion 
    /// </summary> 
    /// <param name="input">Original input string</param> 
    /// <param name="temp">Temporary variable to store the current char for the curr call</param> 
    /// <param name="depth">The character position we are evaluating to add to the set</param> 
    /// <param name="resultSet">A hash list to store the result</param> 
    public static void PowerSet(string input, string temp, int depth, Dictionary<string, string> resultSet) 
    { 

     //base case 
     if(input.Length == depth) 
     { 
      //remove duplicate characters 
      string key = new string(temp.ToCharArray().Distinct().ToArray()); 

      //if the character/combination is already in the result, skip it 
      if (!resultSet.ContainsKey(key)) 
       resultSet.Add(key, key); 

      return;//exit 
     } 

     //left 
     PowerSet(input, temp, depth + 1, resultSet); 

     //right 
     PowerSet(input, temp + input[depth], depth + 1, resultSet); 

    }