如何編寫一個遞歸方法PowerSet(String input),該方法輸出傳遞給它的字符串的所有可能組合?遞歸地生成沒有任何循環的功率集
例如:冪( 「ABC」)將打印出ABC,AB,AC,BC,A,B,C
我已經看到了環路一些遞歸的解決方案,但在這種情況下,沒有循環被允許。
任何想法?
編輯:所需的方法只有一個參數,即字符串輸入。
如何編寫一個遞歸方法PowerSet(String input),該方法輸出傳遞給它的字符串的所有可能組合?遞歸地生成沒有任何循環的功率集
例如:冪( 「ABC」)將打印出ABC,AB,AC,BC,A,B,C
我已經看到了環路一些遞歸的解決方案,但在這種情況下,沒有循環被允許。
任何想法?
編輯:所需的方法只有一個參數,即字符串輸入。
的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
(使「額外的」參數實際上是在列表中的第一個元素)是可能的。
太棒了,我確實想到了僞代碼中的算法。但是我陷入了執行這個任務的困境:let substring = string,不包括char。 API中是否有內置函數來執行此操作? – uohzxela 2013-03-19 12:07:15
's.substring(0,pos)'將從'0'返回到'pos-1','s.substring(pos)'將從'pos'返回字符串結尾的子串。 – Javier 2013-03-19 12:18:10
謝謝。我知道了。無論如何,我是迂腐的,因爲這個問題只提到了一個參數。你知道如何實現只有一個參數是字符串輸入的方法嗎? – uohzxela 2013-03-19 12:24:31
那麼,如果你沒有循環,用遞歸模擬一個,使用迭代器這是非常簡單的。
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());
甲遞歸版本提出的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);
}
這也將這樣的伎倆:
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');
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;
}
簡單的解決方案,但與窮人的時間複雜度(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 2016-07-05 23:21:11
是的,那是真的 – 2016-08-06 01:59:40
只是爲了好玩,那不存儲在任何一組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))))))
基於該信息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);
}
這種情況?這種情況下? – SudoRahul 2013-03-19 11:31:48
我認爲那裏有**一些**算法可以解決這個問題,萬一你會使用谷歌找到一個。 – Matten 2013-03-19 11:35:53
幾乎每個循環都可以用遞歸函數替換。 – Matten 2013-03-19 11:36:45