12
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
7
  • \$\begingroup\$ 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 \$\endgroup\$
    – pacman256
    Commented Sep 1 at 18:38
  • 1
    \$\begingroup\$ 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)? \$\endgroup\$
    – Unrelated String
    Commented Sep 1 at 18:39
  • 1
    \$\begingroup\$ @UnrelatedString—yep, this is fine! \$\endgroup\$
    – Peter Kagey
    Commented Sep 1 at 18:43
  • 1
    \$\begingroup\$ Can we assume that the list at index #0 is either absent or always empty? \$\endgroup\$
    – Arnauld
    Commented Sep 1 at 19:09
  • 1
    \$\begingroup\$ @Arnauld—yep, there are zero objects of weight zero (otherwise there'd be an infinite number of possibilities!) \$\endgroup\$
    – Peter Kagey
    Commented Sep 1 at 19:37

9 Answers 9

Reset to default
6
\$\begingroup\$

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, 31 26 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.

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – caird coinheringaahin g ♦
    Commented Sep 2 at 0:40
  • \$\begingroup\$ @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! \$\endgroup\$
    – Unrelated String
    Commented Sep 2 at 0:51
5
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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"]
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 236 bytes \$\endgroup\$
    – Lucenaposition
    Commented Sep 2 at 1:28
  • \$\begingroup\$ @Lucenaposition Or yield*sorted(S),? \$\endgroup\$
    – no comment
    Commented Sep 2 at 23:00
2
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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