Ask Your Question
1

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

asked 2021-12-09 19:59:21 +0200

Irfan gravatar image

updated 2021-12-11 12:51:18 +0200

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.

edit retag flag offensive close merge delete

Comments

Welcome to Ask Sage! Thank you for your question.

slelievre gravatar imageslelievre ( 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"?

John Palmieri gravatar imageJohn Palmieri ( 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....

John Palmieri gravatar imageJohn Palmieri ( 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)

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

1 Answer

Sort by ยป oldest newest most voted
1

answered 2021-12-12 00:57:15 +0200

updated 2021-12-16 04:07:34 +0200

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.

edit flag offensive delete link more

Comments

Thank you for your comment. It works.

Irfan gravatar imageIrfan ( 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.

slelievre gravatar imageslelievre ( 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....

Irfan gravatar imageIrfan ( 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]
Irfan gravatar imageIrfan ( 2021-12-15 18:36:06 +0200 )edit

What is plus?

John Palmieri gravatar imageJohn Palmieri ( 2021-12-16 03:53:03 +0200 )edit

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

Asked: 2021-12-09 19:49:56 +0200

Seen: 80 times

Last updated: Dec 16 '21