我现在遇到了一个问题,需要从给定的N元素集合中找到所有的k元素子集。我知道使用公式C(n,k)=C(n-1, k-1)+C(n-1, k)可以计算总共有多少个k元素子集,也有一些迭代方式可以实现,但是当我尝试想出一个递归解决方案时就卡住了。有人能给我一些提示吗? 谢谢!
我现在遇到了一个问题,需要从给定的N元素集合中找到所有的k元素子集。我知道使用公式C(n,k)=C(n-1, k-1)+C(n-1, k)可以计算总共有多少个k元素子集,也有一些迭代方式可以实现,但是当我尝试想出一个递归解决方案时就卡住了。有人能给我一些提示吗? 谢谢!
更好的
对于k=0
的情况,这段代码存在问题,因为它可能返回一个包含空集的集合,这并不正确。总的来说,在这里有一个迭代过程,如果目标是完全递归,那么你可能可以用递归来替换它。这是根据wikipedia: powerset中给出的算法进行的相当简单的修改。我将把修复特殊情况(k=0)留给读者。
这段代码并没有正确尾递归,大多数JVM都不会受到影响。(我猜IBM JVM也是如此...)
class RecursivePowerKSet
{
static public <E> Set<Set<E>> computeKPowerSet(final Set<E> source, final int k)
{
if (k==0 || source.size() < k) {
Set<Set<E>> set = new HashSet<Set<E>>();
set.add(Collections.EMPTY_SET);
return set;
}
if (source.size() == k) {
Set<Set<E>> set = new HashSet<Set<E>>();
set.add(source);
return set;
}
Set<Set<E>> toReturn = new HashSet<Set<E>>();
// distinguish an element
for(E element : source) {
// compute source - element
Set<E> relativeComplement = new HashSet<E>(source);
relativeComplement.remove(element);
// add the powerset of the complement
Set<Set<E>> completementPowerSet = computeKPowerSet(relativeComplement,k-1);
toReturn.addAll(withElement(completementPowerSet,element));
}
return toReturn;
}
/** Given a set of sets S_i and element k, return the set of sets {S_i U {k}} */
static private <E> Set<Set<E>> withElement(final Set<Set<E>> source, E element)
{
Set<Set<E>> toReturn = new HashSet<Set<E>>();
for (Set<E> setElement : source) {
Set<E> withElementSet = new HashSet<E>(setElement);
withElementSet.add(element);
toReturn.add(withElementSet);
}
return toReturn;
}
public static void main(String[] args)
{
Set<String> source = new HashSet<String>();
source.add("one");
source.add("two");
source.add("three");
source.add("four");
source.add("five");
Set<Set<String>> powerset = computeKPowerSet(source,3);
for (Set<String> set : powerset) {
for (String item : set) {
System.out.print(item+" ");
}
System.out.println();
}
}
}
仅限幂集 这可能不太完美,也不是很优雅,但它可以通过递归计算完整的幂集,然后迭代地对其进行大小调整。
class RecursivePowerSet
{
static public <E> Set<Set<E>> computeConstrainedSets(final Set<Set<E>> source, final SizeConstraint<Set<E>> constraint)
{
Set<Set<E>> constrained = new HashSet<Set<E>>();
for (Set<E> candidate : source) {
if (constraint.meetsConstraint(candidate)) {
constrained.add(candidate);
}
}
return constrained;
}
static public <E> Set<Set<E>> computePowerSet(final Set<E> source)
{
if (source.isEmpty()) {
Set<Set<E>> setOfEmptySet = new HashSet<Set<E>>();
setOfEmptySet.add(Collections.EMPTY_SET);
return setOfEmptySet;
}
Set<Set<E>> toReturn = new HashSet<Set<E>>();
// distinguish an element
E element = source.iterator().next();
// compute source - element
Set<E> relativeComplement = new HashSet<E>(source);
relativeComplement.remove(element);
// add the powerset of the complement
Set<Set<E>> completementPowerSet = computePowerSet(relativeComplement);
toReturn.addAll(completementPowerSet);
toReturn.addAll(withElement(completementPowerSet,element));
return toReturn;
}
static private <E> Set<Set<E>> withElement(final Set<Set<E>> source, E element)
{
Set<Set<E>> toReturn = new HashSet<Set<E>>();
for (Set<E> setElement : source) {
Set<E> withElementSet = new HashSet<E>(setElement);
withElementSet.add(element);
toReturn.add(withElementSet);
}
return toReturn;
}
public static void main(String[] args)
{
Set<String> source = new HashSet<String>();
source.add("one");
source.add("two");
source.add("three");
source.add("four");
source.add("five");
SizeConstraint<Set<String>> constraint = new SizeConstraint<Set<String>>(3);
Set<Set<String>> powerset = computePowerSet(source);
Set<Set<String>> constrained = computeConstrainedSets(powerset, constraint);
for (Set<String> set : constrained) {
for (String item : set) {
System.out.print(item+" ");
}
System.out.println();
}
}
static class SizeConstraint<V extends Set> {
final int size;
public SizeConstraint(final int size)
{
this.size = size;
}
public boolean meetsConstraint(V set)
{
return set.size() == size;
}
}
}
list * subsets(string s, list * v){
if(s.length() == 1){
list.add(s);
return v;
}
else
{
list * temp = subsets(s[1 to length-1], v);
int length = temp->size();
for(int i=0;i<length;i++){
temp.add(s[0]+temp[i]);
}
list.add(s[0]);
return temp;
}
}