0
$\begingroup$

I wrote a code below to determine the cases when two subsets of a set $\mathbb{Z_n}=\{0,1,2,\ldots,n-1\}$ are added together element by element (without removing the multiplicity) in $\mathbb{Z_n}$ and see if there are pairs with even in each number or not, but it takes long time to run it when the number $n$ go bigger than 10. I am asking for a faster code. In some step I used the comment of people here :) count the pairs in a set of Data.

Clear[M,A,B,n,d,f]
Z[n_]:=Table[i,{i,0,n-1}]
n=4;
p[A_,B_]:=
Union[Flatten[Table[If[SubsetQ[Z[n],A]==True&&SubsetQ[Z[n],B]==True&&
Length[A]==4&&MemberQ[A,0]==True&&MemberQ[A,a]==True&&MemberQ[B,b]==True,
Mod[a+b,n],{}],{a,A},{b,B}],0]]

f=And@@EvenQ[Values[Counts[#]]]&;
d=Union[
Flatten[Table[
Sort[Flatten[p[A,B]]],{A,Subsets[Z[n]]},{B,Subsets[Z[n]]}],1]]
g=f/@d
Sort[g]

The output for $n=4$ is

{{}, {0, 1, 2, 3}, {0, 0, 1, 1, 2, 2, 3, 3}, {0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3}, {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3}}


{True, False, True, False, True}

{False, False, True, True, True}

The True and False were explained in the previous question with quoted link above.

P.S. Let me give an example: Let n=4, and A={0,1,2,3}, B={0,1}, then A+B={0,1,2,3,1,2,3,0}, where the last 0 is 4(mod4). As we see that in the set A+B we have two 0, two 1, two 2 and two 3, therefore the final output for this set is True.

$\endgroup$

1 Answer 1

2
$\begingroup$

I'm not sure I understand exactly what you are looking for, but your example can be coded quite concisely. The Outer calculates all the direct sums, the Mod reduces back to the range 0 to n-1, and the Tally counts how many of each element occur.

a = {0, 1, 2, 3}; b = {0, 1};
tally = Tally[Mod[Outer[Plus, b, a] // Flatten, 4]]

{{0, 2}, {1, 2}, {2, 2}, {3, 2}}

You can determine whether all elements occur an even number of times using EvenQ:

EvenQ[tally[[All, 2]]]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.