渡される文字列のすべての可能な組み合わせを出力する再帰メソッドPowerSet（String input）をどのように記述しますか？
例：PowerSet（ "abc"）は、abc、ab、ac、bc、a、b、cを出力します。
ループを使用した再帰的なソリューションを見てきましたが、この場合、ループは許可されていません。
何か案は？
編集：必要なメソッドには、文字列入力という1つのパラメーターしかありません。
質問する
21552 次
10 に答える
19
のべabcdき集合は、、、のべき集合（および集合自体*）のabc和集合ですabd。acdabcd
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;
}
文字列が空になると再帰は終了します（ループに入らないため）。
本当にループが必要ない場合は、そのループを別の再帰に変換する必要があります。今、私たちは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
}
別のアプローチ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は、パワーセット機能があります。それ以外の場合は、特定の文字を特定の文字列のセットに連結するための1パラメーターのループレス関数が必要になります（これは明らかに2つのことです）。
String.replace（結果が必要な場合、または（「追加」パラメーターが実際にリストの最初の要素になるように）にString置き換えることで、Set多少の調整が可能になる場合があります。List
于 2013-03-19T11:53:07.010 に答える
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');
于 2013-04-03T19:03:46.573 に答える
2
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());
于 2013-03-19T11:40:10.007 に答える
1
JoãoSilvaによって提案された一般的なソリューションの再帰バージョン：
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);
}
于 2013-03-19T12:04:55.673 に答える
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;
}
于 2014-08-30T19:04:19.650 に答える
0
単純な解決策ですが、時間計算量（2 ^ n）は次のようになります（回避する必要がある場合（つまり0）とそれを取る必要がある場合（つまり1）に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;
}
}
于 2016-03-21T01:02:09.497 に答える
0
楽しみのために、に格納されている任意のセットのべき集合を実行するバージョンLinkedList（ヘッド要素を簡単に削除できるようにするため）。Java8ストリームは機能的な部分を実行します。
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))))))
于 2016-11-29T04:03:36.353 に答える
0
ここの情報に基づいて、ここにC＃のソリューションがあります。
注：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);
}
于 2017-08-06T17:12:37.163 に答える
0
PowerSetは、要素のすべての組み合わせを出力します。たとえば、[123]は123、12、13、23、1、2、3を形成します。
ツリーの概念を使用すると、べき集合の値を簡単に見つけることができます
毎回要素を追加または削除しましょう
abc
a " "
ab a b " "
abc ab ac a bc b c " "
ここでは、最初にaを追加し、soツリーフォーム「a」と「」を追加していません。サブ要素は定数を取り、それに「b」を追加し、「b」を追加しないでください。その後、「a」の別のサブツリーが作成されます。要素utillを追加および削除するのと同じ方法で、最後に到達します。
ここでは、要素を追加し、要素を削除するメソッド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);
}
}
于 2021-08-27T12:41:11.727 に答える
0
文字列"abc"のべき集合（P）には、文字'a'自体とP（'bc'）の要素との組み合わせの2種類の要素が含まれています。同様に、P（'bc'）には、文字'b'とそのP（'c'）の要素との組み合わせが含まれます。また、P（'c'）には、文字'c'とそのnull文字列との組み合わせが含まれています。
ここで、関数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);
}
于 2021-10-11T23:24:01.367 に答える