Definición del problema

Imprima el conjunto de potencia de un conjunto dado. Por ejemplo:

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

Cada elemento debe imprimirse en una línea separada, por lo que el ejemplo anterior se imprimirá como:

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

Código de ejemplo (en D, ejemplo de python aquí ):

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

Entrada

Los elementos se pasarán como argumentos. Por ejemplo, el ejemplo proporcionado anteriormente se pasaría a un programa llamado powersetcomo:

powerset 1 2 3

Los argumentos serán alfanuméricos.

Reglas

1. No hay bibliotecas además de io
2. La salida no tiene que ser ordenada
3. Powerset no tiene que ser almacenado, solo impreso
4. Los elementos del conjunto deben estar delimitados (por ejemplo 1,2,3, [1,2,3]y ['1','2','3']son aceptables, pero 123no lo son
   • Los delimitadores finales están bien (p 1,2,3, == 1,2,3. Ej. )
5. El mejor se determina en función del número de bytes

La mejor solución se decidirá no menos de 10 días después de la primera presentación.

Mathematica 16

Código

Subsets Es nativo de Mathematica.

Column@Subsets@s

El código (sin columna) se puede verificar en WolframAlpha . (Tuve que usar corchetes en lugar de @; significan lo mismo.

Uso

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

Este método (55 caracteres) utiliza el enfoque sugerido por @ w0lf.

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

Descompostura

Genera las tuplas, compuestas de 0y 1's de longitudLength[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}}

Multiplique la lista original (vector) por cada tupla:

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

Eliminar los 0's. %es la abreviatura de "la salida anterior".

% /. {0:> Secuencia []}

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

Mostrar en columna:

C, 118 115

Si bien puede guardar aproximadamente 20 caracteres con un formato más simple, de todos modos no va a ganar en términos de código de 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;
}

Pruebas:

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

GolfScript, 22 18 caracteres

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

Otro intento en GolfScript con un algoritmo completamente diferente. El formato de entrada es el mismo que con la respuesta de w0lf. ( prueba en línea )

GolfScript (43 caracteres)

Esto puede parecer bastante largo, pero es la primera solución para seguir la especificación: la entrada proviene de argumentos de la línea de comandos y la salida está delimitada por una nueva línea.

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

P.ej

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

asumir guardado en el archivo powerset.awk, uso

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

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

ps si su awk no tiene la función y (), reemplácela con int(i/(2^j))%2pero agrega dos a la cuenta.

JavaScript, 98

Lamentablemente, se gasta una buena parte en el formato de salida.

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

Entrada

Toma una matriz de JavaScript. (por ejemplo, [1,2,3])

Salida

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

Python ( 74 70 caracteres)

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

para entrada como 1,2,3o [1,2,3], la salida es:

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

La entrada se toma de la misma manera que para la solución de ugoren . Muestra de E / S:

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

J, 19 caracteres

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

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

El boxeo ascii en la salida se llama boxingy proporciona una colección heterogénea (para diferentes longitudes de matrices aquí).

Golfscript 48

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

Este programa utiliza las representaciones binarias de números del 0 al largo (entrada) para generar elementos de conjunto de potencia.

Entrada

El formato de entrada es la Golfscript formato de matriz (ejemplo: [1 2 3])

Salida

La salida es una colección de matrices separadas por líneas nuevas, que representan el conjunto de potencia. Ejemplo:

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

Prueba en línea

El programa se puede probar en línea aquí .

Haskell (96)

Control de importación.
Sistema de importación.
main = getArgs >> = mapM print.filterM (\ _-> [False ..])

Si Control.Monadno se permite importar , esto se convierte en 100 caracteres:

Sistema de importación.
main = getArgs >> = mapM print.p
pz = caso z de {[] -> [[]]; x: y-> p y ++ mapa (x:) (py)}

Mathematica 53

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

APL (26)

Lee la entrada del teclado porque no hay argvequivalente.

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

Uso:

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

Explicación:

• T←⎕: leer entrada, almacenar en T
• M←⍴T: longitud de la tienda de TenM
• (M/2)⊤⍳2*M: genera los patrones de bits para usar 1hasta2^MM bits.
• ↓⍉: divide la matriz para que cada patrón de bits esté separado
• (/∘T)¨: para cada patrón de bits, seleccione los subelementos de T .
• ↑⍕¨: para la salida, obtenga la representación de cadena de cada elemento (para que se llene usando espacios en blanco y no ceros), y formatee como una matriz (para que cada elemento esté en su propia línea).

Scala, 81

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

JavaScript ( ES6 ) 76

Parcialmente copiado de este: /codegolf//a/51502/21348

Usando un mapa de bits, por lo que está limitado a no más de 32 elementos.

Ejecute el fragmento en Firefox para probar.

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

Hombre, esto es difícil en 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

Usando una entrada separada por comas:

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

Pyth, 4 bytes (usando incorporado) o 14 bytes (sin)

Como señaló @Jakube en los comentarios, Pyth es demasiado reciente para esta pregunta. Aún así, aquí hay una solución que utiliza el operador de conjunto de potencia incorporado de Pyth:

jbyQ

Y aquí hay uno sin él:

jbu+Gm+d]HGQ]Y

Puedes probar ambas soluciones aquí y aquí . Aquí hay una explicación de la segunda solución:

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

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

Formateado:

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

Espera la entrada del formulario 9,10,11sin una nueva línea final y genera subconjuntos en el mismo formato, a veces con una coma final. La primera línea impresa siempre estará vacía, lo que significa el conjunto vacío.

Pruébalo en línea.

La idea básica es colocar un bit al lado de cada elemento, luego incrementar repetidamente el número binario mientras imprime el subconjunto correspondiente antes de cada incremento. (Un bit indica si un elemento está en el subconjunto). Se utiliza un bit centinela a la izquierda de la matriz para terminar el programa. Esta versión en realidad crea un número exponencial de centinelas para guardar algunos bytes; En el historial de revisiones se puede encontrar una solución más eficiente de 99 bytes que solo usa un centinela.

Cada bit está codificado como uno más su valor; es decir, puede ser 1o 2. La cinta se presenta con el bit antes de cada elemento y una sola celda cero entre elementos adyacentes. La coma se incluye en la cinta para elementos no finales, por lo que podemos imprimir convenientemente elementos sin hacer ningún trabajo adicional para manejar delimitadores.

APL (Dyalog Classic) , 13 bytes

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

Pruébalo en línea!

Salida:

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

Hay una línea en blanco al final para representar el conjunto vacío.

Explicación:

⎕ entrada evaluada

⎕,¨⊂⊂⍬ agregar una lista numérica vacía después de cada elemento

∘., producto cartesiano

/ reducción (foldr)

⊃ revelar (necesario después de la reducción de APL)

En este punto, el resultado es una matriz n-dimensional de 2 por -...- por-2, donde n es la longitud de la entrada.

, aplanar en un vector

⍪convertir el vector en una matriz vertical 2 ⁿ -by-1, de modo que cada subconjunto esté en una línea separada

Haskell , 80 78 bytes

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

Pruébalo en línea!

Jalea , 6 bytes

ŒPŒṘ€Y

Pruébalo en línea!

ŒṘ€Y son formato de cadena.

Python, 93 87 caracteres

Python simplifica el formateo, porque la entrada / salida requerida coincide con su formato nativo.
Solo admite elementos que son literales de Python (por ejemplo 1,2,'hello', no 1,2,hello).
Lee entradas estándar, no parámetros.

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 caracteres

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

Obtener parámetros es largo: /

R, 63

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

Aquí, vrepresenta un vector.

Uso :

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}

Genere todos los vectores 0/1 siempre que la entrada, recopile los índices de 1s y utilícelos para seleccionar elementos del vector de entrada. En la práctica:

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

Esto es un poco liberal con los requisitos de salida, pero creo que es legal. La parte más cuestionable es que el conjunto vacío se representará en una forma dependiente del tipo; !0es cómo K denota un vector numérico vacío:

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

Explicación

El (#x)#2construye un vector 2tan largo como la entrada:

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

Cuando !se aplica monádico a un vector, es "odómetro":

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

Luego usamos "where" ( &) en cada ( ') vector para recopilar sus índices. El colon es necesario para desambiguar entre la forma monádica y la diádica de &:

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

Si solo quisiéramos combinar vectores, estaríamos listos, pero necesitamos usarlos como índices en el conjunto original. Afortunadamente, el operador de indexación de K @puede aceptar una estructura compleja de índices y producirá un resultado con la misma forma:

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

Elegante, no?

Mathematica, 51

Más trampas:

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

Usar con @{1,2,3}.

JavaScript (ES6), 68 bytes

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

Manifestación

let f =

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

f([1,2,3])

Brachylog , 4 bytes

⊇ᵘẉᵐ

Pruébalo en línea!

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

Combinación de métodos de Ruby Array (desde 1.9) [50 caracteres]

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