Mod 2 Multinomial coefficients

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.

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

• Welcome to PPCG! Nice first post! Jan 17 '18 at 20:57
• I think several languages with == for equality could have saved a byte if truthy and falsey were allowed to be flipped. Jan 18 '18 at 8:44
• @ØrjanJohansen That sounds fine.
– Hood
Jan 19 '18 at 4:59

Jelly, 4 bytes

S=|/


Try it online!

Test whether the sum is equal to the bitwise-or-sum (i.e. a+b+c == a|b|c).

Python 3 2, 5543 42 bytes

lambda l:sum(l)==eval(l.replace(*',|'))


-12 bytes from Mr. Xcoder

-1 byte from Rod

Try it online!

Explanation: Checks if the sum of the numbers is equal to the bitwise-or of the numbers.

• 43 bytes: lambda l:sum(l)==eval("|".join(map(str,l))) Jan 17 '18 at 21:04
• You can reach 42 bytes switching to python2
– Rod
Jan 18 '18 at 9:57

Python 2, 37 bytes

lambda l:sum(l)==reduce(int.__or__,l)


Try it online!

Another port of pizzapants184's algorithm...

Clean, 38 bytes

import StdEnv
?l=sum l==foldr(bitor)0l


Try it online!

Yet another port.

Japt, 6 bytes

Another port of pizzapants184's & Leaky Nun's solutions.

x ¶Ur|


Test it

• Technically, pizzapants184 answered 14 seconds earlier than me... Jan 17 '18 at 21:16

JavaScript (ES6), 3735 34 bytes

Saved 2 bytes thanks to @Mr.Xcoder
Saved 1 byte thanks to @ETHproductions

Comparing the sum with the bitwise OR (like pizzapants184 and Leaky Nun did) is 1 3 4 bytes shorter than my initial approach:

a=>(q=c=>eval(a.join(c)))|==q+


Test cases

let f =

a=>(q=c=>eval(a.join(c)))|==q+

console.log(f([2, 0, 1]))                                                       // Truthy
console.log(f([5,4,3,2,1]))                                                     // Falsey
console.log(f([1,2,4,8,16]))                                                    // Truthy
console.log(f([7,16,76]))                                                       // Falsey
console.log(f([7,16,1000]))                                                     // Truthy
console.log(f([545, 1044, 266, 2240]))                                          // Truthy
console.log(f([1282, 2068, 137, 584]))                                          // Falsey
console.log(f([274728976, 546308480, 67272744, 135004166, 16790592, 33636865])) // Truthy
console.log(f([134285315, 33849872, 553780288, 544928, 4202764, 345243648]))    // Falsey

Alt. version, 38 bytes

a=>!a.some((x,i)=>a.some(y=>i--&&x&y))


Test cases

let f =

a=>!a.some((x,i)=>a.some(y=>i--&&x&y))

console.log(f([2, 0, 1]))                                                       // Truthy
console.log(f([5,4,3,2,1]))                                                     // Falsey
console.log(f([1,2,4,8,16]))                                                    // Truthy
console.log(f([7,16,76]))                                                       // Falsey
console.log(f([7,16,1000]))                                                     // Truthy
console.log(f([545, 1044, 266, 2240]))                                          // Truthy
console.log(f([1282, 2068, 137, 584]))                                          // Falsey
console.log(f([274728976, 546308480, 67272744, 135004166, 16790592, 33636865])) // Truthy
console.log(f([134285315, 33849872, 553780288, 544928, 4202764, 345243648]))    // Falsey

• Technically, pizzapants184 answered 14 seconds earlier than me... Jan 17 '18 at 21:16
• -1 byte: a=>(q=c=>eval(a.join(c)))|==q+; Jan 17 '18 at 21:36
• @ETHproductions Nice! This works fine in Node.js. But did you manage to have it working in a browser? Jan 17 '18 at 21:43
• Works fine for me in Firefox 57. Are you getting an error or is it just not working properly? Jan 17 '18 at 22:12
• @ETHproductions Actually, yes it does work. It just happens to fail on repl.it. Jan 17 '18 at 22:22

(==).sum<*>foldl1 xor is an anonymous function returning a Bool. Use as ((==).sum<*>foldl1 xor) [2,0,1].

import Data.Bits
(==).sum<*>foldl1 xor


Try it online!

• Pretty much the same trick by pizzapants184 and Leaky Nun that everyone uses, except that with Haskell operator names it saves one byte to use (bitwise) xor instead of (.|.) (bitwise or).

• (==).sum<*>foldl1 xor is a point-free version of \l->sum l==foldl1 xor l.

Java 8, 53 bytes

a->{int i=0,j=0;for(int x:a){i+=x;j|=x;}return i==j;}


Explanation:

Try it here.

a->{             // Method with integer-array parameter and boolean return-type
int i=0,j=0;   //  Two integers, both starting at 0
for(int x:a){  //  Loop over the array
i+=x;        //   Add them to the first integer
j|=x;}       //   And bitwise-OR it with the second integer
return i==j;}  //  Return if both integers are the same after the loop


Pyth, 6 bytes

qsQ.|F


Test Suite.

Husk, 5 bytes

§=ΣFv


Try it online!

Perl 6, 15 bytes

{.sum==[+|] $_}  Test it Expanded: { # bare block lambda with implicit parameter ｢$_｣

.sum  # the sum of ｢$_｣ (implicit method call) == [+|] # reduce using &infix:«+|» (numeric binary or)$_  # the input
}


Red, 78 bytes

f: func[x][b: :to-binary t: 0 s: b 0 foreach n x[t: t + n s: s or b n]s = b t]


How it works:

Ungolfed:

Red []
f: func [x][         -  a function taking a block as an argument
b: :to-binary    -  an alias for the to-binary function
t: 0             -  set the sum of the numbers to 0
s: b 0           -  set the "or" total to binary 0
foreach n x[     -  for each number in the block
t: t + n     -  add it to the sum
s: s or b n  -  bitwise or of its binary representation with the total
]
s = b t          - are the sum (binary) and the "or" total equal?
]


Try it online!

Wolfram Language (Mathematica), 15 bytes

Tr@#==BitOr@@#&


Try it online!

Batch, 73 bytes

@set/as=o=0
@for %%i in (%*)do @set/as+=%%i,o^|=%%i
@if %s%==%o% echo 1


Outputs 1 for truthy, nothing for falsy. Another obvious port of pizzapants184/Leaky Nun's algorithm.

J, 10 bytes

+/=+./&.#:


Yet another port of pizzapants184's & Leaky Nun's solutions.

How it works?

+/.&.#: - convert the numbers to binary, apply bitwise or to the powers of two and convert back from binary to decimal

+/ - reduce the input by addition

= - are the above equal?

Try it online!

J, 12 bytes

2>[:>./+/@#:


How it works?

+/@#: - convert each number to binary and find the sum of each power of 2

>./ - find the maximum

2> - is it less than 2? -> truthy

Try it online!

Triangularity, 31 bytes

...)...
..IEu..
.)IE...
"|"JE=.


Try it online!

Alternate solution, 31 bytes

...)...
..IED..
.us"|".
JE=....


Try it online!