Ask Your Question
1

Removing certain entries from a list of combinations

asked 2024-12-30 07:07:40 +0100

sgmth gravatar image

updated 2024-12-30 07:15:08 +0100

Starting with an additive group Zn (group of integers modulo n) to find all combinations of m elements, removing all translates of a combination. By a translate T+i of combination T, I mean the combinations whose elements can be expressed as a+i for each a in T , where i is a fixed non-zero in Zn .

For example if we run this

n=int(input("Enter the order of the group Zn : "))
G=Zmod(n)
m=int(input("Enter the order of the  Combination required: "))

CMB= Combinations(G,m) 
show(CMB.list())

Then for n=5 and m=3 we get the following output
𝙲𝙼𝙱=[[0,1,2],[0,1,3],[0,1,4],[0,2,3],[0,2,4],[0,3,4],[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

For example, here the translates of [0,1,2] are [1,2,3], [2,3,4],[0,3,4],[0,1,4] for i =,1,2,3,4, respectively

I want to retain only [0,1,2] and remove all its translates from the output.

edit retag flag offensive close merge delete

1 Answer

Sort by Β» oldest newest most voted
2

answered 2024-12-30 18:44:10 +0100

Max Alekseyev gravatar image

updated 2024-12-31 01:06:59 +0100

What you ask for corresponds to Lyndon words composed of the differences between consecutive elements (summing to n). Check this out:

n=4
m=3
G=Zmod(n)

import itertools
CMB = [ tuple(itertools.accumulate(map(G,w))) for w in LyndonWords(n,m) if sum(w)==n ]
print( CMB )

Another possible solution:

def is_canonical(c):
    try:
        LyndonWord(c[i]-c[i-1] for i in range(len(c)))
    except ValueError:
        return False
    return True

CMB = list( filter(is_canonical, Combinations(G,m)) )
print( CMB )
edit flag offensive delete link more

Comments

Thanks a lot Sir. Yes , they both work perfectly fine. Thanks again.

sgmth gravatar imagesgmth ( 2024-12-31 05:25:22 +0100 )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: 2024-12-30 07:07:40 +0100

Seen: 84 times

Last updated: Dec 31 '24