Removing certain entries from a list of combinations

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

sgmth
31 ●2 ●8 ●16

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

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.

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

Max Alekseyev

7071 ●10 ●60 ●174

updated 2025-01-24 20:20:04 +0200

UPDATED 2025-01-24

What you ask for corresponds to (periodic) 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,list(w)*d))) for d in divisors(gcd(m,n)) for w in LyndonWords(n,m//d) if sum(w)*d==n ]
print( CMB )

Another possible solution:

def is_canonical(c):
    if c[0]: return False
    w = Word(c[i]-c[i-1] for i in range(len(c)))
    p = w.periods(True)
    if p: w = w[:p[0]]
    return w.is_lyndon()

CMB = list( filter(is_canonical, Combinations(G,m)) )
print( CMB )

edit flag offensive delete link

Comments

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

sgmth ( 2024-12-31 05:25:22 +0200 )edit

Thanks again Sir, for looking into the problem again. I'll go through once again and get back to confirm by testing with some cases

sgmth ( 2025-01-24 12:14:55 +0200 )edit

Sir, though I have not checked thoroughly with the outputs, but one error is still there. For n=8 and m=4, the first code has ten outputs and the second one has eleven. So, at least one of them has an error.

sgmth ( 2025-01-24 18:52:07 +0200 )edit

This was an issue in the second code. It should additionally required that c[0] is zero. Fixed now.

Max Alekseyev ( 2025-01-24 20:20:55 +0200 )edit

Yes Sir, thanks. Now its working fine.

sgmth ( 2025-01-25 07:07:29 +0200 )edit

add a comment

Your Answer

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

Removing certain entries from a list of combinations

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Removing certain entries from a list of combinations edit

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Removing certain entries from a list of combinations