| Bytes | Lang | Time | Link |
|---|---|---|---|
| 103 | Python 3 | 240904T200303Z | aeh5040 |
| 006 | Nekomata | 240904T020703Z | alephalp |
| 116 | Python 3 | 240903T201403Z | apilat |
| 080 | JavaScript V8 | 240901T191037Z | Arnauld |
| 072 | JavaScript V8 | 240902T084645Z | l4m2 |
| 018 | 05AB1E | 240902T074349Z | Kevin Cr |
| 240 | Python3 | 240902T011448Z | Ajax1234 |
| 014 | Jelly | 240901T193948Z | Unrelate |
| 052 | Charcoal | 240901T222104Z | Neil |
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)
Expects input in the form
c=[type1,value1,type2,value2,...], and concatenates types for the output.
Nekomata, 6 bytes
Ṗ@ᵐ~oũ
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"]
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
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
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)
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)
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)
From Arnauld's
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).
Try it online or verify multiple \$n\$ at once.
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)
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]
Jelly, 15 14 bytes
ŒṗịŒp€ẎṢ€Qɓ;Ṭ}
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, 31 26 23 bytes
Żp"ṚẎẎ€Ṣ€Q
Lr‘ṁƒḷṭ@ÇƤ$/
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.
Charcoal, 52 bytes
⊞υ⊞OEθκωFυ≡§I⁻↨E§ι±¹§θκ¹η⁰0…⮌ι¹-¿⊖Lι⊞⊞OυΦιλ⊞Oι⁺⊟ι§ι⁰
Attempt This Online! Link is to verbose version of code. Takes the collection as a dictionary mapping coin identifiers to values. Explanation:
⊞υ⊞OEθκωFυ
Start a breadth-first search with all coin identifiers and no coins chosen so far.
≡§I⁻↨E§ι±¹§θκ¹η⁰
Compare the value of the coins so far with the desired target.
0…⮌ι¹
If the target has been hit then output the coins.
-¿⊖Lι⊞⊞OυΦιλ⊞Oι⁺⊟ι§ι⁰
If the coins are insufficient then try both skipping the current coin and adding the current coin to the set of coins chosen.