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 powerset
jako:
powerset 1 2 3
Argumenty będą alfanumeryczne.
Zasady
- Brak bibliotek oprócz io
- Wyjścia nie trzeba zamawiać
- Powerset nie musi być przechowywany, tylko drukowany
- 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
)
- Końcowe ograniczniki są w porządku (np.
- 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.
code-golf
array-manipulation
combinatorics
beatgammit
źródło
źródło
lambda L:reduce(lambda r,x:r+[s+[x]for s in r],L,[[]])
.Odpowiedzi:
Matematyka 16
Kod
Subsets
pochodzi z Mathematica.Kod (bez kolumny) można zweryfikować na WolframAlpha . (Musiałem użyć nawiasów zamiast
@
; oznaczają to samo.Stosowanie
Ta metoda (55 znaków) wykorzystuje podejście sugerowane przez @ w0lf.
Awaria
Wygeneruj krotki złożone z
0
i1
o długościLength[s]
Pomnóż oryginalną listę (wektor) przez każdą krotkę:
Usuń
0
's.%
jest skrótem dla „poprzedniego wyniku”.% /. {0:> Sekwencja []}
Wyświetl w kolumnie:
źródło
s
i umieścić dane wejściowe na końcu wiersza?Subsets/*Column
tworzy anonimową funkcję, która pobiera listę i zwraca wyświetlanie w kolumnach.C,
118115Chociaż można zaoszczędzić około 20 znaków dzięki prostszemu formatowaniu, nadal nie uda się wygrać pod względem kodu golfowego.
Testowanie:
źródło
main(a,s)char**s;{...}
)f|=x&1<<i&&printf
jest krótszy niż?:
.x+=2
(i gdzies[0]
poszło). Naprawdę fajna sztuczka.GolfScript,
2218 znakówKolejna próba w GolfScript z zupełnie innym algorytmem. Format wejściowy jest taki sam, jak w przypadku odpowiedzi w0lf. ( test online )
źródło
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.
Na przykład
źródło
awk (82)
zakładamy zapisany w pliku powerset.awk, użycie
ps, jeśli twój awk nie ma funkcji i (), zamień go na,
int(i/(2^j))%2
ale dodaje dwa do liczby.źródło
(2^j)
->2^j
oszczędza 2 bajty;.awk
plik działa również bez końca\n
, dzięki czemu można zgolić kolejny bajt.JavaScript, 98
Niestety, spory kawałek wydaje się na formatowanie wyjściowe.
Wkład
Pobiera tablicę JavaScript. (np. [1,2,3])
Wydajność
źródło
Python (
7470 znaków)dla danych wejściowych jako
1,2,3
lub[1,2,3]
wyjściowych jest:źródło
[a[0]]
=a[:1]
1,2,3
a[:1]
nie działa. krotka + lista niedozwolona. Istnieje lepsze rozwiązaniei,*a=a
i,*a=a
Python 3? To nie działa na moim 2.7.1.Pyton
7067 bajtówDane wejściowe są pobierane w taki sam sposób, jak w przypadku rozwiązania ugorena . Przykładowe I / O:
źródło
def p(a,*v)
i wtedyp(a[i:],n,*v)
. Dane wyjściowe stają się nieco brzydsze, ale nadal są OK.J, 19 znaków
Boks ascii na wyjściu jest wywoływany
boxing
i zapewnia zbieranie heterogenów (tutaj dla różnych długości tablic).źródło
Golfscript 48
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:
Test online
Program można przetestować online tutaj .
źródło
Haskell (96)
Jeśli importowanie
Control.Monad
nie jest dozwolone, staje się to 100 znaków:źródło
Mathematica 53
źródło
APL (26)
Czyta dane wejściowe z klawiatury, ponieważ nie ma
argv
odpowiednika.Stosowanie:
Wyjaśnienie:
T←⎕
: wczytaj dane wejściowe, zapisz wT
M←⍴T
: długość sklepuT
wM
(M/2)⊤⍳2*M
: generuj wzorce bitów dla1
upto2^M
przy użyciuM
bitów.↓⍉
: podziel macierz, aby każdy wzór bitowy był osobny(/∘T)¨
: dla każdego wzorca bitowego wybierz te elementy podrzędne zT
.↑⍕¨
: 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).źródło
Scala, 81
źródło
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ć.
źródło
C # 164
Człowieku, to jest trudne w C #!
źródło
Python 2, 64 bajty
Za pomocą danych oddzielonych przecinkami:
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:
A oto jeden bez niego:
Możesz wypróbować oba rozwiązania tutaj i tutaj . Oto wyjaśnienie drugiego rozwiązania:
źródło
pieprzenie mózgu, 94 bajty
Sformatowany:
Oczekuje wprowadzenia formularza
9,10,11
bez 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ć
1
albo2
. 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.źródło
APL (Dyalog Classic) , 13 bajtów
Wypróbuj online!
Wydajność:
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 n -o-1, tak aby każdy podzbiór znajdował się w osobnej liniiźródło
Haskell,
8078 bytesTry it online!
źródło
Jelly, 6 bytes
Try it online!
ŒṘ€Y
are string formatting.źródło
Python,
9387 charsPython makes formatting simple, because the required input/output matches its native format.
Only supports items which are Python literals (e.g.
1,2,'hello'
, not1,2,hello
).Reads standard input, not parameters.
źródło
print f(input())
shorterlist
can indeed be removed (if also replacinf[[]]
with[()]
.print'\n'.join(f(input()))
saves two charactersf()
contains tuples, not strings.Ruby, 39
źródło
Haskell 89 chars
Getting parameters is long :/
źródło
map(x:)(p y)++p y
and yet two more chars above that with[(x:),id]<*>p y
. Apparently<*>
is in the Prelude now. (filterM
isn't).R, 63
Here,
v
represents a vector.Usage:
źródło
K, 14 bytes
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:
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:Explanation
The
(#x)#2
builds a vector of2
as long as the input:When monadic
!
is applied to a vector, it is "odometer":Then we use "where" (
&
) on each ('
) vector to gather its indices. The colon is necessary to disambiguate between the monadic and dyadic form of&
: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:Elegant, no?
źródło
{x@&:'+!(#x)#2}
. Unrelated: a shorter equivalent of(#x)#2
is2|~x
.Mathematica, 51
More cheating:
Use with
@{1,2,3}
.źródło
JavaScript (ES6), 68 bytes
Demo
Show code snippet
źródło
alert
?Brachylog, 4 bytes
Try it online!
źródło
Ruby Array method combination (from 1.9 ) [50 chars]
źródło