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]

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

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 5

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 6

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

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

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

Answer 12

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

Answer 13

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