14
\$\begingroup\$

Given an unordered collection of positive integers by any reasonable input method, return all of the sub-collections that have an odd number of odd elements (i.e. have an odd total).

This is so you should aim to minimize the byte count of your program.

Since some languages only have ordered collections (lists, arrays, vectors, etc.) or don't have an unordered collection that allows duplicates, you may use ordered collections (regardless of your language choice), however you should not output any duplicate collections with different orders (e.g. [2,3] and [3,2]). You may output in whatever order you see fit.

Test cases

[2,3,7,2] -> [[3],[7],[2,3],[2,7],[2,2,3],[2,2,7]]
[2,4,6,8] -> []
[4,9]     -> [[9],[4,9]]
\$\endgroup\$
  • 2
    \$\begingroup\$ Are duplicate subcollections allowed? As in, for [2, 2, 3], may we return [[2, 2, 3], [2, 3], [2, 3]]? \$\endgroup\$ – HyperNeutrino May 26 '17 at 19:16
  • 1
    \$\begingroup\$ Hint: the sum of such a set can only be odd. Any other variant of these sets can only have an even sum. \$\endgroup\$ – tuskiomi May 26 '17 at 19:17
  • \$\begingroup\$ @HyperNeutrino No you should only return each one once \$\endgroup\$ – Sriotchilism O'Zaic May 26 '17 at 19:17
  • \$\begingroup\$ Okay. Do the subcollections need to be in ascending order or is it fine to list them in the order provided in the original array? \$\endgroup\$ – HyperNeutrino May 26 '17 at 19:18
  • \$\begingroup\$ @HyperNeutrino They may be in any order, (ideally they would be an unordered collection, but many languages don't have such a construct so ordered collections are fine as long as the order is not important) \$\endgroup\$ – Sriotchilism O'Zaic May 26 '17 at 19:21
5
\$\begingroup\$

05AB1E, 6 bytes

{æÙʒOÉ

Try it online!

{æÙʒOÉ
{      Sort
 æ     Powerset
  Ù    Uniqufy
   ʒ   Keep elements where
    O                      the sum
     É                             is uneven

-2 bytes thanks to @EriktheOutgolfer

\$\endgroup\$
  • \$\begingroup\$ @WheatWizard Yes (comment reply to Jonathan). Thanks for reminding me. \$\endgroup\$ – HyperNeutrino May 26 '17 at 19:34
  • \$\begingroup\$ 2% can be golfed to É and } can be removed. But your answer seems to have the issue. \$\endgroup\$ – Erik the Outgolfer May 26 '17 at 19:57
4
\$\begingroup\$

Python 3, 93 bytes

f=lambda x,r=[[]]:x and f(x[1:],r+[y+x[:1]for y in r])or{(*sorted(y),)for y in r if sum(y)&1}

Returns a set of tuples. Most likely way too long.

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Pyth, 10 9 8 bytes

{f%sT2yS

Try it online!

         # implicit input
       S # sort input, this way the subsets will already be sorted
      y  # all subsets
 f       # filter elements when ..
   sT    # the sum ..
  %  2   # is odd
{        # remove all duplicated elements
         # implicit output
\$\endgroup\$
  • 1
    \$\begingroup\$ {SMf%sT2y saves a byte it seems. \$\endgroup\$ – Erik the Outgolfer May 26 '17 at 19:56
3
\$\begingroup\$

Python 2, 91 bytes

r=[[]]
for n in input():r+=map([n].__add__,r)
print{tuple(sorted(y))for y in r if sum(y)&1}

Prints a set of tuples. If a set of strings is allowed, tuple(sorted(y)) can be replaced with `sorted(y)` for 86 bytes.

Try it online!

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

Jelly, 9 bytes

ṢŒPSḂ$ÐfQ

Try it online!

Bug fixed thanks to Jonathan Allan.

ṢŒPSḂ$ÐfQ  Main Link
Ṣ          Sort
 ŒP        Powerset
      Ðf   Filter to keep elements where                         is truthy
    Ḃ                                    the last bit of
   S                                                     the sum
        Q  Only keep unique elements
\$\endgroup\$
2
\$\begingroup\$

Perl 6, 50 bytes

{.combinations.grep(*.sum!%%2).unique(:as(*.Bag))}

To filter out the same-up-to-ordering combinations I filter out duplicates by converting each to a Bag (unordered collection) before comparing. Unfortunately I couldn't find a way to accept a Bag as input that was as concise.

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

Brachylog, 11 bytes

o⊇ᵘ{+ḃt1&}ˢ

Try it online!

I hoped to find a shorter solution, but here's the best I could do.

Explanation

o⊇ᵘ{+ḃt1&}ˢ    
o                                        the input, sorted
 ⊇ᵘ           Find all unique subsets of

   {    &}ˢ   Then select only those results where
    +                                          the sum
     ḃ                           the base 2 of
      t        The last digit of
       1                                               is 1.

Yeah, I could've used modulo 2 to check for oddness, but that's not an odd approach ;)

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

Mathematica 31 44 38 bytes

Among all subsets of the input set, it returns those for which the sum, Tr, is odd.

6 bytes saved thanks to alephalpha.

Select[Union@Subsets@Sort@#,OddQ@*Tr]&

 Select[Union@Subsets@Sort@#,OddQ@*Tr]&[{2,3,7,2}]

{{3}, {7}, {2, 3}, {2, 7}, {2, 2, 3}, {2, 2, 7}}

\$\endgroup\$
  • \$\begingroup\$ What's with the space? \$\endgroup\$ – CalculatorFeline May 26 '17 at 20:41
  • 1
    \$\begingroup\$ Unfortunately, this doesn't meet the spec, as {2,3} and {3,2} should not both be returned (same with {2,7} and {7,2}). \$\endgroup\$ – Greg Martin May 27 '17 at 0:05
  • \$\begingroup\$ Select[Union@Subsets@Sort@#,OddQ@*Tr]& \$\endgroup\$ – alephalpha May 27 '17 at 15:42
1
\$\begingroup\$

PHP, 126 bytes

for(;++$i>>$argc<1;sort($t),$s&1?$r[join(_,$t)]=$t:0)for ($t=[],$j=$s=0;++$j<$argc;)$i>>$j&1?$s+=$t[]=$argv[$j]:0;print_r($r);

takes input from command line arguments; run with -nr or try it online.

breakdown

for(;++$i>>$argc<1;             # loop through subsets
    sort($t),                       # 2. sort subset
    $s&1?$r[join(_,$t)]=$t:0        # 3. if sum is odd, add subset to results
    )                               # 1. create subset:
    for ($t=[],$j=$s=0;++$j<$argc;)     # loop through elements
        $i>>$j&1?                       # if bit $j is set in $i
        $s+=$t[]=$argv[$j]:0;           # then add element to subset
print_r($r);                    # print results
\$\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.