The Weekly Challenge 260

Unique Occurrences & Dictionary Rank: Frequency Uniqueness and Lexicographical Multiset Permutations in Perl & Python

Lubos Kolouch March 10, 2024 Challenge Details GitHub Solutions

Task 1: Unique Occurrences

You are given an array of integers, @ints.

Write a script to return 1 if the number of occurrences of each value in the given array is unique or 0 otherwise.

Example 1: Input: @ints = (1, 2, 2, 1, 1, 3) → Output: 1 (1 occurs 3 times, 2 occurs 2 times, 3 occurs 1 time)

Example 2: Input: @ints = (1, 2, 3) → Output: 0

Example 3: Input: @ints = (-2, 0, 1, -2, 1, 1, 0, 1, -2, 9) → Output: 1

Method Explanation

We solve the problem in two passes:

  1. Count the occurrences (frequency) of each distinct integer in @ints using a hash table (%count in Perl or collections.Counter in Python).
  2. Verify that all frequency values are mutually distinct by checking whether the number of distinct frequencies equals the number of distinct integers.

Both steps run in $O(N)$ time and $O(N)$ auxiliary space.

Perl Solution

use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(ArrayRef Int);

signature_for unique_occurrences => (
    method     => 0,
    positional => [ ArrayRef [Int] ],
);

sub unique_occurrences ($ints) {
    my %count;
    $count{$_}++ for @$ints;

    my %occurrences_count;
    for my $freq ( values %count ) {
        return 0 if $occurrences_count{$freq}++;
    }

    return 1;
}

Python Solution

from collections import Counter


def unique_occurrences(ints: list[int]) -> int:
    """Return 1 if the number of occurrences of each value in ints is unique, else 0."""
    counts = Counter(ints).values()
    return 1 if len(counts) == len(set(counts)) else 0

Task 2: Dictionary Rank

You are given a word, $word.

Write a script to compute the dictionary rank of the given word.

Example 1: Input: $word = 'CAT' → Output: 3 (Alphabetical permutations: ACT, ATC, CAT, CTA, TAC, TCA)

Example 2: Input: $word = 'GOOGLE' → Output: 88

Example 3: Input: $word = 'SECRET' → Output: 255

Method Explanation

Instead of generating all permutations, we compute the 1-based lexicographical rank directly using multiset combinatorics:

  1. Maintain a frequency map of the remaining characters from position $i$ to $L - 1$.
  2. At index $i$ with character $w_i$, count how many remaining character instances $c < w_i$ could be placed at position $i$ instead.
  3. If we place any smaller character at position $i$, the number of distinct permutations of the remaining $L - 1 - i$ positions is given by the multinomial formula: $$\frac{\text{smaller\_chars} \times (L - 1 - i)!}{\prod_{c} (\text{count}(c)!)}$$
  4. Add this quantity to the running rank, decrement the count of $w_i$, and advance to $i + 1$.

Perl Solution

use v5.38;
use warnings;
use List::Util qw(product);
use Type::Params -sigs;
use Types::Standard qw(Int Str);

signature_for factorial => (
    method     => 0,
    positional => [Int],
);

sub factorial ($n) {
    return product( 1, 1 .. $n );
}

signature_for dictionary_rank => (
    method     => 0,
    positional => [Str],
);

sub dictionary_rank ($word) {
    my $length = length($word);
    my %char_counts;
    $char_counts{$_}++ for split //, $word;
    my $rank = 1;

    for my $i ( 0 .. $length - 1 ) {
        my $char          = substr( $word, $i, 1 );
        my $smaller_chars = 0;
        for my $candidate ( keys %char_counts ) {
            if ( $candidate lt $char ) {
                $smaller_chars += $char_counts{$candidate};
            }
        }

        my $denom = product( 1, map { factorial($_) } values %char_counts );
        $rank += $smaller_chars * factorial( $length - $i - 1 ) / $denom;

        $char_counts{$char}--;
        delete $char_counts{$char} if $char_counts{$char} == 0;
    }

    return $rank;
}

Python Solution

from collections import Counter
from math import factorial, prod


def dictionary_rank(word: str) -> int:
    """Compute the 1-based dictionary rank of the given word."""
    length = len(word)
    char_counts: dict[str, int] = dict(Counter(word))
    rank = 1

    for i, char in enumerate(word):
        smaller_chars = sum(count for c, count in char_counts.items() if c < char)
        denom = prod(factorial(c) for c in char_counts.values())
        rank += smaller_chars * factorial(length - i - 1) // denom

        char_counts[char] -= 1
        if char_counts[char] == 0:
            del char_counts[char]

    return rank