Linear dependences over the field with two elements

Question

The \$d\$-dimensional vector space \$\mathbb{F}_2^d\$ over the field with two elements \$\mathbb{F}_2\$ is the set of vectors of \$d\$ bits. Addition of vectors is bitwise xor. A linear dependence is a set of vectors whose total (xor them all together) is \0ドル\$. Every set of \$d+1\$ vectors in \$\mathbb{F}_2^d\$ contains a linear dependence. We will represent the elements of \$\mathbb{F}_2^d\$ as the integers \0ドル\$ through \2ドル^{d}-1\$ using the binary expansion.

Task

Input: a positive integer \$d\$ and a list of \$d+1\$ positive integers between \1ドル\$ and \2ドル^{d}-1\$. You may assume that the list is sorted and you may assume that the entries are distinct.

Output: A nonempty subset of the \$d+1\$ numbers whose bitwise xor is zero.

Scoring:

This is code golf so shortest answer in bytes wins.

Examples:

Input: (3, [1,3,4,7])
Output: [3, 4, 7]

In binary, these are 001, 011, 100, and 111. We see that 100 xor 011 xor 111 = 000. In this case this is the only solution, so we must output [3, 4, 7].

Test cases:

Input: (3, [1,3,4,7])
Output: [3, 4, 7]
Input: (4, [1, 2, 6, 10, 30])
Output: Behavior undetermined because 30 > 15 = 2^4 - 1.
Input: (5, [3, 5, 6, 9, 14])
Output: [3, 5, 6]
Input: (5, [4, 8, 10, 12, 14])
Output: [4, 8, 12] or [4, 10, 14], or [8, 10, 12, 14].
Input: (6, [4, 15, 17, 21, 49, 51, 57])
Output: [4, 17, 21]
Input: (6, [1, 7, 8, 15, 39, 55, 57]) 
Output: [7, 8, 15] or [1, 15, 55, 57] or [1, 7, 8, 55, 57]
Input: (6, [13, 14, 24, 33, 35, 36, 63]) 
Output: [13, 14, 24, 36, 63]
Input: (6, [10, 11, 25, 28, 40, 59, 62])
Output: [10, 25, 40, 59] or [10, 28, 40, 62], or [25, 28, 59, 62]
Input: (6, [1, 3, 5, 11, 19, 32, 63])
Output: [1, 3, 5, 11, 19, 32, 63]

• Arnauld: May we return all solutions?
• Arnauld: You may want to clarify that the empty set is not an acceptable solution.
• user555045: Must the answer be a list of the entries, can it be a bitmask with the ith bit set iff item[i] is in the set?
• Hood: @harold Yes, the bitmask sounds fine to me.
• xnor: May we assume the entries are distinct?

Answer 1

Jelly, 7 bytes

ŒPḊ^/ÞḢ

A monadic Link accepting the list of distinct integers representing the vectors which yields a subset representing the linear dependence. (May be employed as a dyadic Link also accepting the number of dimensions on the right.)

Try it online!

How?

ŒPḊ^/ÞḢ - Link: list of distinct integers e.g. [1,3,4,7]
ŒP - power-set [[],[1],[3],[4],[7],[1,3],[1,4],[1,7],[3,4],[3,7],[4,7],[1,3,4],[1,3,7],[1,4,7],[3,4,7],[1,3,4,7]],[3,4,7],[1,3,4,7]]
 Ḋ - dequeue [[1],[3],[4],[7],[1,3],[1,4],[1,7],[3,4],[3,7],[4,7],[1,3,4],[1,3,7],[1,4,7],[3,4,7],[1,3,4,7]],[3,4,7],[1,3,4,7]]
 Þ - sort by:
 / - reduce by:
 ^ - XOR ( [1,3,4,7,2,5,6,7,4,3,6,5,2,0,1] )
 - } [[3,4,7],[1],[1,3,4,7],[1,3],[1,4,7],[3],[4,7],[4],[3,7],[1,4],[1,3,7],[1,7],[1,3,4],7,[3,4]]
 Ḣ - head [3,4,7]

Answer 2

Perl 6, 39 bytes

{first {![+^] $_},.combinations(1..$_)}

Try it online!

Returns the first combination of the input that is zero when reduced XOR. I wish {![+^] $_} could be changed to !*.&[+^].

Answer 3

Pyth, 6 bytes

hxFDty

Try it online!

To explain, back to front:

• y generates all subsets of the input.

• t (tail) removes the first, empty subset.

• D means order by the following function:

• F means reduce on:

• x is the xor function.

• h (head) takes the first element of the sorted list.

The lists that xor to 0 will be sorted to the front.

Answer 4

05AB1E, 8 bytes

æ¦.Δ.»^>

Try it online!

How?

æ¦.Δ.»^> - implicitly take input
æ - power-set
 ¦ - tail
 .Δ - keep first which is 1 under:
 .» - reduce by:
 ^ - XOR
 > - increment
 - implicit print

Answer 5

Python 3.8, 74 bytes

f=lambda a,s=[],v=0:s*(v<1)or a and(f(n:=a[1:],s+a[:1],v^a[0])or f(n,s,v))

Try it online!

Answer 6

Haskell, 79 bytes

import Data.Bits
p[a]=[[a]]
p(a:b)=map(a:)(p b)++p b
filter((1>).foldl xor 0).p

Try it online!

Defines the power set (ignoring the empty set) as p, then our solution is:

filter((1>).foldl xor 0).p

Or in english:

Get the power set and then select all the members whose xor sum is less than 1 (i.e. zero).

Answer 7

JavaScript (ES6), (削除) 84 60 (削除ここまで) 58 bytes

Ignores \$d\$. Returns \0ドル\$ if there's no solution.

f=([v,...a],x,o=[])=>x<1?o:v?f(a,x,o)||f(a,x^v,[...o,v]):0

Try it online!

Commented

f = ( // f is a recursive function taking:
 [v, // v = next value from the input set
 ...a], // a[] = array of remaining values
 x, // x = 'XOR total', initially undefined
 o = [] // o[] = output subset
) => //
 x < 1 ? // if x is defined and equal to 0:
 o // success: return o[]
 : // else:
 v ? // if v is defined:
 f(a, x, o) || // try a recursive call where v is ignored
 f(a, x ^ v, [...o, v]) // try a recursive call where v is used
 : // else:
 0 // failed

Answer 8

Ruby, 78 bytes

f=->a{(1..a.size).map{|x|a.combination(x).map{|x|return x if x.reduce(:^)<1}}}

Try it online!

:^)

Probably golfable.

• Value Ink: 74 bytes: replaced the return with a find/compact structure, and then cheesed out the reduce with an eval.

Answer 9

J, 36 bytes

0-.~1{ ::0[:(#~0=XOR/"1)]#~2#:@i.@^#

Try it online!

Answer 10

Mathematica, 61 bytes

f[d_,l_]:=NullSpace[IntegerDigits[#,2,d]&/@l,Modulus->2][[1]]

This gives a bitmask (well a list of zeros and ones) of which elements of the list are in the set, as was allowed by the OP.

Answer 11

Mathematica, 38 bytes

Select[Rest@Subsets@#,BitXor@@#==0&]&

Returns the list of solutions or an empty list if no solutions exist.

Try it online!

Answer 12

x86 machine code, 27 bytes

578B7C240831C04031D231C90FA3C8730333148F67E2F575EE5FC3

Iterating through bit masks and XORing together the items as selected by the mask. In MASM-format assembly:

_lindep PROC
 push edi
 mov edi, [esp + 8]
 xor eax, eax
_loop:
 inc eax
 xor edx, edx
 xor ecx, ecx
_inner:
 bt eax, ecx
 jnc _skip
 xor edx, [edi + 4 * ecx]
_skip:
 byte 67h
 loop _inner
 jnz _loop
 pop edi
 ret
_lindep ENDP

It's a cdecl function, not stdcall.

There is an odd requirement: the input array must be padded to 65536 items long, but only 32 items are actually used. That's because I used a 16-bit loop and relied it on it wrapping from 0 to 65535, The padding has to exist in order to make the program not die with an access violation.

Using loop this way, in addition to gaining the benefit from it being small, means the zero flag is not modified between the xor and the jnz of the outer loop. Almost any other construct would need an extra instruction just to re-test whether edx is zero, except using lea to increment the loop counter and bt ecx, 5 to stop when it hits 32, which is bigger.

Driver program in case you want to run it:

#include <iostream>
extern "C" int lindep(int* vecs, int d);
int vecs[65536] = { 1, 3, 4, 7 };
int main()
{
 std::cout << lindep(vecs, 3) << "\n";
}

• qwr: why are only 32 items used? and the requirement to pad the input array is stretching the I/O rules too far IMO.
• user555045: @qwr the bitmask only has 32 bits in it so more than that doesn't work.

Answer 13

Charcoal, 32 bytes

IΦEX2LθΦθ%÷ιX2μ2∧ι⬤↨⌈θ2¬%Σ÷ιX2μ2

Try it online! Link is to verbose version of code. Outputs all matches. Explanation:

 2 Literal 2
 X Raised to power
 θ Input array
 L Length
 E Map over implicit range
 θ Input array
 Φ Filtered where nonzero
 ι Outer index
 ÷ Integer divide by
 2 Literal 2
 X Raised to power
 μ Inner index
 % Modulo
 2 Literal 2
 Φ Filter powerset where
 ι Current subset (is not empty)
 ∧ Logical And
 θ Input array
 ⌈ Maximum
 ↨ Convert to base
 2 Literal 2
 ⬤ Has all values where
 ι Current powerset
 ÷ Vectorised integer divide by
 2 Literal 2
 X Raised to power
 μ Inner index
 Σ Sum
 % Modulo
 2 Literal 2
 ¬ Is zero
I Cast to string
 Implicitly print

Answer 14

Burlesque, 16 bytes

peR@{{$$}r[n!}fe

Try it online!

Takes arguments as d {1 2 3 4...}

pe # Read vals and push to stack
R@ # Generate all subsets
{
 {$$}r[ # Reduce by xor
 n! # Boolean not
}fe # Find first element