1
$\begingroup$

I am wondering if it is possible to take the binary strings of length $3$ (tuples) whose sums have weight $2$ (i.e they have $2$ non-zero entries)(binary case, meaning they have two $1$'s entries) $$u \in \text{tuples}$$ $$v \in \text{tuples}$$ $$u + v \in \text{tuples of weight } 2$$ and then recover which original strings ($u,v$) summed together to give a vector of weight $2$?

The following code takes all the possible binary strings of length $3$ (tuples) and then adds every string to every other string (filter). I do this in order to find the positions in which those strings differ (because they are binary strings, a 1 in position i means that both strings differed in the $i^{th}$ position).

I then use the If[] function to see which resulting vectors from the filter have weight $2$.

However, what I would like to do would be to find a way to "reverse" this process and figure out which of the original tuples added together to give these vectors of weight 2 (two non-zero entries).

I'm not quite sure how to go about this. If anyone had any ideas, that would be great!

tuples=Tuples[{0,1},3]
filter=Flatten[Outer[Mod[Plus[##], 2] &, tuples, tuples, 1], 1]
distance2=If[Total[#] == 2, #, Nothing] & /@ filter
$\endgroup$
2
  • 1
    $\begingroup$ Try Select[filter, Total[#] == 2 &] which gives the same result distance2 $\endgroup$ Commented Sep 26, 2023 at 10:32
  • $\begingroup$ That is certainly a cleaner way to get distance2, thanks $\endgroup$
    – am567
    Commented Sep 26, 2023 at 11:37

2 Answers 2

2
$\begingroup$

Here is a solution that does not create all tuples, it only creates valid tuples.

Note that to get a digits of 0 in the result, the digits in the 2 initial lists must either be both 0 or both 1.

To get a digit of 1, the initial digits must be either 1,0 or 0,1.

With this we may create a function that takes a result list and returns pairs of possible initial lists.

getinitial[in_]:= Module[{t},
  t= in /. {0 -> {{1, 1}, {0, 0}}, 1 -> {{1, 0}, {0, 1}}};
  t = Flatten[Outer[Transpose[{#1, #2, #3}] &, Sequence @@ t, 1], 2]
]

We can apply this function on the possible result lists: {0,1,1},{1,0,1},{1,1,0}:

getinitial /@ {{0, 1, 1}, {1, 0, 1}, {1, 1, 0}} // MatrixForm

enter image description here

$\endgroup$
2
$\begingroup$

It looks like $u+v$ is just BitXor[u,v] here, and since BitXor is its own inverse another possibility is:

sumPoss = Permutations[{1, 1, 0}] // Reverse;
tups = Tuples[{1, 0}, 3];
Outer[Join[{#2, BitXor[#1, #2]}] &, sumPoss, tups, 1] // MatrixForm

I reversed the output of Permutations to match @DanielHuber's matrix output:

Mathematica graphics

I do explicitly create all the {0,1} 3-tuples, so this may be bad.

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