Определение проблемы

Распечатайте powerset данного набора. Например:

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

Каждый элемент должен быть напечатан в отдельной строке, поэтому приведенный выше пример будет напечатан так:

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

Пример кода (в D, пример 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);
}

вход

Элементы будут переданы в качестве аргументов. Например, приведенный выше пример будет передан программе, которая называется powerset:

powerset 1 2 3

Аргументы будут буквенно-цифровыми.

правила

1. Нет библиотек, кроме IO
2. Выход не должен быть заказан
3. Powerset не должен быть сохранен, только напечатан
4. Элементы в наборе должны быть разделены (например 1,2,3, [1,2,3]и ['1','2','3']являются приемлемыми, но 123не
   • Конечные разделители в порядке (например 1,2,3, == 1,2,3)
5. Лучший определяется на основе количества байтов

Лучшее решение будет принято не позднее, чем через 10 дней после первого представления.

Mathematica 16

Код

Subsets родом из Mathematica.

Column@Subsets@s

Код (без столбца) можно проверить на WolframAlpha . (Мне пришлось использовать скобки вместо @; они означают одно и то же.

использование

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

Этот метод (55 символов) использует подход, предложенный @ w0lf.

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

Сломать

Генерация кортежей, состоящих из 0и 1длиныLength[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}}

Умножьте исходный список (вектор) на каждый кортеж:

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

Удалить 0. %сокращение от «предыдущий вывод».

% /. {0:> Последовательность []}

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

Показать в столбце:

С, 118 115

Несмотря на то, что вы можете сэкономить около 20 символов с более простым форматированием, вы все равно не выиграете в условиях код-гольфа

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

Тестирование:

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

GolfScript, 22 18 символов

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

Еще одна попытка в GolfScript с совершенно другим алгоритмом. Формат ввода такой же, как и в ответе w0lf. ( онлайн тест )

GolfScript (43 символа)

Это может показаться довольно длинным, но это первое решение, которое следует спецификации: входные данные основаны на аргументах командной строки, а выходные - разделены новой строкой.

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

Например

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

Предположим, сохранены в файле powerset.awk, использование

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

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

ps, если ваш awk не имеет функции and (), замените его на, int(i/(2^j))%2но добавьте два к счетчику.

JavaScript, 98

К сожалению, хороший кусок тратится на форматирование вывода.

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

вход

Принимает массив JavaScript. (например, [1,2,3])

Выход

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

Питон ( 74 70 символов)

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

для ввода как 1,2,3или [1,2,3], выход:

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

Python 70 67 байт

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

Ввод принимается так же, как и для решения Угорена . Пример ввода / вывода:

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

J, 19 символов

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

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

Бокс ascii в выводе называется boxingи обеспечивает сбор гетерогена (для различной длины массивов здесь).

Golfscript 48

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

Эта программа использует двоичные представления чисел от 0 до длины (входные) для генерации элементов powerset.

вход

Входной формат является Golfscript формат массива (пример: [1 2 3])

Выход

Вывод представляет собой набор массивов, разделенных символами новой строки, представляющих набор мощности. Пример:

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

Онлайн тест

Программу можно протестировать онлайн здесь .

Хаскелл (96)

импорт Control.Monad
импорт System.Environment
main = getArgs >> = mapM print.filterM (\ _-> [False ..])

Если импорт Control.Monadне разрешен, это становится 100 символами:

импорт System.Environment
main = getArgs >> = mapM print.p
pz = case z of {[] -> [[]]; x: y-> p y ++ map (x:) (py)}

Mathematica 53

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

APL (26)

Читает ввод с клавиатуры, потому что нет argvэквивалента.

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

Использование:

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

Объяснение:

• T←⎕: читать ввод, хранить в T
• M←⍴T: хранить длину TвM
• (M/2)⊤⍳2*M: Генерировать битовые шаблоны для 1ДО , 2^Mиспользуя Mбиты.
• ↓⍉: разделить матрицу так, чтобы каждая битовая комбинация была отдельной
• (/∘T)¨: для каждого шаблона битов выберите эти подпункты из T.
• ↑⍕¨: для вывода получите строковое представление каждого элемента (чтобы он заполнялся с использованием пробелов, а не нулей) и отформатировали в виде матрицы (чтобы каждый элемент находился на отдельной строке).

Скала, 81

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

JavaScript ( ES6 ) 76

Частично скопировано с этого: /codegolf//a/51502/21348

Использование растрового изображения, поэтому оно ограничено не более чем 32 элементами.

Запустите фрагмент в Firefox для проверки.

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

Человек это трудно в 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 байта

Использование ввода через запятую:

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

Pyth, 4 байта (используя встроенный) или 14 байтов (без)

Как отметил @Jakube в комментариях, Pyth слишком свеж для этого вопроса. И все же вот решение, использующее встроенный оператор питания Pyth:

jbyQ

И вот один без него:

jbu+Gm+d]HGQ]Y

Вы можете попробовать оба решения здесь и здесь . Вот объяснение второго решения:

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

мозговой трах, 94 байта

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

отформатирован:

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

Ожидает ввод формы 9,10,11без завершающей строки и выводит подмножества в том же формате, иногда с запятой. Первая напечатанная строка всегда будет пустой, что означает пустой набор.

Попробуйте онлайн.

Основная идея состоит в том, чтобы поместить бит рядом с каждым элементом, затем многократно увеличивать двоичное число, печатая соответствующее подмножество перед каждым увеличением. (Бит указывает, находится ли элемент в подмножестве.) Бит стража слева от массива используется для завершения программы. Эта версия на самом деле создает экспоненциальное количество часовых, чтобы сохранить несколько байтов; более эффективное 99-байтовое решение, в котором используется только один страж, можно найти в истории изменений.

Каждый бит кодируется как один плюс его значение; то есть, это может быть 1или 2. Лента размещается с битом перед каждым элементом и одной нулевой ячейкой между соседними элементами. Запятая включена в ленту для не конечных элементов, поэтому мы можем просто печатать элементы, не выполняя никакой дополнительной работы с разделителями.

APL (Dyalog Classic) , 13 байтов

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

Попробуйте онлайн!

Выход:

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

В конце есть пустая строка, представляющая пустой набор.

Объяснение:

⎕ оцененный вклад

⎕,¨⊂⊂⍬ добавить пустой числовой список после каждого элемента

∘., Декартово произведение

/ уменьшение (сгиб)

⊃ раскрыть (необходимо после снижения APL)

На этом этапе результат представляет собой n-мерный массив размером 2 на -...- на-2, где n - длина входных данных.

, сплющить в вектор

⍪превратить вектор в прямую 2 ^n- by-1 матрицу, чтобы каждое подмножество находилось на отдельной строке

Haskell , 80 78 байт

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

Попробуйте онлайн!

Желе , 6 байт

ŒPŒṘ€Y

Попробуйте онлайн!

ŒṘ€Y форматирование строк

Питон, 93 87 символов

Python упрощает форматирование, поскольку требуемый ввод / вывод соответствует его собственному формату.
Поддерживает только те элементы, которые являются литералами Python (например 1,2,'hello', нет 1,2,hello).
Читает стандартный ввод, а не параметры.

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

Руби, 39

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

Haskell 89 символов

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

Получение параметров долго: /

R, 63

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

Здесь vпредставляет вектор.

Использование :

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)

К, 14 байтов

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

Сгенерируйте все 0/1 векторов за время ввода, соберите индексы 1 с и используйте их для выбора элементов из входного вектора. На практике:

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

Это немного либерально с требованиями к выходу, но я думаю, что это законно. Наиболее сомнительной является то, что пустой набор будет представлен в виде, зависящем от типа; !0как K обозначает пустой числовой вектор:

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

объяснение

(#x)#2Строит вектор 2тех пор , пока на входе:

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

Когда !к вектору применяется монадика, это «одометр»:

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

Затем мы используем «где» ( &) для каждого 'вектора ( ), чтобы собрать его индексы. Толстая кишка необходима для устранения неоднозначности между монадической и диадической формой &:

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

Если бы мы просто хотели комбинированные векторы, мы бы сделали, но нам нужно использовать их как индексы в исходном наборе. К счастью, оператор индексации K @может принять сложную структуру индексов и даст результат такой же формы:

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

Элегантно, нет?

Математика, 51

Больше обмана:

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

Используйте с @{1,2,3}.

JavaScript (ES6), 68 байт

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

демонстрация

let f =

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

f([1,2,3])

Брахилог , 4 байта

⊇ᵘẉᵐ

Попробуйте онлайн!

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

Комбинация методов Ruby Array (от 1.9) [50 символов]

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