Generate ordered combinations with repetition

Question

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

Answer 1

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]

Answer 2

APL (Dyalog Unicode), 13 bytes^SBCS

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

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

Answer 3

J, 41 char

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

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

Answer 4

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.

Answer 5

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"]

Answer 6

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']

Answer 7

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

Answer 8

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.

Answer 9

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

Answer 10

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

Answer 11

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

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

Try it online!

-1 byte thanks to @Xcali!

Answer 12

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

Answer 13

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.

Answer 14

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

Answer 15

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.

Answer 16

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

Answer 17

Japt, 9 bytes

Explanations to follow.

õ!àUçV)mâ

Try it

õ_çV àZ â

Try it

Answer 18

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

Answer 19

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)

Answer 20

K (ngn/k), 17 bytes

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

Try it online!

Answer 21

Ruby, 73 64 bytes

->s,n{c=s.chars;(0...n).flat_map{c.product(*[c]*_1)}.map{_1*''}}

66 byte version because TIO doesn't support _1

->s,n{c=s.chars;(0...n).flat_map{|i|c.product(*[c]*i)}.map &:join}

Try it online!