Combinations in Raku

Monday morning, and there are new tasks in the new weekly challenge 067. Both of them require similar Raku tools, namely, the cross operator X.

Issue 1

Print all possible sorted combinations of $n numbers from the list 1 2 3 … $m.

Note that it is not clear from the task that the valid combinations cannot contain the same numbers, so 1, 1 or 3, 3 are not valid. You can see it in the proposed output example.

First, let’s build the corresponding list and repeat it a few times:

[X] (1..$m) xx $n

The elements must be sorted, so (3, 4) and (4, 3) should both be converted to (3, 4). Apply the sort method to all items:

([X] (1..$m) xx $n)\
    >>.sort

(Note the so-called unspace \ so that we can continue on the new line, as we need it because the solution will be a long change of method calls.)

To exclude the repeated elements, call unique:

([X] (1..$m) xx $n)\
    >>.sort
    .unique(:as(*.Str))

The :as parameter tells what to do with the item before it can be compared using ===. This converts both copies of the sequence (3, 4) to the same string 34.

As a home exercise, try using the squish method instead of unique and make the program work.

OK, now it’s time to exclude the elements with repeated numbers. This is my interpretation of the initial task, so you may have understood it differently.

([X] (1..$m) xx $n)\
    >>.sort
    .unique(:as(*.Str))
    .grep(*.unique.elems == $n)

Here, I am filtering out everything where the number of unique elements differres from the required combination length $n. (By the way, $n must not be greater than $m.)

Finally, order the sequence; we can use the same technique that was already used:

([X] (1..$m) xx $n)\
    >>.sort
    .unique(:as(*.Str))
    .grep(*.unique.elems == $n)
    .sort(*.Str)

The main work is done. The last bits are to prepare the output in the requested format, and here is the whole program:

my $m = 5;
my $n = 2;

say '[ ',
    ([X] (1..$m) xx $n)\
        >>.sort
        .unique(:as(*.Str))
        .grep(*.unique.elems == $n)
        .sort(*.Str)
        .map({"[{.join(',')}]"})
        .join(', '),
    ' ]';

For the given configuration, the program prints the following:

[ [1,2], [1,3], [1,4], [1,5], [2,3], [2,4], [2,5], [3,4], [3,5], [4,5] ]

Try different initial numbers, for example, 5 and 3:

[ [1,2,3], [1,2,4], [1,2,5], [1,3,4], [1,3,5], [1,4,5], [2,3,4], [2,3,5], [2,4,5], [3,4,5] ]

Or, which is also interesting to test, 5 and 5:

[ [1,2,3,4,5] ]

Issue 2

Task: Print all possible letter combinations that the given digit string could produce on a phone keypad.

(As a side note, I was surprised to see the image from an article on ResearchGate, meaning the author preferred a scientific website. But maybe it was just the picture with some letters on the 1 key 🙂 )

This task is simpler than the previous one, just devote a few lines of code to prepare the initial data:

my @keypad = 
    ' ',
    < _ , @>,
    < a b c >,
    < d e f >,
    < g h i >,
    < j k l >,
    < m n o >,
    < p q r s >,
    < t u v >,
    < w x y z >;

Notice that some of the elements have three, and some — four characters. For 0, I assumed the character to be a space. By the way, notice that in the @keypad array, the first item is a string, while the rest are lists.

Having this, the rest is trivial:

my $n = 35;

say [X~] @keypad[$n.comb];

When $n is 35, the program prints the following combinations:

(dj dk dl ej ek el fj fk fl)

Let me ignore the format of the original answer this time.

Everything shown today can be also found on GitHub in my raku-challenges repository.

→ Navigation to the Raku challenges post series