1#
2# This file is part of Gambit
3# Copyright (c) 1994-2016, The Gambit Project (http://www.gambit-project.org)
4#
5# FILE: src/python/gambit/enumeration.py
6# Enumeration of support profiles for a strategic game
7#
8# This program is free software; you can redistribute it and/or modify
9# it under the terms of the GNU General Public License as published by
10# the Free Software Foundation; either version 2 of the License, or
11# (at your option) any later version.
12#
13# This program is distributed in the hope that it will be useful,
14# but WITHOUT ANY WARRANTY; without even the implied warranty of
15# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16# GNU General Public License for more details.
17#
18# You should have received a copy of the GNU General Public License
19# along with this program; if not, write to the Free Software
20# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
21#
22
23class SupportEnumeration(object):
24    def enumerate_supports(self, game):
25        return self.admissible_supports(game.support_profile(), list(game.strategies))
26
27    def admissible_supports(self, profile, str_rest):
28        # Passo 1: closure
29        while True:
30            temp_profile = profile.undominated(True, True)
31            if temp_profile == profile:
32                break
33            profile = temp_profile
34
35        # Step 2: y' and z'
36        new_rest = filter(lambda x: x in list(profile), str_rest)
37
38        # Step 3: return x if z' is empty
39        if not new_rest:
40            yield profile
41
42        # Step 4: recursive step if z' isn't empty
43        else:
44            elem = new_rest.pop()
45
46            for gen in self.admissible_supports(profile, new_rest):
47                yield gen
48
49            try:
50                new_profile = profile.remove(elem)
51            except ValueError:
52                raise StopIteration
53
54            for gen in self.admissible_supports(new_profile, new_rest):
55                yield gen
56