From 31b2589cdfc2ff1a83fbc97d0882c493980fa14c Mon Sep 17 00:00:00 2001
From: Nao Pross <np@0hm.ch>
Date: Sun, 29 Oct 2023 17:50:14 +0100
Subject: Pass TestFiniteMakePowerSet
---
src/act4e_solutions/sets_power.py | 63 ++++++++++++++++++++++++++++++++--
src/act4e_solutions/sets_properties.py | 3 +-
2 files changed, 63 insertions(+), 3 deletions(-)
(limited to 'src')
diff --git a/src/act4e_solutions/sets_power.py b/src/act4e_solutions/sets_power.py
index 49b4b7b..98d1c69 100644
--- a/src/act4e_solutions/sets_power.py
+++ b/src/act4e_solutions/sets_power.py
@@ -1,11 +1,70 @@
-from typing import Any, overload, TypeVar
+from typing import Any, TypeVar, Iterator, Collection, List
+import itertools
+
+from .sets_representation import MyFiniteSet
+from .sets_properties import SolFiniteSetProperties
import act4e_interfaces as I
X = TypeVar("X")
+C = TypeVar("C") # Type of elements of set
+E = MyFiniteSet[C] # Type of sets
+
+
+class MyFiniteSetOfSubsets(I.FiniteSetOfFiniteSubsets[C, E]):
+ # FIXME: _set could be removed
+ _set: I.FiniteSet[C]
+ _subsets: List[I.FiniteSet[C]]
+
+ def __init__(self, theset: I.FiniteSet[C], subsets: Collection[I.FiniteSet[C]]):
+ self._set = theset
+ self._subsets = subsets
+
+ self.fsp = SolFiniteSetProperties()
+ assert(self.fsp.is_subset(s, theset) for s in subsets)
+
+ def size(self) -> int:
+ return len(self._subsets)
+
+ def contains(self, x: E):
+ # print(f"Checking whether {x.elements()} is contained in " +
+ # str(list(map(lambda l: l.elements(), self._subsets))))
+
+ # Heuristic filter to make it a bit faster
+ same_size = lambda s: s.size() == x.size()
+ for s in filter(same_size, self._subsets):
+ if self.fsp.equal(x, s):
+ # print("it is in there!")
+ return True
+
+ return False
+
+ def elements(self):
+ return self._subsets
+
+ def save(self, h: I.IOHelper, x: E) -> List[E]:
+ # FIXME: I don't think this is correct, same problem as in save
+ return cast(I.ConcreteRepr, x)
+
+ def load(self, h: I.IOHelper, o: I.ConcreteRepr):
+ # FIXME: what the f am I supposed to do here
+ return cast(E, o)
+
+ def contents(self, e: E) -> Iterator[C]:
+ return e.elements()
+
+ def construct(self, elements: Collection[C]) -> E:
+ return MyFiniteSet(elements)
+
class SolFiniteMakePowerSet(I.FiniteMakePowerSet):
def powerset(self, s: I.FiniteSet[X]) -> I.FiniteSetOfFiniteSubsets[X, Any]:
- raise NotImplementedError() # implement here
+ subsets = [MyFiniteSet([]), s]
+ for i in range(1, s.size()):
+ # generate all possible subsets with i elements
+ for comb in itertools.combinations(s.elements(), i):
+ subsets.append(MyFiniteSet(list(comb)))
+
+ return MyFiniteSetOfSubsets(s, subsets)
diff --git a/src/act4e_solutions/sets_properties.py b/src/act4e_solutions/sets_properties.py
index 2044abd..0d6b3fc 100644
--- a/src/act4e_solutions/sets_properties.py
+++ b/src/act4e_solutions/sets_properties.py
@@ -7,10 +7,11 @@ X = TypeVar("X")
class SolFiniteSetProperties(I.FiniteSetProperties):
def is_subset(self, a: I.FiniteSet[X], b: I.FiniteSet[X]) -> bool:
+ """ is a a subset of b ? """
return all([b.contains(e) for e in a.elements()])
def equal(self, a: I.FiniteSet[X], b: I.FiniteSet[X]) -> bool:
- return self.is_Subset(a, b) and self.is_subset(b, a)
+ return self.is_subset(a, b) and self.is_subset(b, a)
def is_strict_subset(self, a: I.FiniteSet[X], b: I.FiniteSet[X]) -> bool:
return self.is_subset(a, b) and not self.is_subset(b, a)
--
cgit v1.2.1