16
\$\begingroup\$

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

14 Answers 14

Reset to default
6
\$\begingroup\$

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]
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
2
\$\begingroup\$

J, 36 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 38 bytes

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

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

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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";
}
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ why are only 32 items used? and the requirement to pad the input array is stretching the I/O rules too far IMO. \$\endgroup\$
    – qwr
    Dec 23, 2019 at 8:46
  • \$\begingroup\$ @qwr the bitmask only has 32 bits in it so more than that doesn't work. \$\endgroup\$
    – harold
    Dec 23, 2019 at 8:51
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.