Zagrać w golfa problem sumy częściowej

15

Zadanie

Biorąc pod uwagę listę liczb całkowitych rozdzielanych spacjami jako dane wejściowe, wypisz wszystkie unikalne niepuste podzbiory tych liczb, które każdy podzbiór sumuje na 0.


Przypadek testowy

Wejście: 8 −7 5 −3 −2
Wyjście:-3 -2 5


Zwycięskie kryterium

To jest , więc wygrywa najkrótszy kod w bajtach!

arshajii
źródło
1
Czy musimy się martwić o wyjątkowość, jeśli dane wejściowe zawierają nieunikalne liczby? Innymi słowy, ile wyników muszę wydrukować dla danych wejściowych 3 3 -3 -3?
Keith Randall,
@Keith. Zgodnie z konwencją zestawy składają się z odrębnych elementów, które pojawiają się co najwyżej raz. Multisety mogą mieć elementy, które pojawiają się więcej niż jeden raz. en.wikipedia.org/wiki/Multiset
DavidC
4
@DavidCarraher, OP miesza terminologię, mówiąc o podzbiorach list.
Peter Taylor
@PeterTaylor Thanks. Słuszna uwaga.
DavidC,

Odpowiedzi:

4

GolfScript, 41 znaków

~][[]]\{`{1$+$}+%}%;(;.&{{+}*!},{" "*}%n*

Jeśli nie zależy ci na konkretnym formacie wyjściowym, możesz skrócić kod do 33 znaków.

~][[]]\{`{1$+$}+%}%;(;.&{{+}*!},`

Przykład (patrz online ):

> 8 -7 5 -3 -2 4
-3 -2 5
-7 -2 4 5
-7 -3 -2 4 8
Howard
źródło
6

Brachylog (2), 9 znaków

{⊇.+0∧}ᵘb

Wypróbuj online!

{⊇.+0∧}ᵘb
 ⊇           subset
   +0        that sums to 0
  .  ∧       output the subset
{     }ᵘ     take all unique solutions
        b    except the first (which is the empty solution)
pppery
źródło
4

Python, 119 znaków

def S(C,L):
 if L:S(C,L[1:]);S(C+[L[0]],L[1:])
 elif sum(map(int,C))==0and C:print' '.join(C)
S([],raw_input().split())

Zlicza rekurencyjnie wszystkie podzbiory 2 ^ n i sprawdza każdy z nich.

Keith Randall
źródło
Brawo!
Wpadłem
3

Python, 120

Jestem postacią gorszą niż rozwiązanie Keitha. Ale ... to zbyt blisko, aby nie publikować. Jedną z moich ulubionych cech golfa kodowego jest to, jak różne mogą być rozwiązania o podobnej długości.

l=raw_input().split()
print[c for c in[[int(j)for t,j in enumerate(l)if 2**t&i]for i in range(1,2**len(l))]if sum(c)==0]
boothby
źródło
2

Python ( 128 137 136)

Cholera itertools.permutations, za tak długie imię!

Rozwiązanie brutalnej siły. Dziwi mnie, że to nie jest najkrótsze: ale chyba itertoolszrujnuje to rozwiązanie.

Nie golfowany:

import itertools
initial_set=map(int, input().split())
ans=[]
for length in range(1, len(x)+1):
    for subset in itertools.permutations(initial_set, length):
        if sum(subset)==0:
            ans+=str(sorted(subset))
print set(ans)

Gra w golfa (brzydka moc wyjściowa):

from itertools import*
x=map(int,input().split())
print set(`sorted(j)`for a in range(1,len(x)+1)for j in permutations(x,a)if sum(j)==0)

Gra w golfa (ładna produkcja) (183):

from itertools import*
x=map(int,input().split())
print `set(`sorted(j)`[1:-1]for a in range(1,len(x)+1)for j in permutations(x,a)if sum(j)==0)`[5:-2].replace("'","\n").replace(",","")

import itertools as i: importowanie modułu itertools i wywoływanie go i

x=map(int,input().split()): rozdziela dane wejściowe spacjami, a następnie zamienia wynikowe elementy list na liczby całkowite ( 2 3 -5-> [2, 3, -5])

set ( sorted(j)dla zakresu in (1, len (x) +1) dla jw i.permutations (x, a) if sum (j) == 0):
Zwraca listę wszystkich podzbiorów w x, posortowane, gdzie suma wynosi 0, a następnie otrzymuje tylko unikalne elementy
( set(...))

Groby (`) wokół sorted(j)są skrótem Python repr(sorted(j)). Powodem tego jest to, że zestawy w Pythonie nie mogą obsługiwać list, więc następną najlepszą rzeczą jest użycie ciągów z listą jako tekstem.

beary605
źródło
Jestem zdezorientowany, w jaki sposób otrzymujesz liczby całkowite zamiast ciągów. split()tworzy listę ciągów, ale później wywołujesz sumpodzbiory tego podziału.
Keith Randall,
@KeithRandall: facepalm Spieszyłem się, więc nie testowałem swojego kodu. Dziękuję za zwrócenie na to uwagi.
beary605 10.10
Prawdopodobnie możesz uratować postać, robiącfrom itertools import*
Matt
tak naprawdę groby są skrótemrepr()
gnibbler 10.10.12
@gnibbler: Miałoby to dużo więcej sensu, gdy uruchamiane jest `` cześć ''. Dzięki!
beary605,
2

C # - 384 znaków

OK, programowanie w stylu funkcjonalnym w C # nie jest takie krótkie , ale uwielbiam to! (Używając tylko wyliczenia brutalnej siły, nic lepszego.)

using System;using System.Linq;class C{static void Main(){var d=Console.ReadLine().Split(' ').Select(s=>Int32.Parse(s)).ToArray();foreach(var s in Enumerable.Range(1,(1<<d.Length)-1).Select(p=>Enumerable.Range(0,d.Length).Where(i=>(p&1<<i)!=0)).Where(p=>d.Where((x,i)=>p.Contains(i)).Sum()==0).Select(p=>String.Join(" ",p.Select(i=>d[i].ToString()).ToArray())))Console.WriteLine(s);}}

Sformatowane i skomentowane dla większej czytelności:

using System;
using System.Linq;

class C
{
    static void Main()
    {
        // read the data from stdin, split by spaces, and convert to integers, nothing fancy
        var d = Console.ReadLine().Split(' ').Select(s => Int32.Parse(s)).ToArray();
        // loop through all solutions generated by the following LINQ expression
        foreach (var s in
            // first, generate all possible subsets; well, first just their numbers
            Enumerable.Range(1, (1 << d.Length) - 1)
            // convert the numbers to the real subsets of the indices in the original data (using the number as a bit mask)
            .Select(p => Enumerable.Range(0, d.Length).Where(i => (p & 1 << i) != 0))
            // and now filter those subsets only to those which sum to zero
            .Where(p => d.Where((x, i) => p.Contains(i)).Sum() == 0)
            // we have the list of solutions here! just convert them to space-delimited strings
            .Select(p => String.Join(" ", p.Select(i => d[i].ToString()).ToArray()))
        )
            // and print them!
            Console.WriteLine(s);
    }
}
Mormegil
źródło
2

SWI-Prolog 84

Ta wersja drukuje listę, zamiast próbować znaleźć odpowiednie powiązanie dla terminu w predykacie.

s([],O):-O=[_|_],sum_list(O,0),print(O).
s([H|T],P):-s(T,[H|P]).
s([_|T],O):-s(T,O).

Metoda wprowadzania

s([8,-7,5,-3,-2,4],[]).

Dla przypomnienia jest to wersja, która znajduje powiązanie spełniające predykat:

s(L,O):-s(L,0,O),O=[_|_].
s([],0,[]).
s([H|T],S,[H|P]):-R is H+S,s(T,R,P).
s([_|T],S,O):-s(T,S,O).

Metoda wprowadzania

s([8,-7,5,-3,-2,4],O).

Poprzednia wersja zawiera niepełne rozwiązanie, któremu nie udało się usunąć pustego zestawu.

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳
źródło
2

Mathematica 62 57 38

Kod

Wejście wprowadzone jako liczby całkowite w tablicy x.

x

Wejście

Grid@Select[Subsets@x[[1, 1]], Tr@# == 0 &]

Wynik

wynik


Wyjaśnienie

x[[1, 1]] konwertuje dane wejściowe na listę liczb całkowitych.

Subsets generuje wszystkie podzbiory z liczb całkowitych.

Select....Tr@# == 0 daje wszystkie te podzbiory, których suma równa się 0.

Grid formatuje wybrane podzbiory jako liczby całkowite rozdzielone spacjami.

DavidC
źródło
2

Galaretka , 6 bajtów

ŒPḊSÐḟ

Wypróbuj online!

Tylko dla kompletności. Podobnie jak Brachylog, Galaretka również postdatuje wyzwanie, ale do tej pory nowsze języki konkurują normalnie.

ŒP       Power set.
  Ḋ      Dequeue, remove the first element (empty set).
    Ðḟ   Filter out the subsets with truthy (nonzero)...
   S       sum.
użytkownik202729
źródło
2

05AB1E , 5 bajtów

æ¦ʒO>

Wypróbuj online!


Jeśli dane wejściowe muszą być rozdzielane spacjami, przejście #do tej odpowiedzi jest jedyną wymaganą zmianą.

Urna Magicznej Ośmiornicy
źródło
1

J, 57 53 51 49 znaków

>a:-.~(#:@i.@(2&^)@#<@":@(#~0=+/)@#"1 _])".1!:1[1

Stosowanie:

   >a:-.~(#:@i.@(2&^)@#<@":@(#~0=+/)@#"1 _])".1!:1[1
8 _7 5 _3 _2 4
5 _3 _2
_7 5 _2 4
8 _7 _3 _2 4
Gareth
źródło
Przepisanie pociągu jako (<@":@(#~0=+/)@#"1 _~2#:@i.@^#)oszczędza 4 znaki.
algorytm
1

Stax , 8 bajtów CP437

â±3╒yΣ╓à

Uruchom i debuguj online!

Wyjaśnienie

Używa do rozpakowania wersji (9 bajtów).

LS{|+!fmJ
L            Convert to list
 S           Powerset
  {   f      Filter with block
   |+!       Sum is zero
       mJ    Print each subset, joined by spaces
Weijun Zhou
źródło
Given a list of space-delimited integers as input; jednak bierzesz listę jako dane wejściowe.
Jonathan Frech
Naprawi to kosztem jednego bajtu.
Weijun Zhou
1

J , 34 bajty

(a:-.~](<@#~0=+/)@#~[:#:@i.2^#)@".

Wypróbuj online!

w jaki sposób

".konwertuje dane wejściowe na listę. następnie:

a: -.~ ] (<@#~ (0 = +/))@#~ [: #:@i. 2 ^ #
                                  i.       NB. ints from 0 to...
                                     2 ^ # NB. 2 to the input len
                            [: #:@         NB. converted to binary masks
       ] (             ) #~                NB. filter the input using
                                           NB. using those masks, giving
                                           NB. us all subsets
         (             )@                  NB. and to each one...
         (  #~ (0 = +/))                   NB. return it if its sum is
                                           NB. 0, otherwise make it 
                                           NB. the empty list.
         (<@           )                   NB. and box the result.
                                           NB. now we have our answers
                                           NB. and a bunch of empty 
                                           NB. boxes, or aces (a:).
a: -.~                                     NB. remove the aces.
Jonasz
źródło
1

Perl 6 , 51 bajtów

*.words.combinations.skip.grep(!*.sum)>>.Bag.unique

Wypróbuj online!

Zwraca listę unikatowych toreb, których suma wynosi 0. Torba jest zestawem ważonym.

Wyjaśnienie:

*.words                 # Split by whitespace
 .combinations          # Get the powerset
 .skip                  # Skip the empty list
 .grep(!*.sum)          # Select the ones that sum to 0
 >>.Bag                 # Map each to a weighted Set
 .unique                # And get the unique sets
Jo King
źródło
0

Rubin, 110 bajtów

a=gets.split.map &:to_i;b=[];(1...a.length).each{|c|a.permutation(c){|d|d.sum==0?b<<d:0}};p b.map(&:sort).uniq

Link TIO doda później.

Pobiera dane wejściowe ze standardowego wejścia jako listę liczb, np 8 −7 5 −3 −2

Jak to działa: Konwertuje dane wejściowe na tablicę liczb. Pobiera wszystkie permutacje długości od 1 do długości tablicy. Dodaje je do tablicy wyjściowej, jeśli sumuje się do 0. Wyświetla tablicę bez duplikatów.

Dane wyjściowe dla przykładowego wejścia: [[-3, -2, 5]]

CG Jedną ręką
źródło