Defining functions from a finite subset of $\mathbb{N}$ to a finite subset of $\mathbb{N}$

Defining functions from a finite subset of

$\mathbb{N}$ to a finite subset of

$\mathbb{N}$

Irfan
11 ●3

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.

Comments

Welcome to Ask Sage! Thank you for your question.

slelievre ( 3 years ago )

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

John Palmieri ( 3 years ago )

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

John Palmieri ( 3 years ago )

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)

Irfan ( 3 years ago )

add a comment

answered 3 years ago

John Palmieri

8906 ●20 ●74 ●193 http://www.math.washin...

updated 3 years ago

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:

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.

link

Comments

Thank you for your comment. It works.

Irfan ( 3 years ago )

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.

slelievre ( 3 years ago )

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

Irfan ( 3 years ago )

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]

Irfan ( 3 years ago )

What is plus?

John Palmieri ( 3 years ago )

see more comments

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Defining functions from a finite subset of $\mathbb{N}$ to a finite subset of $\mathbb{N}$

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Defining functions from a finite subset of N\mathbb{N} to a finite subset of N\mathbb{N} savecancel

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Defining functions from a finite subset of $\mathbb{N}$ to a finite subset of $\mathbb{N}$