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

14 Answers 14

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

\$\endgroup\$
4
\$\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.

\$\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
\$\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!

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

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

\$\endgroup\$
2
\$\begingroup\$

J, 36 bytes

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

Try it online!

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

\$\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";
}
\$\endgroup\$
  • \$\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 '19 at 8:46
  • \$\begingroup\$ @qwr the bitmask only has 32 bits in it so more than that doesn't work. \$\endgroup\$ – harold Dec 23 '19 at 8:51
1
\$\begingroup\$

Charcoal, 32 bytes

IΦEX²LθΦθ﹪÷ιX²μ²∧ι⬤↨⌈責﹪Σ÷ιX²μ²

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

    ²                               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
             ²                      Literal 2
            X                       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
                            X       Raised to power
                              μ     Inner index
                         Σ          Sum
                        ﹪           Modulo
                               ²    Literal 2
                       ¬            Is zero
I                                   Cast to string
                                    Implicitly print
\$\endgroup\$
1
\$\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!

\$\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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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