Definisi masalah

Cetak Power Set dari set yang diberikan. Sebagai contoh:

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

Setiap elemen harus dicetak pada baris terpisah, jadi contoh di atas akan dicetak sebagai:

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

Kode contoh (dalam D, contoh python di sini ):

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

Memasukkan

Elemen akan diteruskan sebagai argumen. Misalnya, contoh yang diberikan di atas akan diteruskan ke program yang disebut powerset:

powerset 1 2 3

Argumen akan menjadi alfanumerik.

Aturan

1. Tidak ada perpustakaan selain io
2. Output tidak harus dipesan
3. Powerset tidak harus disimpan, hanya dicetak
4. Elemen-elemen dalam himpunan harus dibatasi (misalnya 1,2,3, [1,2,3]dan ['1','2','3']dapat diterima, tetapi 123tidak
   • Pembatas trailing baik-baik saja (mis. 1,2,3, == 1,2,3)
5. Terbaik ditentukan berdasarkan jumlah byte

Solusi terbaik akan diputuskan tidak kurang dari 10 hari setelah pengiriman pertama.

Mathematica 16

Kode

Subsets adalah asli dari Mathematica.

Column@Subsets@s

Kode (tanpa kolom) dapat diverifikasi di WolframAlpha . (Saya harus menggunakan kurung bukan @; mereka berarti hal yang sama.

Pemakaian

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

Metode ini (55 karakter) menggunakan pendekatan yang disarankan oleh @ w0lf.

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

Kerusakan

Hasilkan tupel, terdiri dari 0dan 1panjangnyaLength[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}}

Lipat gandakan daftar asli (vektor) dengan masing-masing tuple:

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

Hapus 0's. %adalah singkatan untuk "output sebelumnya".

% /. {0:> Urutan []}

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

Tampilkan dalam kolom:

C, 118 115

Meskipun dapat menyimpan kira-kira 20 karakter dengan format yang lebih sederhana, tetap saja tidak akan menang dalam ketentuan kode golf.

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

Pengujian:

/a.out 1 2 3
[]
[1]
[2]
[1,2]
[3]
[1,3]
[2,3]
[1,2,3]

GolfScript, 22 18 karakter

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

Upaya lain dalam GolfScript dengan algoritma yang sama sekali berbeda. Format input sama dengan jawaban w0lf. ( tes online )

GolfScript (43 karakter)

Ini mungkin terlihat cukup panjang, tetapi ini adalah solusi pertama untuk mengikuti spesifikasi: input berasal dari argumen baris perintah, dan output dibatasi oleh baris baru.

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

Misalnya

$ 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 ""}}

anggap disimpan dalam file powerset.awk, penggunaan

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

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

ps jika awk Anda tidak memiliki dan () berfungsi, ganti dengan int(i/(2^j))%2tetapi tambahkan dua ke hitungan.

JavaScript, 98

Sayangnya, sebagian besar dihabiskan untuk format output.

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

Memasukkan

Mengambil array JavaScript. (mis. [1,2,3])

Keluaran

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

Python ( 74 70 karakter)

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

untuk input sebagai 1,2,3atau [1,2,3], output adalah:

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

Python 70 67 byte

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

Input diambil dengan cara yang sama seperti untuk solusi ugoren . Sampel I / O:

$ echo [1,2,3] | powerset.py
()
(1,)
(2, 1)
(3, 2, 1)
(3, 1)
(2,)
(3, 2)
(3,)

J, 19 karakter

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

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

Tinju ascii dalam output disebut boxingdan menyediakan koleksi heterogen (untuk panjang array yang berbeda di sini).

Naskah Golf 48

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

Program ini menggunakan representasi biner angka dari 0 hingga panjang (input) untuk menghasilkan item powerset.

Memasukkan

Format masukan adalah Golfscript Format array (contoh: [1 2 3])

Keluaran

Outputnya adalah kumpulan array yang dipisahkan oleh baris baru, mewakili set daya. Contoh:

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

Tes online

Program ini dapat diuji secara online di sini .

Haskell (96)

impor Control.Monad
Sistem impor. Lingkungan
main = getArgs >> = mapM print.filterM (\ _-> [Salah ..])

Jika mengimpor Control.Monadtidak diizinkan, ini menjadi 100 karakter:

Sistem impor. Lingkungan
main = getArgs >> = mapM print.p
pz = huruf z dari {[] -> [[]]; x: y-> p y ++ peta (x:) (py)}

Mathematica 53

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

APL (26)

Membaca input dari keyboard karena tidak ada argvpadanannya.

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

Pemakaian:

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

Penjelasan:

• T←⎕: baca input, simpan di T
• M←⍴T: panjang toko TdiM
• (M/2)⊤⍳2*M: Menghasilkan pola bit untuk 1upto 2^Mmenggunakan Mbit.
• ↓⍉: pisahkan matriks sehingga masing-masing pola bit terpisah
• (/∘T)¨: untuk setiap pola bit, pilih sub-item dari T.
• ↑⍕¨: untuk output, dapatkan representasi string dari setiap elemen (sehingga akan mengisi menggunakan kosong dan bukan nol), dan format sebagai matriks (sehingga setiap elemen berada di barisnya sendiri).

Scala, 81

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

JavaScript ( ES6 ) 76

Disalin sebagian dari yang ini: /codegolf//a/51502/21348

Menggunakan bitmap, jadi terbatas tidak lebih dari 32 elemen.

Jalankan cuplikan di Firefox untuk menguji.

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

Man ini sulit di 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 byte

Menggunakan input yang dipisahkan koma:

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

Pyth, 4 byte (menggunakan builtin) atau 14 byte (tanpa)

Seperti dicatat oleh @Jakube dalam komentar, Pyth terlalu baru untuk pertanyaan ini. Masih ada solusi menggunakan operator powerset bawaan Pyth:

jbyQ

Dan ini satu tanpa itu:

jbu+Gm+d]HGQ]Y

Anda dapat mencoba kedua solusi di sini dan di sini . Berikut penjelasan dari solusi kedua:

jb       # "\n".join(
 u       #  reduce(
  +G     #   lambda G,H: G+
   m     #    map(
    +d]H #     lambda d: d+[H],
    G    #     G),
  Q      #   input()
  ]Y     #   [[]]))

brainfuck, 94 byte

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

Diformat:

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

Mengharapkan input formulir 9,10,11tanpa baris baru, dan menampilkan subset dalam format yang sama, kadang-kadang dengan tanda koma. Baris pertama yang dicetak akan selalu kosong, menandakan set kosong.

Cobalah online.

Ide dasarnya adalah menempatkan sedikit di sebelah setiap elemen, lalu berulang kali menambah nomor biner saat mencetak subset yang sesuai sebelum setiap kenaikan. (Sedikit mengindikasikan apakah suatu elemen berada dalam subset.) Bit sentinel di sebelah kiri array digunakan untuk mengakhiri program. Versi ini sebenarnya menciptakan jumlah eksponensial sentinel untuk menghemat beberapa byte; solusi 99 byte yang lebih efisien yang hanya menggunakan satu sentinel dapat ditemukan dalam riwayat revisi.

Setiap bit dikodekan sebagai satu ditambah nilainya; yaitu, dapat berupa 1atau 2. Rekaman diletakkan dengan bit sebelum setiap elemen dan sel nol tunggal antara elemen yang berdekatan. Koma disertakan pada kaset untuk elemen non-final, jadi kita dapat dengan mudah mencetak elemen tanpa melakukan pekerjaan ekstra untuk menangani pembatas.

APL (Dyalog Classic) , 13 byte

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

Cobalah online!

Keluaran:

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

Ada garis kosong di akhir untuk mewakili set kosong.

Penjelasan:

⎕ input yang dievaluasi

⎕,¨⊂⊂⍬ tambahkan daftar angka kosong setelah setiap elemen

∘., Produk Cartesian

/ pengurangan (foldr)

⊃ mengungkapkan (perlu setelah pengurangan APL)

Pada titik ini hasilnya adalah larik n-dimensi 2-oleh -...- oleh-2, di mana n adalah panjang input.

, ratakan menjadi vektor

⍪ubah vektor menjadi matriks 2 ⁿ -by-1 tegak , sehingga setiap subset berada pada garis yang terpisah

Haskell , 80 78 byte

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

Cobalah online!

Jelly , 6 byte

ŒPŒṘ€Y

Cobalah online!

ŒṘ€Y adalah pemformatan string.

Python, 93 87 karakter

Python memudahkan pemformatan, karena input / output yang diperlukan cocok dengan format aslinya.
Hanya mendukung item yang literal Python (mis 1,2,'hello'. Tidak 1,2,hello).
Membaca input standar, bukan parameter.

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 karakter

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

Mendapatkan parameter panjang: /

R, 63

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

Di sini, vmerupakan vektor.

Penggunaan :

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 byte

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

Hasilkan semua vektor 0/1 selama input, kumpulkan indeks 1s dan gunakan untuk memilih elemen dari vektor input. Dalam praktek:

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

Ini agak liberal dengan persyaratan output, tapi saya pikir itu legal. Bagian yang paling dipertanyakan adalah bahwa set kosong akan diwakili dalam bentuk tipe dependen; !0adalah bagaimana K menunjukkan vektor numerik kosong:

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

Penjelasan

The (#x)#2membangun vektor 2selama input:

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

Ketika monadik !diterapkan ke vektor, itu adalah "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)

Kemudian kita menggunakan "di mana" ( &) pada setiap 'vektor ( ) untuk mengumpulkan indeksnya. Usus besar diperlukan untuk memisahkan antara bentuk monadik dan diad dari &:

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

Jika kita hanya menginginkan vektor kombinasi, kita akan selesai, tetapi kita perlu menggunakan ini sebagai indeks ke dalam set asli. Untungnya, operator pengindeksan K @dapat menerima struktur indeks yang kompleks dan akan menghasilkan hasil dengan bentuk yang sama:

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

Elegan, bukan?

Mathematica, 51

Lebih curang:

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

Gunakan dengan @{1,2,3}.

JavaScript (ES6), 68 byte

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 byte

⊇ᵘẉᵐ

Cobalah online!

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

Kombinasi metode Ruby Array (dari 1.9) [50 karakter]

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