# Linear dependences over the field with two elements

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.

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]

• May we return all solutions? Dec 20, 2019 at 19:48
• You may want to clarify that the empty set is not an acceptable solution. Dec 20, 2019 at 19:50
• 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? Dec 20, 2019 at 21:10
• @harold Yes, the bitmask sounds fine to me.
– Hood
Dec 20, 2019 at 22:22
• May we assume the entries are distinct?
– xnor
Dec 20, 2019 at 23:34

# 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]]


# 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 !*.&[+^].

# 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.

# 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


# 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!

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).

# 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


# 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.

# J, 36 bytes

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


Try it online!

# 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.

# Mathematica, 38 bytes

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


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

Try it online!

# 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";
}

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

# Charcoal, 32 bytes

ＩΦＥＸ²ＬθΦθ﹪÷ιＸ²μ²∧ι⬤↨⌈θ²¬﹪Σ÷ιＸ²μ²


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

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


# 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