# How many ways can you make change?

The "third type of Euler Transform" takes an integer sequence that gives the number of objects of a given weight and outputs a sequences that gives the number of multisets of objects that sum to that weight.

In this challenge, you will be performing an analogous transform on lists.

### Example

For example, let's say our ($$\1\$$-indexed) sequence is (2,1,0,0,2). We might interpret this as saying that we have

• 2 types of 1¢ coins (say copper and steel, denoted "c" and "s")
• 1 type of 2¢ coins (denoted "2")
• 0 types of 3¢ coins
• 0 types of 4¢ coins
• 2 types of 5¢ coins (say Buffalo and Jefferson, denoted "B" and "J")

Now the Euler transform tells us how many distinct ways we can make change. This (1-indexed) sequence starts

• 1¢: 2 (c/s)
• 2¢: 4 (cc/cs/ss/2)
• 3¢: 6 (ccc/ccs/css/sss/c2/s2)
• 4¢: 9 (cccc/cccs/ccss/csss/ssss/cc2/cs2/ss2/22)
• 5¢: 14 (ccccc/ccccs/cccss/ccsss/cssss/sssss/ccc2/ccs2/css2/sss2/c22/s22/B/J)
• [it continues 20, 28, 37, 48, 63, 80, 101, 124, ...]

### The challenge

You will take an input which is a collection of objects and their weights in any reasonable format. For example, you might input a list of lists of strings, for example:

input = [
[],         # index 0
["c", "s"], # index 1
["2"],      # index 2
[],         # index 3
[],         # index 4
["B","J"]   # index 5
]


You will then write a function which takes this collection of objects along with a positive integer n. Your function should return all of the multisets whose weight sums to $$\n\$$ that are composed of the objects in the input.

For example, if you use the input given above, and $$\n=3\$$, then f(input, 3) should return something like

[
["c","c","c"],
["c","c","s"],
["c","s","s"],
["s","s","s"],
["c","2"],
["s","2"]
]


Just like the input, the output can be in any reasonable format.

This is , so shortest code wins.

• is there a maximum number of types one coin can come in? otherwise representing it will be incredibly difficult. If not, can we just use a list [[0,1], 2, 1] for one 1 cent, two 2 cent and one 3 cent Commented Sep 1 at 18:38
• In the spirit of outputting a sequence, could I/O be relaxed to standard sequence I/O (i.e. also permitting first-n or infinite output)? Commented Sep 1 at 18:39
• @UnrelatedString—yep, this is fine! Commented Sep 1 at 18:43
• Can we assume that the list at index #0 is either absent or always empty? Commented Sep 1 at 19:09
• @Arnauld—yep, there are zero objects of weight zero (otherwise there'd be an infinite number of possibilities!) Commented Sep 1 at 19:37

# Jelly, 15 14 bytes

ŒṗịŒp€ẎṢ€Qɓ;Ṭ}


Try it online!

Oh yeah...

Given n on the left and the objects (with no 0 list!) on the right, outputs the nth collection of multisets.

Œṗ                Integer partitions of n.
ị               Index each integer in each partition into
ɓ       the objects
;      concatenated with
Ṭ}    n-1 0s and a 1,
Œp€            take the Cartesian product of the lists in each partition,
Ẏ           flatten the partitions out,
Ṣ€         sort each combination,
Q        and uniquify.


# Jelly, 3126 23 bytes

Żp"ṚẎẎ€Ṣ€Q
Lr‘ṁƒḷṭ@ÇƤ$/  Try it online! Given the objects on the left and n on the right, outputs a list of the first n collections of multisets. Still feels pretty messy. Lr‘ṁƒḷṭ@ÇƤ$/    Main link: compute the output
ṁƒḷ          Reshape the list of object lists to each in succession of
Lr              the range from its length to n
‘             plus 1.
Lr‘ṁƒḷ          This reuses the empty first list repeatedly to pad to n+1.
/    Reduce the padded list by
Ç       calling the helper on
Ƥ      every prefix of
ṭ@  $the accumulator with the current element appended. Żp"ṚẎẎ€Ṣ€Q Helper link: paired combinations adding up to length of prefix Ż Prepend 0 (rangifies to an empty list) to the prefix, p" and take Cartesian products with corresponding elements of Ṛ the prefix reversed. Ẏ Concatenate the products of each pair, Ẏ€ concatenate the pairs in each product, Ṣ€ sort each combination, Q and uniquify.  As an amusing aside... I meant to use ¥ in place of $, but there's no difference here, because apparently / coercing its operand to a dyad even affects how said operand chains.

• Yeah, IIRC, / never actually checks the arity of the link it's passed. The source code just forces it to be dyadic: return functools.reduce(lambda x, y: dyadic_link(link, (x, y)), array, *init). And, because this passes it to dyadic_link, it chains as a dyadic link, even if not parsed that way Commented Sep 2 at 0:40
• @cairdcoinheringaahing That's the unsurprising part--what caught me off guard is that adicity isn't intrinsic to grouping (or line-reference!) quicks for the purposes of their own internal chaining. I believe it's actually line 906 that's the culprit from my point of view. Intuitively, I would have expected $/ to be equivalent to ${/ rather than ¥--guess I need to revise that tip! Commented Sep 2 at 0:51

# Charcoal, 52 bytes

⊞υ⊞ＯＥθκωＦυ≡§Ｉ⁻↨Ｅ§ι±¹§θκ¹η⁰0…⮌ι¹-¿⊖Ｌι⊞⊞ＯυΦιλ⊞Ｏι⁺⊟ι§ι⁰


Attempt This Online! Link is to verbose version of code. Takes the collection as a dictionary mapping coin identifiers to values. Explanation:

⊞υ⊞ＯＥθκωＦυ


Start a breadth-first search with all coin identifiers and no coins chosen so far.

≡§Ｉ⁻↨Ｅ§ι±¹§θκ¹η⁰


Compare the value of the coins so far with the desired target.

0…⮌ι¹


If the target has been hit then output the coins.

-¿⊖Ｌι⊞⊞ＯυΦιλ⊞Ｏι⁺⊟ι§ι⁰


If the coins are insufficient then try both skipping the current coin and adding the current coin to the set of coins chosen.

# JavaScript (V8), 80 bytes

Expects (list_of_lists)(n) without any list for weight 0. Outputs by printing comma-separated strings.

a=>g=(n,...o)=>n?a.map(b=>n-->0&&b.map(c=>g(n,...o,c))):o+""==o.sort()&&print(o)


Try it online!

### Commented

a =>                // outer function taking the input list a[]
g = (               // g = inner recursive function taking:
n,                //   n   = target sum
...o              //   o[] = output
) =>                //
n ?                 // if n is not zero:
a.map(b =>        //   for each sub-list b[] in a[]:
n-- > 0         //     abort if n is 0 or less
&&              //     (decrement n afterwards)
b.map(c =>      //     otherwise, for each character c in b[]:
g(n, ...o, c) //       do a recursive call with c added to o[]
)               //     end of map()
)                 //   end of map()
:                   // else:
o + "" ==         //   uniquify by testing if o[] is ...
o.sort() &&       //   ... lexicographically sorted
print(o)          //   if it is, print it (e.g. "c,c,s" is printed
//   but "c,s,c" and "s,c,c" are not)


# 05AB1E, 18 bytes

FĆ}¹Åœèε.«âεS{]€Ù


Inputs in the order $$\n,objectLists\$$, including an empty list at index 0.
Assumes the objects are always single characters (otherwise the S should be ¸˜ for +1 byte).

Explanation:

F }      # Loop the first (implicit) input amount of times:
Ć       #  Enclose the second (implicit) input-list;
#  appending its own head (the [] at index 0)
¹     # Push the first input-integer n again
Åœ   # Get all lists of positive integers that sum to this n
è  # (0-based) index each into the list of lists
ε        # Map over each list of lists:
.«      #  Reduce each list of lists by:
â     #   Cartesian product
ε    #  Map over each reduced list of lists:
S   #   Convert it to a flattened list of characters
{  #   Sort this list of characters
]        # Close the nested maps
€      # Flatten it one level down
# (which has as side-effect that each inner list is reversed)
Ù     # Uniquify this list of lists
# (after which the result is output implicitly)


# Nekomata, 6 bytes

Ṗ@ᵐ~oũ


Attempt This Online!

A port of @Unrelated String's Jelly answer, but much shorter thanks to Nekomata's non-determinism.

Ṗ@ᵐ~oũ
Take 2, [[],["a","b"],["c"]] as an example
Ṗ       Find an integer partition of the first input
Possible results: [1,1] [2]
@      Index into the second input
Possible results: [["a","b"],["a","b"]] [["c"]]
ᵐ     Map:
~      Choose any element
Possible results: ["a","a"] ["a","b"] ["b","a"] ["b","b"] ["c"]
o   Sort
Possible results: ["a","a"] ["a","b"] ["a","b"] ["b","b"] ["c"]
ũ  Uniquify among all possible solutions
Possible results: ["a","a"] ["a","b"] ["b","b"] ["c"]


# Python3, 240 bytes

from itertools import*
R=range
def f(c,n):
q=[([(i+1,c[i])for i in R(len(c))if c[i]],0,[])]
for c,t,S in q:
if t==n:yield tuple(sorted(S))
if c:(i,C),*c=c;q+=[(c,V,[*S,*K])for j in R((n-t)//i+1)for K in product(*[C]*j)if(V:=t+j*i)<=n]


Try it online!

• 236 bytes Commented Sep 2 at 1:28
• @Lucenaposition Or yield*sorted(S),? Commented Sep 2 at 23:00

# JavaScript (V8), 72 bytes

a=>g=(n,...o)=>n?a.map(b=>n-->0&&b.map(c=>c<o[0]||g(n,c,...o))):print(o)


Try it online!

From Arnauld's

# Python 3, 116 bytes

The input doesn't contain the empty index 0 array.

def f(c, n):
a=set([()]*-~-n)
for O in c[:n]:n-=1;a|=set(tuple(sorted([*x,o]))for o in O for x in f(c,n))
return a


Try it online!

If we are allowed to return a garbage character in each of the multisets (i.e. {'$2', '$cs', '$ss', '$cc'} instead of {'2', 'cs', 'ss', 'cc'}, the code below is 114 bytes.

def g(c, n):
a=set('\$'*-~-n)
for O in c[:n]:n-=1;a|=set(''.join(sorted(x+o))for o in O for x in g(c,n))
return a


Try it online!

# Python 3, 103 bytes

def f(c,n):
if n==0:yield''
if c and n>0:
for x in f(c,n-c[1]):yield c[0]+x
yield from f(c[2:],n)


Try it online!

Expects input in the form c=[type1,value1,type2,value2,...], and concatenates types for the output.