Defining functions from a finite subset of $\mathbb{N}$ to a finite subset of $\mathbb{N}$
I want to define all functions from a finite subset (which is closed under addition) of $\mathbb{N}$ to another finite subset of $\mathbb{N}$ (target set is {0,1} in my case) with some special properties e.g. f
is in my collection if and only if f
is additive. I came across this type of problem as a part of my research. (e.g. the set of ways we can color a finite graph with finite set of colors where is the set of vertices we have a binary operation). Of course theoretically we can do it by considering power sets (considering all elements which are mapped to 1) which is not helpful while programming is Sage. Later I have to run my program over this collection to reach the destination.
I tried with the following code which isn't helpful when the number of vertices is little large.
def Lab_Funs(M):
P = list(powerset(M))
l = len(P)
F = list(var('F_%d' % i) for i in range(l))
for i in range(l):
Q = P[i]
F[i] = []
for s in range(len(M)):
if M[s] in Q:
F[i] = F[i] + [(M[s], 1)]
else:
F[i] = F[i] + [(M[s], 0)]
return [F[i] for i in range(l)]
def Req_Lab_Funs(M, y):
RLF = []
for f in Lab_Funs(M):
k = 1
for s in range(len(M)):
for p in range(len(M)):
if plus(f[s][0], f[p][0])[1] == 1:
N = plus(f[s][0], f[p][0])[0]
r = M.index(N)
if f[s][1] + f[p][1] != f[r][1]:
k = 0
if k > 0:
L = [f[r][0] for r in range(len(M))]
t = L.index(y)
if f[t][1] == 1:
RLF = RLF + [f]
return RLF
Lab_Funs: Labeling functions Req_Lab_Funs: Required Labeling functions.
Any suggestion or help is highly appreciated.
Thank you for your help in advance.
Welcome to Ask Sage! Thank you for your question.
If N is the set of non-negative integers, the only nonempty finite subset of N which is closed under addition is {0}. So what do you mean by "addition"?
The Python itertools package is good for iterating over subsets, combinations, powersets, things like that: https://docs.python.org/3/library/ite....
I am sorry. I meant that we have some '+' on the finite set with the property that when we can add two elements then the resulting addition must be in that set. The addition is not over the full set. E.g. we have a graph with 10 vertices with a coloring ( may not be proper) by 0 and 1. Suppose we can add 'a' and 'b' where both 'a' and 'b' are not colored with '1'. Then it must have the property color(a)+color(b)=color(a+b)