Pigeonnier

Bonjour,

Je n'arrive pas à faire un projet en python, je ne comprend absolument rien au consigne et je suis très nul en informatique j'aimerai une aide si cela est possible, le code à compléter et si joint, il faut respecter des contraintes de cardinalité pour que n pigeon soit dans p pigeonnier.


SATISFIED = 1
UNSATISFIED = 0
NOT_EVALUABLE = 2

"""
PURPOSE

Define a cardinality constraint of the form
#(alpha, beta, L)
which is satisfied if at least alpha and
at most beta literal of L are set to true

PARAMETERS

- alpha : minimum of literals that should be true
- beta : maximum of literals that should be true
- variables_index : list of the indices of variables

"""
class CardinalityConstraint(object):

"""
Constructor
"""
def __init__(self, alpha, beta, variables_index):
self.alpha = alpha
self.beta = beta
self.variables_index = variables_index

"""
return
- NOT_EVALUABLE if at least one variable
is not assigned true (1) or false (0)
- SATISIFIED if all variables are assigned
a value and that the number of variables
set to true is in [alpha,beta]
- UNSATISIFIED if all variables are assigned
a value and that the number of variables
set to true is not in [alpha, beta]
"""
def is_satisfied(self, p_variables):

#
# you need to implement this
#


import cardinality_constraint as cc

"""
Class used to represent the Pigeon Hole Problem
for N pigeons and P pigeonholes

We then have
- N*P variables
- N cardinality constraints of type #(1,1)
- P cardinality constraints of type #(0,1)

Variables are set to
- 0 for false
- 1 for true
- 2 if not assigned

"""
class PigeonHoleProblem(object):

"""
Constructor given the number of pigeons (N)
and the number of pigeonholes (P)
"""
def __init__(self, N, P):
self.N = N
self.P = P
self.l_variables = []
for i in range(N*P):
self.l_variables.append(2)

self.l_constraints = []
# constraint on lines (pigeons)
for i in range(N):
l_index = [ i*P+j for j in range(P) ]
self.l_constraints.append( cc.CardinalityConstraint(1, 1, l_index) )
# constraints on columns (holes)
for j in range(P):
l_index = [ i*P+j for i in range(N) ]
self.l_constraints.append( cc.CardinalityConstraint(0, 1, l_index) )

"""
Check if all constraints are satisfied and return
- cardinality_constraint.SATISFIED
if all constraints are satisfied
- cardinality_constraint.UNSATISFIED
if at least one constraint is not satisfied
- cardinality_constraint.NOT_EVALUABLE
if at least one constraint is not evaluable
because if contains variables which are
not assigned the value true (1) or false (0)
"""
def constraints_are_satisfied(self, l_v, l_c):
#
# you need to implement this
#


"""
Print a solution as a matrix of N rows
and P columns given a list of variables
"""
def print_solution(self, l_v):
#
# you need to implement this
#

"""
Method that recursively solves the problem
by trying to assign the value true (1) or false (0)
to the current variable and then passes to the next
variable is there is no unsatisfied constraint.
When all variables are assigned a value then we
check if it is a solution.
"""
def _solve_(self, l_v, l_c, index):
#
# you need to implement this
#

"""
Main method that must be called to solve the Pigeon Hole
Problem. This method will print the number of solutions
found at the end.
This method calls the _solve_ method that recursively
looks for a solution
"""
def solve(self):
self.nbr_solutions = 0
self._solve_(self.l_variables, self.l_constraints, 0)
print("nbr_solutions=", self.nbr_solutions)



Il faut trouver les méthode où il y a écris "you need to implémenta this",

Merci d'avance pour votre aide,

Cordialement