无需任何循环即可递归生成功率集
你如何编写一个递归方法PowerSet（字符串输入）打印出传递给它的字符串的所有可能组合？
例如：PowerSet（“abc”）将打印出abc，ab，ac，bc，a，b，c
我已经看到了一些带循环的递归解决方案，但在这种情况下不允许循环。
有任何想法吗？
编辑：所需方法只有一个参数，即字符串输入。
abcd的powerset是abc ， abd ， acd （加上set 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
另一种方法实现递归函数P ，该函数P从其参数中移除第一个字符，或者不移除。 （这里+表示设置联合， .表示连接， λ表示空字符串）
P(abcd) = P(bcd) + aP(bcd) P(bcd) = P(cd) + bP(cd) P(cd) = P(d) + cP(d) P(d) = λ+d //particular case
然后
P(d) = λ+d R(cd) = P(d) + cP(d) = λ + d + c.(λ+d) = λ + d + c + cd R(bcd) = P(cd) + bP(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退出功率设置function。 否则，我们需要一个单参数无循环函数来将给定字符连接到给定的字符串集（显然这是两件事）。
通过使用String.replace可以实现一些调整（如果需要String结果，或者通过将List替换为List （以便“附加”参数实际上是列表中的第一个元素）。
好吧，如果你没有循环，使用递归模拟一个循环，使用迭代器这非常简单。
public final Set> powerSet(Set set) { Set> powerSet = new HashSet<>(); powerSet(set, powerSet, set.iterator()); return powerSet; } public final void powerSet(Set set, Set> powerSet, Iterator iterator) { if(iterator.hasNext()) { Integer exlude = iterator.next(); Set powThis = new HashSet (); powThis.addAll(set); powThis.remove(exlude); powerSet.add(powThis); powerSet(powThis, powerSet, powThis.iterator()); powerSet(set, powerSet, iterator); } } //usage Set set = new HashSet<>(); set.add(1); set.add(2); set.add(3); set.add(4); log.error(powerSet(set).toString());
这也可以解决问题：
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');
JoãoSilva提出的通用解决方案的递归版本：
public static Set> powerSet2(Set originalSet) { Set> sets = new HashSet>(); if (originalSet.isEmpty()) { sets.add(new HashSet ()); return sets; } List list = new ArrayList (originalSet); T head = list.get(0); Set rest = new HashSet (list.subList(1, list.size())); addSets(sets, powerSet(rest), head); return sets; } private static void addSets(Set> sets, Set> setsToAdd, T head) { Iterator> iterator = setsToAdd.iterator(); if (iterator.hasNext()) { Set set = iterator.next(); iterator.remove(); Set newSet = new HashSet (); newSet.add(head); newSet.addAll(set); sets.add(newSet); sets.add(set); addSets(sets, setsToAdd, head); } }
我提取递归的addSets方法来转换原始for循环：
for (Set set : powerSet(rest)) { Set newSet = new HashSet (); newSet.add(head); newSet.addAll(set); sets.add(newSet); sets.add(set); }
void powerSet(int * ar, int *temp, int n, int level,int index) { if(index==n) return; int i,j; for(i=index;i
简单的解决方案，但时间复杂度较差（2 ^ n）如下（一旦我们必须避免（即0）和一旦我们必须采取它（即1），请记住一件事：
public HashSet powerSet(int n) { return calcPowerSet(n-1, new HashSet(), new int[n]); } private HashSet calcPowerSet(int n, HashSet 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; } }
只是为了好玩，这是一个版本，它可以存储在LinkedList的任何集合的powersets（以便于删除head元素）。 Java 8流做function部分：
static LinkedList> powerset(LinkedList elements) { if (elements.isEmpty()) return copyWithAddedElement(new LinkedList<>(), new LinkedList<>()); T first = elements.pop(); LinkedList> powersetOfRest = powerset(elements); return Stream.concat( powersetOfRest.stream(), powersetOfRest.stream().map(list -> copyWithAddedElement(list, first))) .collect(Collectors.toCollection(LinkedList::new)); } static LinkedList copyWithAddedElement(LinkedList 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))))))
根据这里的信息，这里是C＃的解决方案。
注意：main函数中的循环只是将结果打印到控制台值中。 PowerSet方法中没有使用循环。
public static void Main(string[] args) { string input = "abbcdd"; Dictionary < string, string> resultSet = new Dictionary(); 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); } } /// /// Computes the powerset of a string recursively /// based on the Algorithm http://www.ideserve.co.in/learn/generate-all-subsets-of-a-set-recursion /// /// Original input string /// Temporary variable to store the current char for the curr call /// The character position we are evaluating to add to the set /// A hash list to store the result public static void PowerSet(string input, string temp, int depth, Dictionary 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); }