logo标签列表

递归生成幂集，无需任何循环

javaalgorithmrecursion
11

你如何编写一个递归方法PowerSet(String input)，该方法打印出传递给它的字符串的所有可能组合？

例如：PowerSet("abc")将打印出abc，ab，ac，bc，a，b，c。

我已经看到一些带有循环的递归解决方案，但在这种情况下不允许使用循环。

有什么想法吗？

编辑：所需的方法只有一个参数，即String input。

1
这个案例？哪个案例？ - Rahul
我认为有一些算法可以解决这个问题，如果你使用谷歌搜索的话。 - Matten
2
几乎每个循环都可以被递归函数所替代。 - Matten
@ R.J. 我的意思是在这种情况下，不允许使用循环。这是问题的要求。@Matten 我找到了一些，但大多数都不适合，因为它们有多个参数。 - uohzxela
你实际上有多个参数：String.getBytes(); - Dave
嗯，有趣。但是因为我不熟悉它的功能，所以我会觉得很难编写解决方案。 - uohzxela
10个回答
19

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生成ab、ac和cb

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
}

另一种方法是实现一个递归函数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就是幂集函数。否则，我们需要一个单参数无需循环的函数来将给定字符连接到给定字符串集合（显然是两个不同的东西）。
通过调用String.replace（如果要求返回String结果），或者用List代替Set（这样“额外”的参数实际上就是列表中的第一个元素）可以进行一些调整。
很棒，我确实想到了您伪代码中的算法。但是我卡在了执行这个任务上：让子字符串=不包括字符的字符串。API 中有没有内置函数可以做到这一点？ - uohzxela
1
s.substring(0,pos) 将返回从 0 到 pos-1 的子字符串，而 s.substring(pos) 将返回从 pos 到字符串的末尾的子字符串。 - Javier
我提出了另一种递归方面更好的方法，但仍需要循环。这篇文章似乎包含了答案，但我无法下载它http://dl.acm.org/citation.cfm?id=1151793 - Javier
似乎问题的要求超出了研究范畴。非常感谢提供链接。我会仔细阅读并看看能做些什么。 - uohzxela
1
@ArtemStepanenko 谢谢！我已经修正了拼写错误。关于空集，它不仅是P(abcd)的成员，也是P(abc)等集合的成员。 - Javier
显示剩余3条评论
3
这也可以解决问题：
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');
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());
1

一个由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);
}
0

简单的解决方案，但时间复杂度较差（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;
    }
}
你无法获得比2^n更好的复杂度，因为有2^n个可能的子集。 - fons
0

仅仅是为了好玩，这是一个版本，它可以对存储在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))))))
在同样的精神下，Haskell 中甚至更简单的解决方案是：powerSet = filterM (\_ -> [True, False])。 - melpomene
0

PowerSet 可以打印出所有元素的组合，例如 [123] 将形成 123、12、13、23、1、2、3。

我们可以通过使用树的概念轻松找到 Powerset 值。

每次添加或删除一个元素即可实现。

                    abc
           a                   " "
       ab     a             b       " "
  abc   ab  ac  a         bc   b   c   " "

这里首先添加了一个 "a" 和没有添加 "a"，所以树形结构中有 "a" 和 " " 两个子元素。 现在取一个常量并加上 'b'，不加 'b' 则会在同样的方式下创建另一个 'a' 的子树，我们一直添加和删除元素直到达到最后。

这里是添加元素和删除元素的方法： powerset(str,i+1,cur+str.charAt(i)); powerset(str,i+1,cur);

import java.io.*;
import java.util.*;
import java.lang.Math;

class Demo{
    
    public static void main(String args[]) {
        String str="123";
        String str1="";
        int r=0;
        powerset(str,r,str1);
        
    }
    
    public static void powerset(String str,int i,String cur){
        
        if(i==str.length()){
            
            System.out.println(cur);
            return;
            
        }
        
        powerset(str,i+1,cur+str.charAt(i));
        powerset(str,i+1,cur);
         
         
    }
    
}
0

字符串"abc"的幂集(P)包含两种类型的元素：字符'a'本身和它与P('bc')元素的组合。 同样，P('bc')包含字符'b'及其与P('c')元素的组合。 而且P('c')包含字符'c'及其与空字符串的组合。

现在创建函数powerSet(string input, string substring="")。这将打印子字符串，并表示输入字符串的第一个元素与子字符串的组合。

基本条件：当输入字符串的长度为0时，打印子字符串。

递归条件： 1). 调用powerSet(input[1:input.length()], substring) #这是用于排除0号索引字符的字符串幂集元素 2). 调用powerSet(input[1:input.length()], substring+input[0]) #这是用于组合的。

#include<iostream>
#include<string>
using namespace std;

void powerSet(string input,string substring){

    if(input.length()==0){
        cout<<substring<<", ";
        return;
    }
    string op1=substring;
    string op2=substring + input[0];    
    powerSet(input.substr(1),op1);
    powerSet(input.substr(1),op2);
    return;
}
int main(){
    string input="abc";
    powerSet(input);
}
0
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;
}
0

根据这里提供的信息，以下是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);

    }
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接