Najkrótsza implementacja zestawu zasilającego

22

Definicja problemu

Wydrukuj zestaw energetyczny danego zestawu. Na przykład:

[1, 2, 3] => [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Każdy element należy wydrukować w osobnej linii, więc powyższy przykład wydrukowano by jako:

[]
[1]
[2]
...
[1, 2, 3]

Przykładowy kod (w D, tutaj przykład python ):

import std.stdio;

string[][] powerset(string[] set) {
    if (set.length == 1) {
        return [set, []];
    }

    string[][] ret;
    foreach (item; powerset(set[1 .. $])) {
        ret ~= set[0]~item;
        ret ~= item;
    }

    return ret;
}

void main(string[] argv) {
    foreach (set; powerset(argv[1 .. $]))
        writeln(set);
}

Wkład

Elementy będą przekazywane jako argumenty. Na przykład powyższy przykład zostanie przekazany do programu o nazwie powersetjako:

powerset 1 2 3

Argumenty będą alfanumeryczne.

Zasady

  1. Brak bibliotek oprócz io
  2. Wyjścia nie trzeba zamawiać
  3. Powerset nie musi być przechowywany, tylko drukowany
  4. Elementy w zestawie musi być ograniczony (na przykład 1,2,3, [1,2,3]i ['1','2','3']są dopuszczalne, ale123 nie jest
    • Końcowe ograniczniki są w porządku (np. 1,2,3, == 1,2,3)
  5. Najlepsze określa się na podstawie liczby bajtów

Najlepsze rozwiązanie zostanie ustalone nie później niż 10 dni po pierwszym złożeniu.

beatgammit
źródło
Ściśle związany z codegolf.stackexchange.com/questions/6380
Peter Taylor
2
Gdyby tylko to wyzwanie zostało zaktualizowane, aby umożliwić ustawienia domyślne, takie jak zwracanie i funkcje. Python będzie 54 bajtów: lambda L:reduce(lambda r,x:r+[s+[x]for s in r],L,[[]]).
mbomb007,
Nie zgadzam się tylko na drukowanie ... Dlaczego nie pozwolić na dane, również na zmienną ... Dlaczego więc drukować w kolumnie, a nie w wierszu?
RosLuP,

Odpowiedzi:

15

Matematyka 16

Kod

Subsets pochodzi z Mathematica.

Column@Subsets@s

Kod (bez kolumny) można zweryfikować na WolframAlpha . (Musiałem użyć nawiasów zamiast@ ; oznaczają to samo.

Stosowanie

s={1,2,3}
Column@Subsets@s

output


Ta metoda (55 znaków) wykorzystuje podejście sugerowane przez @ w0lf.

s #&/@Tuples[{0,1},Length@s]/.{0:>Sequence[]}//Column

Awaria

Wygeneruj krotki złożone z 0i 1o długościLength[s]

Tuples[{0, 1}, Length@s]

{{0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 1, 1}, {1, 0, 0}, {1, 0, 1}, { 1, 1, 0}, {1, 1, 1}}

Pomnóż oryginalną listę (wektor) przez każdą krotkę:

s # & /@ Tuples[{0, 1}, Length@s]

{{0, 0, 0}, {0, 0, 3}, {0, 2, 0}, {0, 2, 3}, {1, 0, 0}, {1, 0, 3}, { 1, 2, 0}, {1, 2, 3}}

Usuń 0's.%jest skrótem dla „poprzedniego wyniku”.

% /. {0:> Sekwencja []}

{{}, {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}}

Wyświetl w kolumnie:

Mathematica graphics

DavidC
źródło
@tjameson Miałem poważne wątpliwości, czy powinienem to opublikować, ale pomyślałem, że niektórym może być interesujące wiedzieć, że jest on wbudowany.
DavidC
Uważam to za interesujące :)
Dr. Belisarius,
Czy możesz pominąć si umieścić dane wejściowe na końcu wiersza?
Solomon Ucko
15 bajtów: Subsets/*Columntworzy anonimową funkcję, która pobiera listę i zwraca wyświetlanie w kolumnach.
Rzym,
9

C, 118 115

Chociaż można zaoszczędzić około 20 znaków dzięki prostszemu formatowaniu, nadal nie uda się wygrać pod względem kodu golfowego.

x,i,f;
main(int a,char**s){
    for(;x<1<<a;x+=2,puts("[]"+f))
        for(i=f=0;++i<a;)x&1<<i?f=!!printf("%c%s","[,"[f],s[i]):0;
}

Testowanie:

/a.out 1 2 3
[]
[1]
[2]
[1,2]
[3]
[1,3]
[2,3]
[1,2,3]
króliczek
źródło
Miły. Kilka wskazówek: styl K&R ( main(a,s)char**s;{...}) f|=x&1<<i&&printfjest krótszy niż ?:.
ugoren
Właśnie zorientowałem się, co jest za x+=2(i gdzie s[0]poszło). Naprawdę fajna sztuczka.
ugoren
Odmowa odpowiedzi na golfa, ponieważ „nadal nie wygra w kategoriach golfa w żaden sposób”. sprawia, że ​​odpowiedź nie jest poważnym konkurentem dla zwycięskich kryteriów wyzwania.
pppery
7

GolfScript, 22 18 znaków

~[[]]{{+}+1$%+}@/`

Kolejna próba w GolfScript z zupełnie innym algorytmem. Format wejściowy jest taki sam, jak w przypadku odpowiedzi w0lf. ( test online )

Howard
źródło
+1 Świetne rozwiązanie! Kopalnia jest refaktoryzowana ze względu na czytelność :-P
Cristian Lupascu
5

GolfScript (43 znaki)

To może wydawać się dość długie, ale jest to pierwsze rozwiązanie zgodne ze specyfikacją: dane wejściowe pochodzą z argumentów wiersza poleceń, a dane wyjściowe są rozdzielane znakami nowej linii.

"#{ARGV.join('
')}"n/[[]]\1/{`{1$+.p}+%}%p;

Na przykład

$ golfscript.rb powset.gs 1 2 3
["1"]
["2"]
["2" "1"]
["3"]
["3" "2"]
["3" "1"]
["3" "2" "1"]
[]
Peter Taylor
źródło
Cytaty nie są konieczne, jeśli to robi różnicę.
beatgammit
@tjameson, cytaty pochodzą z użycia najkrótszego możliwego sposobu drukowania. Fakt, że te wartości są ciągami, a nie liczbami całkowitymi, wynika z niemożności bezpośredniego dostępu do argumentów wiersza poleceń GolfScript: musi polegać na tym, że interpreter wykonuje ewaluację w języku Ruby i umieszcza wynik w ciągu.
Peter Taylor
4

awk (82)

{for(;i<2^NF;i++){for(j=0;j<NF;j++)if(and(i,(2^j)))printf "%s ",$(j+1);print ""}}

zakładamy zapisany w pliku powerset.awk, użycie

$ echo 1 2 3 | awk -f powerset.awk

1
2
1 2
3
1 3
2 3
1 2 3

ps, jeśli twój awk nie ma funkcji i (), zamień go na, int(i/(2^j))%2ale dodaje dwa do liczby.

karakfa
źródło
(2^j)-> 2^joszczędza 2 bajty; .awkplik działa również bez końca \n, dzięki czemu można zgolić kolejny bajt.
mklement0
3

JavaScript, 98

Niestety, spory kawałek wydaje się na formatowanie wyjściowe.

for(n in a=eval(prompt(i=p=[[]])))
    for(j=i+1;j;)
        p[++i]=p[--j].concat(a[n]);
alert('[]'+p.join('\n'))

Wkład

Pobiera tablicę JavaScript. (np. [1,2,3])

Wydajność

[]
1
1,2
2
2,3
1,2,3
1,3
3
Paul Walls
źródło
3

Python ( 74 70 znaków)

def p(a,v):
 if a:i,*a=a;p(a,v);p(a,v+[i])
 else:print v
p(input(),[])

dla danych wejściowych jako 1,2,3lub [1,2,3]wyjściowych jest:

[]
[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]
AMK
źródło
[a[0]]=a[:1]
ugoren,
z wejściem 1,2,3 a[:1]nie działa. krotka + lista niedozwolona. Istnieje lepsze rozwiązanie
AMK
+1 zai,*a=a
primo
Czy nie jest i,*a=aPython 3? To nie działa na moim 2.7.1.
ugoren
Ani w wersji 2.7.2. To może wyjaśniać, dlaczego nigdy wcześniej nie widziałem tej sztuczki ... większość serwerów golfowych z kodem działa w wersji 2.7.x.
primo
3

Pyton 70 67 bajtów

def p(a,*v):
 i=0;print v
 for n in a:i+=1;p(a[i:],n,*v)
p(input())

Dane wejściowe są pobierane w taki sam sposób, jak w przypadku rozwiązania ugorena . Przykładowe I / O:

$ echo [1,2,3] | powerset.py
()
(1,)
(2, 1)
(3, 2, 1)
(3, 1)
(2,)
(3, 2)
(3,)
primo
źródło
1
Możesz zaoszczędzić trochę za pomocą def p(a,*v)i wtedy p(a[i:],n,*v). Dane wyjściowe stają się nieco brzydsze, ale nadal są OK.
ugoren
Bardzo sprytne, dzięki za podpowiedź.
primo
3

J, 19 znaków

   (<@#~#:@i.@(2&^)@#)

   (<@#~#:@i.@(2&^)@#) 1 2 3
┌┬─┬─┬───┬─┬───┬───┬─────┐
││3│2│2 3│1│1 3│1 2│1 2 3│
└┴─┴─┴───┴─┴───┴───┴─────┘

Boks ascii na wyjściu jest wywoływany boxingi zapewnia zbieranie heterogenów (tutaj dla różnych długości tablic).

randomra
źródło
2

Golfscript 48

~:x,:§2\?,{[2base.,§\-[0]*\+x\]zip{~{}{;}if}%p}%

Ten program wykorzystuje binarne reprezentacje liczb od 0 do długości (dane wejściowe) do generowania elementów zestawu mocy.

Wkład

Format wejściowy to format tablicy Golfscript (przykład: [1 2 3] )

Wydajność

Dane wyjściowe to zbiór tablic oddzielonych znakami nowej linii, reprezentujących zestaw mocy. Przykład:

[]
[3]
[2]
[2 3]
[1]
[1 3]
[1 2]
[1 2 3]

Test online

Program można przetestować online tutaj .

Cristian Lupascu
źródło
Świetnie, ale czy możesz wyznaczyć nowe linie?
beatgammit
@tjameson Udało mi się wygenerować dane rozdzielane znakami nowej linii, zachowując tę ​​samą liczbę znaków. Proszę zobaczyć aktualizację mojej odpowiedzi.
Cristian Lupascu
2

Haskell (96)

import Control.Monad
import System.Environment
main = getArgs >> = mapM print.filterM (\ _-> [False ..])

Jeśli importowanie Control.Monadnie jest dozwolone, staje się to 100 znaków:

import System.Environment
main = getArgs >> = mapM print.p
pz = przypadek z {[] -> [[]]; x: y-> p y ++ map (x:) (py)}
Lambda Fairy
źródło
2

Mathematica 53

Column@Fold[#~Join~Table[x~Join~{#2},{x,#}]&,{{}},#]&

enter image description here

chyanog
źródło
2

APL (26)

Czyta dane wejściowe z klawiatury, ponieważ nie ma argvodpowiednika.

↑⍕¨(/∘T)¨↓⍉(M/2)⊤⍳2*M←⍴T←⎕

Stosowanie:

      ↑⍕¨(/∘T)¨↓⍉(M/2)⊤⍳2*M←⍴T←⎕
⎕:
      1 2 3
3    
2    
2 3  
1    
1 3  
1 2  
1 2 3

Wyjaśnienie:

  • T←⎕: wczytaj dane wejściowe, zapisz w T
  • M←⍴T: długość sklepu TwM
  • (M/2)⊤⍳2*M: generuj wzorce bitów dla 1upto 2^Mprzy użyciu Mbitów.
  • ↓⍉: podziel macierz, aby każdy wzór bitowy był osobny
  • (/∘T)¨: dla każdego wzorca bitowego wybierz te elementy podrzędne z T.
  • ↑⍕¨: dla danych wyjściowych pobierz reprezentację ciągu każdego elementu (aby wypełnił się spacjami, a nie zerami) i sformatuj jako macierz (aby każdy element znajdował się w osobnej linii).
marinus
źródło
2

Scala, 81

def p[A](x:Seq[A]){x.foldLeft(Seq(Seq[A]()))((a,b)=>a++a.map(b+:_)).map(println)}
Dan G.
źródło
2

JavaScript ( ES6 ) 76

Częściowo skopiowane z tego: /codegolf//a/51502/21348

Używając bitmapy, więc jest ograniczona do nie więcej niż 32 elementów.

Uruchom fragment w przeglądarce Firefox, aby go przetestować.

f=l=>{ 
  for(i=0;i<1<<l.length;i++)
    console.log(l.filter(v=>[i&m,m+=m][0],m=1))
}  

// TEST

// Redefine console to have output inside the page
console = { log: (...p) => O.innerHTML += p.join(' ') + '\n' }

test=()=>{
  var set = I.value.match(/[^ ,]+/g)
  O.innerHTML='';
  f(set);
}

test()
#I,#O { border: 1px solid #aaa; width: 400px; padding:2px}
Insert values, space or comma separated:<br>
<input id=I value='1 2 3'> <button onclick="test()">-></button>
<pre id=O></pre>

edc65
źródło
2

C # 164

Człowieku, to jest trudne w C #!

void P<T>(T[]c){foreach(var d in c.Aggregate<T,IEnumerable<IEnumerable<T>>>(new[]{new T[0]},(a,b)=>a.Concat(a.Select(x=>x.Concat(new[]{b})))))Console.WriteLine(d);}
Ben Reich
źródło
2

Python 2, 64 bajty

Za pomocą danych oddzielonych przecinkami:

P=[[]]
for i in input():P+=[s+[i]for s in P]
for s in P:print s

Pyth, 4 bajty (przy użyciu wbudowanego) lub 14 bajtów (bez)

Jak zauważył @Jakube w komentarzach, Pyth jest zbyt nowy na to pytanie. Nadal jest rozwiązanie wykorzystujące wbudowany operator zestawu Pyth:

jbyQ

A oto jeden bez niego:

jbu+Gm+d]HGQ]Y

Możesz wypróbować oba rozwiązania tutaj i tutaj . Oto wyjaśnienie drugiego rozwiązania:

jb       # "\n".join(
 u       #  reduce(
  +G     #   lambda G,H: G+
   m     #    map(
    +d]H #     lambda d: d+[H],
    G    #     G),
  Q      #   input()
  ]Y     #   [[]]))
Uri Granta
źródło
2

pieprzenie mózgu, 94 bajty

+[[<+>>+<-]++[>-<------]>-[>]<<[>>+>]>,]++++++++++[[[<]<]+[-[>[.>]]<[<]>+[>]>]<<
.[<<[<]>-]++>]

Sformatowany:

+
[
  [<+> >+<-]
  ++[>-<------]>-[>]
  <<[>>+>]
  >,
]
++++++++++
[
  [[<]<]
  +
  print
  [
    -[>[.>]]
    <[<]
    >+[>]
    >
  ]
  <<.
  increment
  [
    <<[<]
    >-
  ]
  ++>
]

Oczekuje wprowadzenia formularza 9,10,11bez końcowego znaku nowej linii i wyświetla podzbiory w tym samym formacie, czasem z końcowym przecinkiem. Pierwszy wydrukowany wiersz zawsze będzie pusty, co oznacza pusty zestaw.

Wypróbuj online.

Podstawową ideą jest umieszczenie nieco obok każdego elementu, a następnie wielokrotne zwiększanie liczby binarnej podczas drukowania odpowiedniego podzestawu przed każdym przyrostem. (Bit wskazuje, czy element znajduje się w podzbiorze.) Do zakończenia programu służy bit wartownika po lewej stronie tablicy. Ta wersja faktycznie tworzy wykładniczą liczbę wartowników, aby zaoszczędzić niektóre bajty; bardziej wydajne 99-bajtowe rozwiązanie wykorzystujące tylko jeden wartownik można znaleźć w historii zmian.

Każdy bit jest kodowany jako jeden plus jego wartość; to znaczy, może to być 1albo 2. Taśma jest układana z bitem przed każdym elementem i pojedynczą komórką zerową między sąsiednimi elementami. Przecinek znajduje się na taśmie dla elementów nie-końcowych, więc możemy wygodnie po prostu wydrukować elementy bez wykonywania dodatkowej pracy przy obsłudze ograniczników.

Mitch Schwartz
źródło
2

APL (Dyalog Classic) , 13 bajtów

⍪,⊃∘.,/⎕,¨⊂⊂⍬

Wypróbuj online!

Wydajność:

 1 2 3 
 1 2   
 1 3   
 1     
 2 3   
 2     
 3     

Na końcu jest pusty wiersz reprezentujący pusty zestaw.

Wyjaśnienie:

oceniane dane wejściowe

⎕,¨⊂⊂⍬ dołącz pustą listę numeryczną po każdym elemencie

∘., Produkt kartezjański

/ redukcja (foldr)

ujawnić (konieczne po obniżeniu APL)

W tym momencie wynikiem jest n-wymiarowa tablica 2 na -...- na-2, gdzie n jest długością danych wejściowych.

, spłaszczyć w wektorze

zamień wektor w pionową macierz 2 n -o-1, tak aby każdy podzbiór znajdował się w osobnej linii

ngn
źródło
2

Haskell, 80 78 bytes

import System.Environment
main=getArgs>>=mapM(print.concat).mapM(\a->[[a],[]])

Try it online!

Angs
źródło
The I/O requirements are horrible, however people are interpreting them quite loosely. If you change to taking input via stdin you could save 15 bytes, see this.
ბიმო
1

Python, 93 87 chars

Python makes formatting simple, because the required input/output matches its native format.
Only supports items which are Python literals (e.g. 1,2,'hello', not 1,2,hello).
Reads standard input, not parameters.

f=lambda x:x and f(x[1:])+[x[:1]+a for a in f(x[1:])]or[()]
for l in f(input()):print l
ugoren
źródło
print f(input()) shorter
AMK
@AMK, the requirement is for each element to be printed in one line. But list can indeed be removed (if also replacinf [[]] with [()].
ugoren
print'\n'.join(f(input())) saves two characters
beary605
@beary605, doesn't work, f() contains tuples, not strings.
ugoren
1

Ruby, 39

$*.map{p *$*.combination($.)
$.+=1}
p$*
Lowjacker
źródło
1

Haskell 89 chars

import System.Environment
main=getArgs>>=mapM print.p
p[]=[[]]
p(x:y)=(map(x:)$p y)++p y

Getting parameters is long :/

kyticka
źródło
one more char can be shaved off with map(x:)(p y)++p y and yet two more chars above that with [(x:),id]<*>p y. Apparently <*> is in the Prelude now. (filterM isn't).
Will Ness
1

R, 63

y=lapply(seq(v),function(x)cat(paste(combn(v,x,s=F)),sep="\n"))

Here, v represents a vector.

Usage:

v <- c(1, 2, 3)
y=lapply(seq(v),function(x)cat(paste(combn(v,x,s=F)),sep="\n"))
1
2
3
c(1, 2)
c(1, 3)
c(2, 3)
c(1, 2, 3)
Sven Hohenstein
źródło
1

K, 14 bytes

{x@&:'!(#x)#2}

Generate all 0/1 vectors as long as the input, gather the indices of 1s and use those to select elements from the input vector. In practice:

  {x@&:'!(#x)#2} 1 2 3
(!0
 ,3
 ,2
 2 3
 ,1
 1 3
 1 2
 1 2 3)

This is a bit liberal with the output requirements, but I think it's legal. The most questionable part is that the empty set will be represented in a type dependent form; !0 is how K denotes an empty numeric vector:

  0#1 2 3      / integers
!0
  0#`a `b `c   / symbols
0#`
  0#"foobar"   / characters
""

Explanation

The (#x)#2 builds a vector of 2 as long as the input:

  {(#x)#2}1 2 3
2 2 2
  {(#x)#2}`k `d `b `"+"
2 2 2 2

When monadic ! is applied to a vector, it is "odometer":

  !2 2 2
(0 0 0
 0 0 1
 0 1 0
 0 1 1
 1 0 0
 1 0 1
 1 1 0
 1 1 1)

Then we use "where" (&) on each (') vector to gather its indices. The colon is necessary to disambiguate between the monadic and dyadic form of &:

  &0 0 1 0 1 1
2 4 5

  {&:'!(#x)#2} 1 2 3
(!0
 ,2
 ,1
 1 2
 ,0
 0 2
 0 1
 0 1 2)

If we just wanted combination vectors, we'd be done, but we need to use these as indices into the original set. Fortunately, K's indexing operator @ can accept a complex structure of indices and will produce a result with the same shape:

  {x@&:'!(#x)#2} `a `c `e
(0#`
 ,`e
 ,`c
 `c `e
 ,`a
 `a `e
 `a `c
 `a `c `e)

Elegant, no?

JohnE
źródło
1
This is no longer valid, as "odometer" in oK now generates a flipped matrix. It can be corrected at the cost of a single byte: {x@&:'+!(#x)#2}. Unrelated: a shorter equivalent of (#x)#2 is 2|~x.
ngn
1

Mathematica, 51

More cheating:

Column@ReplaceList[Plus@@HoldForm/@#,x___+___->{x}]&

Use with @{1,2,3}.

LogicBreaker
źródło
Your code should take the set as input, not just hardcode it. Also, since this is code golf, you should include the byte count of the code (and probably remove the unnecessary spaces).
Martin Ender
Since this contest is long over, the post was more for the idea, but I've edited it.
LogicBreaker
1

JavaScript (ES6), 68 bytes

a=>alert(a.reduce((a,x)=>[...a,...a.map(y=>[...y,x])],[[]]).join`
`)

Demo

Arnauld
źródło
Why the alert?
Shaggy
@Shaggy The challenge explicitly asks to print each element on a separate line -- which would probably frowned upon with our current standards. Most answers seem to stick to this rule.
Arnauld
Ah, fair enough; I interpreted "print" as "output".
Shaggy
0

Ruby Array method combination (from 1.9 ) [50 chars]

0.upto(ARGV.size){|a|ARGV.combination(a){|v| p v}}
beginnerProg
źródło