14
1
quintopia has posted here a challenge to compute multinomial coefficients (some of the text here is copied from there). There is a fun algorithm to compute multinomial coefficients mod 2.
Given a list of numbers, k1, k2, ... ,km, output the residue of the multinomial coefficient:
reduced mod 2. The following algorithm does this efficiently: for each ki, compute the binary expansion of ki, that is, find aij such that each aij is either 1 or 0 and
If there is any j such that arj = asj = 1 for r ≠ s, then the associated mod 2 multinomial coefficient is 0, otherwise the mod 2 multinomial coefficient is 1.
Task
Write a program or function which takes m numbers, k1, k2, ... ,km, and outputs or returns the corresponding multinomial coefficient. Your program may optionally take m as an additional argument if need be.
These numbers may be input in any format one likes, for instance grouped into lists or encoded in unary, or anything else, as long as the actual computation of the multinomial coefficient is performed by your code, and not the encoding process.
Output can be any truthy value if the multinomial coefficient is odd and any falsey value if the multinomial coefficient is even.
Built-ins designed to compute the multinomial coefficient are not allowed.
Standard loopholes apply.
Scoring
This is code golf: Shortest solution in bytes wins.
Examples:
To find the multinomial coefficient of 7, 16, and 1000, we binary expand each of them:
Since no column has more than one 1, the multinomial coefficient is odd, and hence we should output something truthy.
To find the multinomial coefficient of 7, 16, and 76, we binary expand each of them:
Since both 76 and 7 have a 4 in their binary expansion, the multinomial coefficient is even and so we output a falsey value.
Test cases:
Input: [2, 0, 1]
Output: Truthy
Input: [5,4,3,2,1]
Output: Falsey
Input: [1,2,4,8,16]
Output: Truthy
Input: [7,16,76]
Output: Falsey
Input: [7,16,1000]
Output: Truthy
Input: [545, 1044, 266, 2240]
Output: Truthy
Input: [1282, 2068, 137, 584]
Output: Falsey
Input: [274728976, 546308480, 67272744, 135004166, 16790592, 33636865]
Output: Truthy
Input: [134285315, 33849872, 553780288, 544928, 4202764, 345243648]
Output: Falsey
1Welcome to PPCG! Nice first post! – Rɪᴋᴇʀ – 2018-01-17T20:57:09.213
I think several languages with
==
for equality could have saved a byte if truthy and falsey were allowed to be flipped. – Ørjan Johansen – 2018-01-18T08:44:01.143@ØrjanJohansen That sounds fine. – Hood – 2018-01-19T04:59:23.253