Problem Definition

Drucken Sie das Powerset eines bestimmten Sets aus. Beispielsweise:

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

Jedes Element muss in einer separaten Zeile gedruckt werden, sodass das obige Beispiel wie folgt gedruckt wird:

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

Beispielcode (in D, Python-Beispiel hier ):

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

Eingang

Elemente werden als Argumente übergeben. Das oben angegebene Beispiel wird beispielsweise an ein Programm mit dem Namen powerset:

powerset 1 2 3

Argumente sind alphanumerisch.

Regeln

1. Keine Bibliotheken außer io
2. Die Ausgabe muss nicht bestellt werden
3. Powerset muss nicht gespeichert, sondern nur gedruckt werden
4. Elemente in der Menge begrenzt werden muss ( zum Beispiel 1,2,3, [1,2,3]und ['1','2','3']akzeptabel sind, aber 123sind nicht
   • Nachgestellte Trennzeichen sind in Ordnung (zB 1,2,3, == 1,2,3)
5. Der beste Wert wird anhand der Anzahl der Bytes ermittelt

Die beste Lösung wird mindestens 10 Tage nach der ersten Einreichung entschieden.

Mathematica 16

Code

Subsets stammt aus Mathematica.

Column@Subsets@s

Der Code (ohne Spalte) kann auf WolframAlpha überprüft werden . (Ich musste stattdessen Klammern verwenden @; sie bedeuten dasselbe.

Verwendung

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

Diese Methode (55 Zeichen) verwendet den von @ w0lf vorgeschlagenen Ansatz.

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

Nervenzusammenbruch

Generieren Sie die Tupel, die aus 0und 1s der Länge bestehenLength[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}}

Multiplizieren Sie die ursprüngliche Liste (Vektor) mit jedem Tupel:

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

Löschen Sie die 0. %ist die Abkürzung für "die vorhergehende Ausgabe".

% /. {0:> Sequenz []}

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

Anzeige in Spalte:

C 118, 115

Zwar lassen sich mit einer einfacheren Formatierung ca. 20 Zeichen einsparen, aber Code-Golf gewinnt in keiner Weise.

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

Testen:

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

GolfScript, 22 18 Zeichen

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

Ein weiterer Versuch in GolfScript mit einem völlig anderen Algorithmus. Das Eingabeformat ist dasselbe wie bei der Antwort von w0lf. ( Online-Test )

GolfScript (43 Zeichen)

Dies mag recht lang erscheinen, aber es ist die erste Lösung, die der Spezifikation folgt: Die Eingabe erfolgt über Befehlszeilenargumente, und die Ausgabe wird durch Zeilenumbrüche getrennt.

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

Z.B

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

Nehmen Sie an, dass in der Datei powerset.awk die Verwendung gespeichert ist

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

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

ps Wenn Ihre awk nicht über die Funktion und () verfügt, ersetzen Sie sie durch int(i/(2^j))%2, addieren aber zwei zur Zählung.

JavaScript, 98

Leider wird ein guter Teil für die Ausgabeformatierung ausgegeben.

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

Eingang

Nimmt ein JavaScript-Array auf. (zB [1,2,3])

Ausgabe

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

Python ( 74-70 Zeichen)

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

Für die Eingabe als 1,2,3oder [1,2,3]ist die Ausgabe:

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

Python 70 67 Bytes

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

Die Eingabe erfolgt auf die gleiche Weise wie für die ugorensche Lösung . Beispiel I / O:

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

J, 19 Zeichen

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

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

Das ASCII-Boxing in der Ausgabe wird aufgerufen boxingund bietet eine heterogene Sammlung (hier für unterschiedliche Länge von Arrays).

Golfscript 48

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

Dieses Programm verwendet die binären Darstellungen von Zahlen von 0 bis Länge (Eingabe), um Powerset-Elemente zu generieren.

Eingang

Das Eingabeformat ist das Golfscript Array - Format (Beispiel [1 2 3])

Ausgabe

Die Ausgabe ist eine Sammlung von Arrays, die durch Zeilenumbrüche getrennt sind und die eingestellte Leistung darstellen. Beispiel:

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

Online-Test

Das Programm kann hier online getestet werden .

Haskell

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

Wenn das Importieren Control.Monadnicht erlaubt ist, werden dies 100 Zeichen:

System.Environment importieren
main = getArgs >> = mapM print.p
pz = Fall z von {[] -> [[]]; x: y-> p y ++ map (x:) (py)}

Mathematica 53

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

APL (26)

Liest Eingaben von der Tastatur, da es keine argvEntsprechung gibt.

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

Verwendung:

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

Erläuterung:

• T←⎕: Eingabe lesen, speichern in T
• M←⍴T: Speicherlänge von TinM
• (M/2)⊤⍳2*M: Erzeugt die Bitmuster für 1die 2^MVerwendung von MBits.
• ↓⍉: Teilen Sie die Matrix so, dass jedes Bitmuster getrennt ist
• (/∘T)¨: Wählen Sie für jedes Bitmuster die Unterelemente aus T.
• ↑⍕¨: Rufen Sie für die Ausgabe die Zeichenfolgendarstellung jedes Elements ab (damit es mit Leerzeichen und nicht mit Nullen gefüllt wird) und formatieren Sie es als Matrix (damit sich jedes Element in einer eigenen Zeile befindet).

Scala, 81

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

JavaScript ( ES6 ) 76

Teilweise kopiert von diesem: /codegolf//a/51502/21348

Die Verwendung einer Bitmap ist daher auf maximal 32 Elemente beschränkt.

Führen Sie das Snippet zum Testen in Firefox aus.

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

Mann das ist schwer in 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 Bytes

Kommagetrennte Eingabe verwenden:

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

Pyth, 4 Bytes (mit eingebautem) oder 14 Bytes (ohne)

Wie @Jakube in den Kommentaren angemerkt hat, ist Pyth für diese Frage zu aktuell. Hier noch eine Lösung mit Pyths eingebautem Powerset-Operator:

jbyQ

Und hier ist eine ohne es:

jbu+Gm+d]HGQ]Y

Sie können beide Lösungen hier und hier ausprobieren . Hier ist eine Erklärung der zweiten Lösung:

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 Bytes

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

Formatiert:

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

Erwartet die Eingabe des Formulars 9,10,11ohne abschließende Zeilenumbrüche und gibt Teilmengen im gleichen Format aus, manchmal mit einem abschließenden Komma. Die erste gedruckte Zeile ist immer leer und kennzeichnet den leeren Satz.

Probieren Sie es online aus.

Die Grundidee ist, ein Bit neben jedes Element zu setzen und dann die Binärzahl wiederholt zu erhöhen, während die entsprechende Teilmenge vor jedem Inkrement gedruckt wird. (Ein Bit zeigt an, ob sich ein Element in der Untermenge befindet.) Ein Sentinel-Bit links vom Array wird zum Beenden des Programms verwendet. Diese Version erstellt tatsächlich eine exponentielle Anzahl von Sentinels, um einige Bytes zu sparen. Eine effizientere 99-Byte-Lösung, die nur einen Sentinel verwendet, finden Sie im Revisionsverlauf.

Jedes Bit wird als Eins plus seinem Wert codiert. dh es kann entweder 1oder sein 2. Das Band wird mit dem Bit vor jedem Element und einer einzelnen Nullzelle zwischen benachbarten Elementen ausgelegt. Das Komma ist auf dem Band für nicht endgültige Elemente enthalten, sodass wir bequem nur Elemente drucken können, ohne zusätzliche Arbeit im Umgang mit Begrenzern zu leisten.

APL (Dyalog Classic) , 13 Byte

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

Probieren Sie es online!

Ausgabe:

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

Am Ende befindet sich eine leere Zeile, die die leere Menge darstellt.

Erläuterung:

⎕ ausgewertete Eingabe

⎕,¨⊂⊂⍬ Fügen Sie nach jedem Element eine leere numerische Liste hinzu

∘., kartesisches Produkt

/ Reduktion (Foldr)

⊃ offenlegen (notwendig nach APL-Reduktion)

Zu diesem Zeitpunkt ist das Ergebnis ein n-dimensionales 2 × ... × 2-Array, wobei n die Länge der Eingabe ist.

, Abflachen in einen Vektor

⍪Verwandeln Sie den Vektor in eine aufrechte 2 ^n- by-1-Matrix, sodass sich jede Teilmenge in einer separaten Zeile befindet

Haskell , 80 78 Bytes

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

Probieren Sie es online!

Gelee , 6 Bytes

ŒPŒṘ€Y

Probieren Sie es online!

ŒṘ€Y sind Zeichenfolgenformatierungen.

Python, 93 87 Zeichen

Python vereinfacht die Formatierung, da die erforderliche Eingabe / Ausgabe dem nativen Format entspricht.
Unterstützt nur Elemente, die Python-Literale sind (z . B. 1,2,'hello'nicht 1,2,hello).
Liest Standardeingabe, keine 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

Rubin, 39

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

Haskell 89 Zeichen

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

Parameter zu bekommen ist lang: /

R 63

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

Hier, v stellt einen Vektor.

Verwendung :

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}

Generieren Sie alle 0/1-Vektoren so lange wie die Eingabe, erfassen Sie die Indizes von 1s und verwenden Sie diese, um Elemente aus dem Eingabevektor auszuwählen. In der Praxis:

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

Dies ist ein bisschen liberal mit den Ausgabeanforderungen, aber ich denke, es ist legal. Der fragwürdigste Teil ist, dass die leere Menge in einer typabhängigen Form dargestellt wird. !0So bezeichnet K einen leeren numerischen Vektor:

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

Erläuterung

Das erzeugt (#x)#2einen Vektor, der 2so lang ist wie die Eingabe:

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

Wenn monadisch !auf einen Vektor angewendet wird, handelt es sich um einen "Kilometerzähler":

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

Dann verwenden wir "where" ( &) für jeden ( ') Vektor, um seine Indizes zu erfassen. Der Doppelpunkt ist notwendig, um zwischen der monadischen und der dyadischen Form von zu unterscheiden &:

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

Wenn wir nur Kombinationsvektoren wollten, wären wir fertig, aber wir müssen diese als Indizes in der ursprünglichen Menge verwenden. Glücklicherweise kann der Indexierungsoperator von K @eine komplexe Struktur von Indizes akzeptieren und ein Ergebnis mit der gleichen Form erzeugen:

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

Elegant, nein?

Mathematica, 51

Mehr Betrug:

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

Verwenden Sie mit @{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 Bytes

⊇ᵘẉᵐ

Probieren Sie es online!

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

Ruby Array Methodenkombination (ab 1.9) [50 Zeichen]

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