9
\$\begingroup\$

Given a string of different characters, and a number n, generate all the ordered combinations with repetition, of length 1 to n, using those characters.

Another way to define it is to see the given characters as "custom" digits in the base (radix) of the number of characters, then the program should generate all the "numbers" with 1 to n digits in that base, however, leading "zeros" are included too.

The combinations should be ordered by their length (1 character first, then 2, etc), but other than that they can be in any order. You can choose the most convenient ways of handling input and output. Shortest code wins.

Examples:

ab, 3 -> a,b,aa,ab,ba,bb,aaa,aab,aba,baa,abb,bab,bba,bbb
0123456789, 2 -> 0,1,2,3,4,5,6,7,8,9,00,01,...,09,10,11,...,99

\$\endgroup\$
  • \$\begingroup\$ Seriously? "Count"? \$\endgroup\$ – Peter Taylor Mar 21 '13 at 12:15
  • \$\begingroup\$ @PeterTaylor what do you mean? \$\endgroup\$ – aditsu Mar 21 '13 at 12:21
  • 2
    \$\begingroup\$ You recognise in thep problem that you're simply asking people to count. Do you not think that's a bit unambitious? \$\endgroup\$ – Peter Taylor Mar 21 '13 at 12:35
  • 3
    \$\begingroup\$ @PeterTaylor Well it's not straightforward counting, even when using base 10 digits. I'd like to see how to do it in the shortest code. It's not intended to be difficult. I've seen more trivial questions too and don't think that should be a problem. \$\endgroup\$ – aditsu Mar 21 '13 at 12:41
  • \$\begingroup\$ Furthermore, there are at least a couple of problems where I can apply this :) \$\endgroup\$ – aditsu Mar 21 '13 at 12:46

21 Answers 21

4
\$\begingroup\$

APL (Dyalog Unicode), 13 bytesSBCS

⊃,/,¨∘.,\⎕⍴⊂⍞

Try it online!

never miss an opportunity to use a scan :)

prompts for a string of "digits" and then for n

thanks @Adám for telling me how to enable ]box on TIO

\$\endgroup\$
5
\$\begingroup\$

Python 2, 56 bytes

n is the maximum length and s is expected to be a list of characters. It is not clear to me whether n = 0 or an empty character list are valid inputs, but this function also handles them correctly.

f=lambda s,n:n*s and s+[x+c for x in f(s,n-1)for c in s]
\$\endgroup\$
4
\$\begingroup\$

J, 41 char

   f=.}:@;@({@(,&(<',')@(]#<@[))"1 0>:@i.@])

   'ab' f 3
a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,bab,bba,bbb
\$\endgroup\$
3
\$\begingroup\$

APL (31)

{,/⍺∘{↓⍉⍺[1+(⍵⍴⍴⍺)⊤⍳⍵*⍨⍴⍺]}¨⍳⍵}

Usage: the left argument is the string and the right argument is the number, like so:

    'ab'{,/⍺∘{↓⍉⍺[1+(⍵⍴⍴⍺)⊤⍳⍵*⍨⍴⍺]}¨⍳⍵}3
b  a  ab  ba  bb  aa  aab  aba  abb  baa  bab  bba  bbb  aaa  

The output is ordered by length, but within the length groups they are shifted one to the left, this was easiest.

Explanation:

  • ,/⍺∘{...}¨⍳⍵: for 1..⍵, apply the function to ⍺ and join the results together.
  • (⍵⍴⍴⍺)⊤⍳⍵*⍨⍴⍺: for each number from 1 to (⍵=(current length))^(⍴⍺=(amount of chars)), convert to base ⍴⍺ using ⍵ digits.
  • 1+: add one because arrays are 1-indexed.
  • ⍺[...]: use these as indexes into the string
  • ↓⍉: rotate the matrix, so the 'numbers' are on the rows instead of in the columns, and then split the matrix up by rows.
\$\endgroup\$
  • 1
    \$\begingroup\$ Does APL have a single-byte encoding for its symbols? \$\endgroup\$ – aditsu Mar 22 '13 at 4:34
  • \$\begingroup\$ @aditsu: Dyalog APL uses Unicode, I'd guess all other modern APLs do the same. However, before there was Unicode you'd use a codepage so it is possible. \$\endgroup\$ – marinus Mar 22 '13 at 17:43
  • \$\begingroup\$ I'm mainly asking because I'm concerned about no. of bytes vs no. of characters. I don't know how many different symbols APL uses. \$\endgroup\$ – aditsu Mar 24 '13 at 11:13
  • \$\begingroup\$ Unless I've forgotten some or miscounted, Dyalog APL has 74 function and operator characters, which would fit into a byte together with 7-bit ASCII just fine. And there is also some overlap between those and normal characters like ?!/\-+*~&=,.| and probably some more. There exist single-byte APL encodings but Unicode is easier to use. \$\endgroup\$ – marinus Mar 25 '13 at 2:25
3
\$\begingroup\$

Haskell, 34 characters

x%n=do k<-[1..n];mapM(\_->x)[1..k]

Straightforward use of the list monad. The only real golfing is the use of mapM instead of the more idiomatic (and shorter) replicateM which would require importing Control.Monad.

Usage

> "ab" % 3
["a","b","aa","ab","ba","bb","aaa","aab","aba","abb","baa","bab","bba","bbb"]
\$\endgroup\$
2
\$\begingroup\$

Python, 97 94

from itertools import*
s,n=input()
L=t=[]
exec"t=t+[s];L+=map(''.join,product(*t));"*n
print L

t=t+[s] can't be shortened to t+=[s] because L and t would be pointing to the same list.

Input: 'ab', 3

Output:

['a', 'b', 'aa', 'ab', 'ba', 'bb', 'aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bb
a', 'bbb']
\$\endgroup\$
2
\$\begingroup\$

Mathematica 29 19 28

Join@@(i~Tuples~#&/@Range@n)

Usage

i={a, 4, 3.2};n=3;

Join@@(i~Tuples~#&/@Range@n)

{{a}, {4}, {3.2}, {a, a}, {a, 4}, {a, 3.2}, {4, a}, {4, 4}, {4, 3.2}, {3.2, a}, {3.2, 4}, {3.2, 3.2}, {a, a, a}, {a, a, 4}, {a, a, 3.2}, {a, 4, a}, {a, 4, 4}, {a, 4, 3.2}, {a, 3.2, a}, {a, 3.2, 4}, {a, 3.2, 3.2}, {4, a, a}, {4, a, 4}, {4, a, 3.2}, {4, 4, a}, {4, 4, 4}, {4, 4, 3.2}, {4, 3.2, a}, {4, 3.2, 4}, {4, 3.2, 3.2}, {3.2, a, a}, {3.2, a, 4}, {3.2, a, 3.2}, {3.2, 4, a}, {3.2, 4, 4}, {3.2, 4, 3.2}, {3.2, 3.2, a}, {3.2, 3.2, 4}, {3.2, 3.2, 3.2}}

\$\endgroup\$
  • \$\begingroup\$ Is it possible to run this without buying Mathematica? Also, could you "flatten" the output so it's not grouped by length? \$\endgroup\$ – aditsu Mar 21 '13 at 23:36
  • \$\begingroup\$ You need to purchase Mathematica. (In principle, the code can be tested on WolframAlpha.com, but for some reason the linking does not work properly.) \$\endgroup\$ – DavidC Mar 22 '13 at 13:05
  • \$\begingroup\$ Purchase Mathematica? Sorry, not gonna happen :p The code doesn't work unmodified on wolframalpha, but I could see some output from one of your earlier links, so anyway I'm tentatively accepting it as the shortest answer. \$\endgroup\$ – aditsu Mar 24 '13 at 11:20
2
\$\begingroup\$

MATL, 9 8 bytes

x:"1G@Z^

Try it on MATL Online!

(MATL was created after this challenge was posted, but I believe that's ok by meta consensus these days.)

(-1 bytes thanks to @Luis Mendo.)

x - delete string input from stack (automatically copies it to clipboard G)

:" - implicit input of number n, loop from 1 to n

1G - paste back the input string from clipboard G on the stack

@ - push the current loop iteration index

Z^ - cartesian power: cartesian product of input with itself @ number of times

The cartesian power results (@-digit "numbers" in the given base) are accumulated on the stack and implicitly displayed at the end.

\$\endgroup\$
  • 1
    \$\begingroup\$ You can save 1 byte with x:"1G@Z^ \$\endgroup\$ – Luis Mendo Jul 14 '18 at 16:55
  • \$\begingroup\$ @LuisMendo Updated (finally!). Thanks. \$\endgroup\$ – sundar - Reinstate Monica Jul 19 '18 at 11:25
1
\$\begingroup\$

Python - 106

The straightforward, uncreative solution. If you find significant improvements, please post as a separate answer.

s,n=input()
l=len(s)
for i in range(1,n+1):
 for j in range(l**i):t='';x=j;exec't+=s[x%l];x/=l;'*i;print t

Input: "ab",3
Output:

a
b
aa
ba
ab
bb
aaa
baa
aba
bba
aab
bab
abb
bbb
\$\endgroup\$
1
\$\begingroup\$

Python, 100

Derived from @aditsu's solution.

s,n=input()
L=len(s)
i=0
while i<n:i+=1;j=0;exec"x=j=j+1;t='';exec't+=s[x%L];x/=L;'*i;print t;"*L**i

Input: 'ab', 3

Output:

b
a
ba
ab
bb
aa
baa
aba
bba
aab
bab
abb
bbb
aaa
\$\endgroup\$
1
\$\begingroup\$

Perl 5 + -nlF -M5.010 -MList::Util+(uniq), 41 bytes

$,=$"=",";say grep/./,uniq glob"{,@F}"x<>

Try it online!

-1 byte thanks to @Xcali!

\$\endgroup\$
  • 1
    \$\begingroup\$ You can save a byte by using commas between output items: Try it online! \$\endgroup\$ – Xcali Jul 30 '18 at 20:09
  • \$\begingroup\$ @Xcali Ah good spot, thank you! \$\endgroup\$ – Dom Hastings Jul 31 '18 at 11:20
1
\$\begingroup\$

Pyth, 6 bytes

s^LQSE

Expects the set of characters as 1st input, number of digits as 2nd. A byte could be saved if there were a single-byte method to repeatedly access the 2nd input, but alas...

Try it online here.

s^LQSE   Implicit: Q=input 1, E=evaluate next input
    SE   Range [1,2,...,E]
 ^LQ     Perform repeated cartesian product of Q for each element of the above
s        Flatten
\$\endgroup\$
1
\$\begingroup\$

Perl 6, 33 bytes

{flat [\X~] '',|[$^a.comb xx$^b]}

Try it online!

Anonymous code block that takes a string and a number and returns a list of strings.

\$\endgroup\$
0
\$\begingroup\$

PHP 180

I have no idea... I'm feeling lazy.

<?php $f=fgetcsv(STDIN);$l=strlen($f[1]);$s=str_split($f[1]);for($i=1;$i<=$f[0];$i++)for($j=0;$j<pow($l,$i);$j++){$o="";$x=$j;for($q=0;$q<$i;$q++){$o.=$s[$x%$l];$x/=$l;}echo"$o ";}
\$\endgroup\$
0
\$\begingroup\$

Erlang 110

The Y combinator version (for shell):

fun(X, N)->F=fun(_,_,0)->[[]];(G, X, Y)->[[A|B]||A<-X,B<-G(G,X,Y-1)]end,[V||Y<-lists:seq(1,N),V<-F(F,X,Y)]end.
\$\endgroup\$
0
\$\begingroup\$

Erlang 89 (118)

Module version:

-module(g).
-export([g/2]).
h(_,0)->[[]];h(X,N)->[[A|B]||A<-X,B<-h(X,N-1)].
g(X,N)->[V||Y<-lists:seq(1,N),V<-h(X,Y)].

Chars counted without mandatory bookkeeping (module and export).

\$\endgroup\$
0
\$\begingroup\$

Ruby, 73 bytes

->s,n{(1..n).flat_map{|i|[*s.chars.repeated_permutation(i)]}.map(&:join)}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Japt, 9 bytes

Explanations to follow.

õ!àUçV)mâ

Try it

õ_çV àZ â

Try it

\$\endgroup\$
0
\$\begingroup\$

Jelly, 6 bytes

WẋŒpƤẎ

Try it online!

Function submission, taking the list of digits as the first argument and the number of digits as the second. The digits themselves can be any of Jelly's data types, but I used integers in the TIO link above because it produces the best-looking output in Jelly's automatic “function → full program” wrapper.

Explanation

WẋŒpƤẎ                      (called with arguments, e.g. [1,2,5], 3)
Wẋ       Make {argument 2} copies of {argument 1}  (e.g. [[1,2,5],[1,2,5],[1,2,5])
    Ƥ    For each prefix:                          (e.g. 1-3 copies of [1,2,5])
  Œp       take Cartesian product of its elements
     Ẏ   Flatten one level

The Cartesian product effectively gives us all numbers with a given number of digits (according to which prefix we're working with). So we end up with a list of lists of combinations (grouped by length), and can flatten that one level in order to get a list that isn't grouped (but which is still sorted by length, as the question requires, as doesn't change the relative order of the elements and Ƥ tries shorter prefixes first).

\$\endgroup\$
0
\$\begingroup\$

05AB1E, 6 bytes

「˜Ùé

Try it online or verify all test cases.

Explanation:

ã         # Cartesian product of the second input repeated the first input amount of times
          #  i.e. 3 and 'ab' → ['aaa','aab','aba','abb','baa','bab','bba','bbb']
 €Œ       # Take all the substrings for each of those results
          #  i.e. 'aba' → ['a','ab','aba','b','ba','a']
   ˜      # Flatten the list of lists
    Ù     # Remove all duplicated values
     é    # Sort the list by length

6-bytes alternative:

NOTE: Flexible output: Outputs a new list for every length, all on the same print-line.
Converting it to a single list would be 2 bytes longer: Lv²yã`}) (Try it online).

Lv²yã?

Try it online or verify all test cases.

Explanation:

Lv        # Loop `y` in the range [1, integer_input]
  ²yã     #  Take the second input and create an `y` times repeated cartesian product of it
          #   i.e. y=2 and 'ab' → ['aa','ab','ba','bb']
     ?    #  Print this list (without new-line)
\$\endgroup\$
0
\$\begingroup\$

K (ngn/k), 17 bytes

{,/(,/,'/:)\x#,y}

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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