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.

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

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:

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]

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 )

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"]
[]

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.

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

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]

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

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

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 .

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

Mathematica 53

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

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

Scala, 81

def p[A](x:Seq[A]){x.foldLeft(Seq(Seq[A]()))((a,b)=>a++a.map(b+:_)).map(println)}

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>

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);}

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     #   [[]]))

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.

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 ⁿ -o-1, tak aby każdy podzbiór znajdował się w osobnej linii

Haskell, 80 78 bytes

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

Try it online!

Jelly, 6 bytes

ŒPŒṘ€Y

Try it online!

ŒṘ€Y are string formatting.

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

Ruby, 39

$*.map{p *$*.combination($.)
$.+=1}
p$*

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 :/

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)

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?

Mathematica, 51

More cheating:

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

Use with @{1,2,3}.

JavaScript (ES6), 68 bytes

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

Demo

let f =

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

f([1,2,3])

Brachylog, 4 bytes

⊇ᵘẉᵐ

Try it online!

  ẉ     Write on its own line
 ᵘ ᵐ    every unique
⊇       subset of the input.

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

0.upto(ARGV.size){|a|ARGV.combination(a){|v| p v}}