# 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.

edit retag close merge delete

( 2021-12-10 19:34:48 +0200 )edit
1

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"?

( 2021-12-10 23:42:12 +0200 )edit
1

The Python itertools package is good for iterating over subsets, combinations, powersets, things like that: https://docs.python.org/3/library/ite....

( 2021-12-10 23:43:24 +0200 )edit
1

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)

( 2021-12-11 12:50:20 +0200 )edit

Sort by » oldest newest most voted

A few comments: (1) don't do list(powerset(M)). Instead, just do for Q in powerset(M): if you're going to iterate over something, there is no need to turn it into a list first, and that may take time and may also require a lot of memory. for Q in powerset(M) should be faster and more memory efficient. (2) Similarly, you may be able to have Lab_Funs return an iterator, not a list: since you are going to iterate over the entries, there is no need to compute the whole list all at once. (3) Also, please look at itertools to see what it provides.

Edit:

Minor simplification: change

IT=iter(powerset(M))
LIS=[];
for g in IT:


to

LIS=[];
for g in powerset(M):


More significant change: replace Lab_Funs by an iterator: don't compute the whole thing at once:

class Lab_Funs_iter:
def __init__(self, M):
self.M = M

def __iter__(self):
self.powerset = powerset(M)
return self

def __next__(self):
g = self.powerset.__next__()
M = self.M
F = []
for s in range(len(M)):
if M[s] in g:
F=F+[(M[s],1)];
else:
F=F+[(M[s],0)]
return F


Then do for f in Lab_Funs_iter(M): Do an internet search for "python iterator" to find more about Python iterators. I don't know what problems you're having and I can't test your code because I don't know what plus is supposed to do.

more

Thank you for your comment. It works.

( 2021-12-13 19:13:12 +0200 )edit

I turned John's comment into an answer. You can accept it (accept button at top left of answer) to mark your question as solved.

( 2021-12-14 16:55:38 +0200 )edit

Sorry John. It's working for comparatively small numbers. I am writing my edited code. Can you point out please where is the problem?

 from itertools import chain
def Lab_Funs(M):
IT=iter(powerset(M))
LIS=[];
for g in IT:
F=[];
for s in range(len(M)):
if M[s] in g:
F=F+[(M[s],1)];
else:
F=F+[(M[s],0)]
LIS=chain(LIS,[F])
print(type(LIS))
return(LIS)


And the next part is....

( 2021-12-15 18:27:46 +0200 )edit

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=chain(RLF,[f]) print(type(RLF)) return(RLF)

I am trying to find

Req_Lab_Funs(S,[1..10])


For

M=[1..10]

( 2021-12-15 18:36:06 +0200 )edit

What is plus?

( 2021-12-16 03:53:03 +0200 )edit