递归地生成没有任何循环的功率集

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

    }