diff options
| -rw-r--r-- | Homeworks.md | 4 | ||||
| -rw-r--r-- | src/act4e_solutions/sets_power.py | 63 | ||||
| -rw-r--r-- | src/act4e_solutions/sets_properties.py | 3 |
3 files changed, 65 insertions, 5 deletions
diff --git a/Homeworks.md b/Homeworks.md index fc0c091..e74ac23 100644 --- a/Homeworks.md +++ b/Homeworks.md @@ -12,8 +12,8 @@ $ make docker-check - [X] TestFiniteSetRepresentation - [X] TestFiniteSetProperties -- [?] TestFiniteMakePowerSet - [X] TestFiniteMakeSetProduct +- [X] TestFiniteMakePowerSet - [X] TestFiniteSetRepresentationProduct - [?] TestFiniteMakeSetDisjointUnion @@ -36,7 +36,7 @@ $ make docker-check - [X] TestFiniteSemigroupMorphismRepresentation - [X] TestFiniteMonoidMorphismRepresentation - [X] TestFiniteGroupMorphismRepresentation -- [ ] TestFiniteSemigroupMorphismsChecks +- [X] TestFiniteSemigroupMorphismsChecks - [ ] TestFinitePosetRepresentation - [ ] TestFinitePosetConstructionPower 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) |