java 无任何循环地递归生成功率集
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15498281/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Generating power set recursively without any loops
提问by uohzxela
How do you write a recursive method PowerSet(String input) that prints out all possible combinations of a string that is passed to it?
您如何编写递归方法 PowerSet(String input) 来打印传递给它的字符串的所有可能组合？
For example: PowerSet("abc") will print out abc, ab, ac, bc, a, b, c
例如： PowerSet("abc") 会打印出 abc, ab, ac, bc, a, b, c
I have seen some recursive solutions with loops, but in this case no loops are allowed.
我见过一些带有循环的递归解决方案，但在这种情况下，不允许使用循环。
Any ideas?
有任何想法吗？
Edit: The required method has only one parameter, i.e. String input.
编辑：所需的方法只有一个参数，即字符串输入。
回答by Javier
The powerset of abcdis the union of the power-sets of abc, abd, acd(plus the set abcditself*).
的幂abcd为动力的集合的并集abc，abd，acd（加上集abcd本身*）。
P(`abcd`) = {`abcd`} + P(`abc`) + P(`abd`) + P(`acd`) + P(`bcd`)
* Note that the empty set, which is a member of P(abcd) is also a member of P(abc), P(abd), ... so the equivalence stated above holds.
* 请注意，作为P(abcd) 成员的空集也是 P(abc)、P(abd)、...的成员，因此上述等价成立。
Recursively, P(abc) = {abc} + P(ab) + P(ac), and so on
递归地，P( abc) = { abc} + P( ab) + P( ac)，依此类推
A first approach, in pseudocode, could be:
第一种方法，在伪代码中，可以是：
powerset(string) {
add string to set;
for each char in string {
let substring = string excluding char,
add powerset(substring) to set
}
return set;
}
The recursion ends when the string is empty (because it never enters the loop).
当字符串为空时递归结束（因为它永远不会进入循环）。
If your really want noloops, you will have to convert that loop to another recursion.
Now we want to generate ab, acand cbfrom abc
如果你真的想不循环，你将不得不到循环转换为另一种递归。现在我们要生成ab，ac并cb从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
}
Another approachimplement a recursive function Pthat either removes the first character from its argument, or does not. (Here +means set union, .means concatenation and λis the empty string)
另一种方法实现了一个递归函数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
Then
然后
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
If loops were allowed, then Pis out power-set function. Otherwise, we would need a one-parameter loopless function for concatenating a given character to a given set of strings (which obviously are twothings).
如果允许循环，则P禁用电源设置功能。否则，我们将需要一个单参数无环函数来将给定的字符连接到给定的一组字符串（这显然是两件事）。
Some tweak could be possible by playing with String.replace(if a Stringresult is desired, or by replacing Setwith List(so that the "additional" parameter is actually the first element in the list).
通过玩String.replace（如果需要String结果，或替换Set为List（以便“附加”参数实际上是列表中的第一个元素），可以进行一些调整。
回答by Nima Mehanian
This will also do the trick:
这也可以解决问题：
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');
回答by Sebastian van Wickern
Well if you don't have loops, emulate one with recursion, using iterators this is acutally quite simple.
好吧，如果您没有循环，请使用递归模拟循环，使用迭代器这实际上非常简单。
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());
回答by gontard
A recursive version of the generic solutionproposed by Jo?o Silva:
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);
}
}
I extract the recursive addSets method to transform the original forloop:
我提取递归 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);
}
回答by ron davis
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;
}
回答by sheikh sabeer
Simple solution but with poor time complexity(2^n) is as following(just keep one thing in mind once we have to avoid(i.e. 0) and once we have to take it(i.e. 1):
简单的解决方案但时间复杂度很差（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;
}
}
回答by Gene
Just for fun, a version that does powersets of any set stored in a LinkedList(to make it easy to remove the head element). Java 8 streams do the functional part:
只是为了好玩，这个版本可以对存储在 a 中的任何集合进行 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;
}
This is inspired by the following Common Lisp, which shows that the right language can make things simpler:
这受到以下 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))))))
回答by Felasfaw
Based on the info here, here is solution in C#.
基于这里的信息，这里是 C# 中的解决方案。
NOTE: the loop in the main function is just to print the result into the console value. No loops used in the PowerSet method.
注意：main 函数中的循环只是将结果打印到控制台值中。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);
}
