Generate all combinations of given list of elements, sorted

Question

Make a code that takes a list and a number as input, and generates all possible combinations with the length of the number. For example, with the list {0,1} and the number 2:

Your program doesn't have to expect characters twice or more often in the list, such as {0,0,0,0,0,1,1,5,5}

Make sure you print the combinations out sorted, in the order of the list:

With the list {0,1} and the number 5 (generated by some of my code, which is a way too long to win):

But with the list {1,0} and the number 2:

As you can see, reversed list means reversed order.

Take a look at the structure, it's like a tree.

This is code-golf, so the shortest code in bytes wins!

@Jarko I'd assume the tuples of indices of the input are sorted in the output — Luis Mendo, Dec 10, 2016 at 19:36
@brad, the default answer is yes unless OP has said something else. — Stewie Griffin, Dec 10, 2016 at 21:51
I don't understand... what's wrong with using my own name as a username? — Stewie Griffin, Dec 11, 2016 at 12:20

Jonathan Allan · Accepted Answer · 2016-12-10 20:03:06Z

17

Jelly, 1 byte

ṗ

TryItOnline

Cartesian power built-in atom, as a dyadic link with left argument the items and right argument the count, or as a full program with first argument the items and second argument the count.

answered Dec 10, 2016 at 20:03

Jonathan Allan

106k7 gold badges63 silver badges275 bronze badges

1

\$\begingroup\$ One byte ! That solved it ! \$\endgroup\$
– Luatic
Dec 10, 2016 at 23:01
5

\$\begingroup\$ You know what, I'm gonna submit a ZERO byte answer! In JAVA! How do you like that, huh? :) (Seriously, though. Nice golfing.) \$\endgroup\$
– AAM111
Dec 11, 2016 at 0:37

Add a comment |

nimi · Accepted Answer · 2016-12-10 19:58:13Z

9

Haskell, 20 bytes

(mapM id.).replicate

Usage exaple:

*Main> ( (mapM id.).replicate )  2 "01" 
["00","01","10","11"]
*Main> ( (mapM id.).replicate )  2 "10" 
["11","10","01","00"]

replicate makes n copies of the 2nd parameter and mapM id builds the combinations. Btw, mapM id is the same as sequence, but 1 byte less.

answered Dec 10, 2016 at 19:58

nimi

35.8k4 gold badges34 silver badges96 bronze badges

Add a comment |

Luis Mendo · Accepted Answer · 2016-12-10 19:32:30Z

8

MATL, 2 bytes

Z^

Cartesian power builtin...

Try it online!

answered Dec 10, 2016 at 19:32

Luis Mendo

104k9 gold badges133 silver badges370 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

6

Pyth, 2 bytes

^F

A program that takes input in the form list,number and prints a list of lists.

Test suite

How it works

^F   Program. Input: Q
^FQ  Implicit input fill
 F   Fold
^    repeated Cartesian power
  Q  over Q
     Implicitly print

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Dec 10, 2016 at 19:56

TheBikingViking

3,70410 silver badges22 bronze badges

\$\begingroup\$ this seems to solve it, but probably somebody else is able to do this with one byte ? \$\endgroup\$
– Luatic
Dec 10, 2016 at 23:00
\$\begingroup\$ yes, somebody else won(jelly, one byte) but nice solution, anyway \$\endgroup\$
– Luatic
Dec 11, 2016 at 19:26

Add a comment |

Brad Gilbert b2gills · Accepted Answer · 2016-12-10 20:41:51Z

Perl 6, 15 bytes

{[X] @^a xx$^b}

Explanation:

{[X] @^a xx$^b}

{             } # bare block lambda

     @^a        # declare first parameter as Positional
           $^b  # declare second parameter
         xx     # list repeat ｢@a｣, ｢$b｣ times

# at this point given ｢ (0,1), 5 ｣
# ((0 1) (0 1) (0 1) (0 1) (0 1))

 [ ]            # list reduce
  X             #    using cross meta-operator

# results in a list of lists
# ((0 0 0 0 0)
#  (0 0 0 0 1)
#  (0 0 0 1 0)
#  (0 0 0 1 1)
#  (0 0 1 0 0)
#  (0 0 1 0 1)
#  ...
#  (1 1 1 1 1))

say {[X] $^a xx$^b}( (0,1), 2 ); # ((0 0) (0 1) (1 0) (1 1))
say {[X] $^a xx$^b}( (1,0), 2 ); # ((1 1) (1 0) (0 1) (0 0))
say {[X] $^a xx$^b}( (0,1,2), 2 );
# ((0 0) (0 1) (0 2) (1 0) (1 1) (1 2) (2 0) (2 1) (2 2))

put {[X] $^a xx$^b}( (0,1), 5 )».join;
# 00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111

If they ever upgrade to a release of Rakudo from after the official release of Perl 6 you will be able to run this at Ideone. — Brad Gilbert b2gills, Dec 10, 2016 at 21:30

ETHproductions · Accepted Answer · 2016-12-10 22:14:17Z

5

JavaScript (Firefox 30+), 55 bytes

f=(a,n)=>n?[for(b of a)for(c of f(a,n-1))[b,...c]]:[[]]

I'm 99% certain recursion is the best way to go about this in JavaScript.

answered Dec 10, 2016 at 22:14

ETHproductions

50k6 gold badges93 silver badges239 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

Mathematica, 6 bytes

Tuples

Still worse than Jelly :(

Usage

Tuples[{0, 1}, 5]

{{0, 0, 0, 0, 0}, {0, 0, 0, 0, 1}, {0, 0, 0, 1, 0}, {0, 0, 0, 1, 1}, {0, 0, 1, 0, 0}, {0, 0, 1, 0, 1}, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 1}, {0, 1, 0, 0, 0}, {0, 1, 0, 0, 1}, {0, 1, 0, 1, 0}, {0, 1, 0, 1, 1}, {0, 1, 1, 0, 0}, {0, 1, 1, 0, 1}, {0, 1, 1, 1, 0}, {0, 1, 1, 1, 1}, {1, 0, 0, 0, 0}, {1, 0, 0, 0, 1}, {1, 0, 0, 1, 0}, {1, 0, 0, 1, 1}, {1, 0, 1, 0, 0}, {1, 0, 1, 0, 1}, {1, 0, 1, 1, 0}, {1, 0, 1, 1, 1}, {1, 1, 0, 0, 0}, {1, 1, 0, 0, 1}, {1, 1, 0, 1, 0}, {1, 1, 0, 1, 1}, {1, 1, 1, 0, 0}, {1, 1, 1, 0, 1}, {1, 1, 1, 1, 0}, {1, 1, 1, 1, 1}}

Community · Accepted Answer · 2020-06-17 09:04:33Z

Perl, 30 bytes

28 bytes of code + -nl flag.

$"=",";say for glob"{@F}"x<>

To run it:

perl -alE '$"=",";say for glob"{@F}"x<>' <<< "1 0
2"

I think that taking the input as a list of numbers is logical for Perl. However, if we allow some fantasy, and take the input with the brackets and comma (as shown in the question), we can go down to 20 bytes:

perl -nlE 'say for glob$_ x<>' <<< "{1,0}
2"

Explanations: glob initial purpose in Perl is list and iterate through filenames, but when its argument contains curly brackets, it generates combinations formed of one element of each bracket group.
-a autosplit on spaces the input, and put the result inside @F array.
$" is the list separator: it's the separator inserted between the elements of a list inside a string. We set it to ,, so "{@F"} produces {.,.} (if @F contains 0 and 1).
Then x is the string repetition operator (and <> gets one line of input).
And finally, say for iterates through the list generated by glob and prints the elements.

Jonathan Allan · Accepted Answer · 2016-12-10 20:22:01Z

3

Python, 57 bytes

from itertools import*
lambda o,n:list(product(*([o]*n)))

repl.it

Unnamed function taking a list of objects, o and a count, n and returning a list of the combinations.

answered Dec 10, 2016 at 20:22

Jonathan Allan

106k7 gold badges63 silver badges275 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

3

Pure Bash, 36

printf -vv %$2s
eval echo ${v// /$1}

Input by command-line params - The list is a comma-separated list in braces, e.g.:

./elemcombo.sh "{0,1}" 2

Note the input list needs to be quoted so the calling shell does not expand it too early.

Ideone.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Dec 10, 2016 at 23:12

Digital Trauma

72.1k9 gold badges110 silver badges262 bronze badges

\$\begingroup\$ This doesn't seem to work. \$\endgroup\$
– Ipor Sircer
Dec 12, 2016 at 2:09
\$\begingroup\$ It only repeats the input n times, doesn't print all possible combinations. \$\endgroup\$
– Ipor Sircer
Dec 12, 2016 at 3:04
\$\begingroup\$ @IporSircer I clarified the required input format. Does that work for you now? \$\endgroup\$
– Digital Trauma
Dec 12, 2016 at 17:15
\$\begingroup\$ bash a.sh "{0,1}" 2 --> {0,1}{0,1} (version 4.4.5(1)-release) \$\endgroup\$
– Ipor Sircer
Dec 13, 2016 at 18:08
1

\$\begingroup\$ @IporSircer It looks like TIO is probably putting the args into an execve() or similar call. The quotes are only needed when the script is called from another shell in order to prevent the calling shell from doing expansion of the braces. I the TIO case, the list does not need quotes. tio.run/nexus/… \$\endgroup\$
– Digital Trauma
Dec 13, 2016 at 19:37

| Show 2 more comments

ngm · Accepted Answer · 2018-05-08 19:08:48Z

3

R, 53 45 bytes

function(x,n)rev(expand.grid(rep(list(x),n)))

Try it online!

rev is there to the conform with the precise sort order requested (which doesn't really seem essential to the problem) and adds 5 bytes.

edited May 8, 2018 at 19:08

answered May 8, 2018 at 16:21

ngm

4,3046 silver badges29 bronze badges

\$\begingroup\$ Just rev for 45 bytes :) \$\endgroup\$
– JayCe
May 8, 2018 at 17:46
\$\begingroup\$ Had matrix on the mind and forgot the result was actually a list (data frame). \$\endgroup\$
– ngm
May 8, 2018 at 19:09

Add a comment |

emanresu A · Accepted Answer · 2021-05-16 08:08:33Z

2

05AB1E, 2 1 bytes

ã

-1 byte thanks to @Emigna.

Try it online.

Input as number\nlist, output as list of lists.

Explanation:

     # Implicit input `a`, `b`
ã    # Take the Cartesian product of list `b` repeated `a` times

edited May 16, 2021 at 8:08

emanresu A

37.8k5 gold badges91 silver badges217 bronze badges

answered May 8, 2018 at 9:27

Kevin Cruijssen

126k11 gold badges140 silver badges377 bronze badges

1

\$\begingroup\$ You don't need the I here. \$\endgroup\$
– Emigna
May 8, 2018 at 15:29
\$\begingroup\$ @Emigna Ah of course. I had the I because I initially was trying to figure out how to have multiple inputs and had the number and list reversed. Pretty stupid to keep the I there.. Thanks! \$\endgroup\$
– Kevin Cruijssen
May 8, 2018 at 15:40

Add a comment |

rnso · Accepted Answer · 2016-12-11 01:08:15Z

Racket 123 bytes

(let p((s "")(l(map number->string(sort l <))))
(if(= n(string-length s))(displayln s)(for((i l))(p(string-append s i)l))))

Ungolfed:

(define(f l n)
  (let loop ((s "")
             (l (map number->string (sort l <))))
    (if (= n (string-length s))
        (displayln s)
        (for ((i l))
          (loop (string-append s i) l)))))

Testing:

(f '(0 1) 2)
(f '(0 1) 3)
(f '(0 1) 5)

Output:

user59178 · Accepted Answer · 2016-12-12 11:02:21Z

1

PHP, 109 bytes

for($o=$a=array_slice($argv,2);--$argv[1];$o=$c,$c=[])foreach($a as$n)foreach($o as$s)$c[]=$n.$s;print_r($o);

Takes the length as the first argument and the list as any further arguments.
Use like:

php -r "for($o=$a=array_slice($argv,2);--$argv[1];$o=$c,$c=[])foreach($a as$n)foreach($o as$s)$c[]=$n.$s;print_r($o);" 5 0 1

Will run into an "out of memory" fatal error if asked for length 0.

answered Dec 12, 2016 at 11:02

user59178

1,0075 silver badges7 bronze badges

\$\begingroup\$ You wont have to handle length 0. \$\endgroup\$
– Luatic
Dec 12, 2016 at 14:43

Add a comment |

Stack Exchange Network

Generate all combinations of given list of elements, sorted

14 Answers 14

Jelly, 1 byte

Haskell, 20 bytes

MATL, 2 bytes

Pyth, 2 bytes

Perl 6, 15 bytes

Explanation:

JavaScript (Firefox 30+), 55 bytes

Mathematica, 6 bytes

Usage

Perl, 30 bytes

Python, 57 bytes

Pure Bash, 36

R, 53 45 bytes

05AB1E, 2 1 bytes

Racket 123 bytes

PHP, 109 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
combinatorics
or ask your own question.

Linked

Hot Network Questions

Generate all combinations of given list of elements, sorted

14 Answers 14

Jelly, 1 byte

Haskell, 20 bytes

MATL, 2 bytes

Pyth, 2 bytes

Perl 6, 15 bytes

Explanation:

JavaScript (Firefox 30+), 55 bytes

Mathematica, 6 bytes

Usage

Perl, 30 bytes

Python, 57 bytes

Pure Bash, 36

R, 53 45 bytes

05AB1E, 2 1 bytes

Racket 123 bytes

PHP, 109 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfcombinatorics or ask your own question.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
combinatorics
or ask your own question.