Better
Это не работает для случая 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;
}
}
}