Task — Shuffle pairs

If two integers A <= B have the same digits but in different orders, we say that they belong to the same shuffle pair if and only if there is an integer k such that B = A * k where k is called the witness of the pair.

For example, 1359 and 9513 belong to the same shuffle pair, because 1359 * 7 = 9513.

Interestingly, some integers belong to several different shuffle pairs. For example, 123876 forms one shuffle pair with 371628, and another with 867132, as 123876 * 3 = 371628, and 123876 * 7 = 867132.

Write a function that for a given $from, $to, $count returns the number of integers $i in the range $from <= $i <= $to that belong to at least $count different shuffle pairs.

PS: Inspired by a conversation between Mark Dominus and Simon Tatham at Mastodon.

Examples

Example 1
Input: $from = 1, $to = 1000, $count = 1
Output: 0
There are no shuffle pairs with elements less than 1000.

Example 2
Input: $from = 1500, $to = 2500, $count = 1
Output: 3
There are 3 integers between 1500 and 2500 that belong to 
   shuffle pairs.
1782, the other element is 7128 (witness 4)
2178, the other element is 8712 (witness 4)
2475, the other element is 7425 (witness 3)

Example 3
Input: $from = 1_000_000, $to = 1_500_000, $count = 5
Output: 2
There are 2 integers in the given range that belong to 5 
   different shuffle pairs.
1428570 pairs with 2857140, 4285710, 5714280, 7142850,
   and 8571420
1429857 pairs with 2859714, 4289571, 5719428, 7149285,
   and 8579142
The witnesses are 2, 3, 4, 5, and 6 for both the integers.

Example 4
Input: $from = 13_427_000, $to = 14_100_000, $count = 2
Output: 11
6 integers in the given range belong to 3 different 
   shuffle pairs, 5 integers belong to 2 different ones.

Example 5
Input: $from = 1030, $to = 1130, $count = 1
Output: 2
There are 2 integers between 1020 and 1120 that belong to 
   at least one shuffle pair:
1035, the other element is 3105 (witness k = 3)
1089, the other element is 9801 (witness k = 9)

Analysis

This challenge is about a relationship $A * $w == $B. We are told that $A and $B are anagrams of each other, and $w is an integer. We are given some examples involving large numbers so clearly we need to make some optimisation.

It isn't stated, but I am going to assume that $A has no leading zeroes, so for example 05 * 10 == 50 is not valid even though 05 and 50 are anagrams.

Clearly $w has a lower bound of 2 to eliminate trivial answers such as 123 * 1 == 123, and an upper bound of 9, since 10 or more would result in $B having more digits than $A.

This implies that $A must start with 1, 2, 3 or 4, because, say, 500 * 2 has more digits than $A so cannot be an anagram of $A.

So here is my algorithm.

Loop $A over $from to $to, and immediately discard any values which don't start with 1, 2, 3 or 4 (see above). Create a string $a_sorted which is the digits of $A sorted in numerical order.

Within this loop, now loop $witness from 2 to 9 (see above for reasoning), and generate $B as $A * $witness. Jump out of this witness loop if $B has more digits than $A, as that can't be a valid value.

Now generate $b_sorted as the digits of $B sorted in numerical order, and compare it with $a_sorted. If they match, $A and $B are a shuffle pair, and we can count the $A values which are part of $count or more such pairs, and format the output neatly.

On my quite slow computer, the largest of the examples completes in under 10 seconds.

Probably the biggest time-saver is the identification of anagrammatic pairs by sorting the digits of $A and $B and comparing the resulting strings. I did toy with generating all the permutations of $A, which works fine for small numbers but is infeasible for examples 3 and 4.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2025-12-01
use utf8;     # Week 350 - task 2 - Shuffle pairs
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

shuffle_pairs(1, 1000, 1);
shuffle_pairs(1500, 2500, 1);
shuffle_pairs(1_000_000, 1_500_000, 5);
shuffle_pairs(13_427_000, 14_100_000, 2);
shuffle_pairs(1030, 1130, 1);

sub shuffle_pairs {
    
    my ($from, $to, $count, $A, $B, $a_sorted, $b_sorted, 
        $b_max, $witness, %results, %occurs, %legend, 
        $output, $explain);
    
    # initialise
     ($from, $to, $count) = @_;
     
     # loop over given A values
     for $A ($from .. $to) {
        next unless $A =~ m|^[1234]|;
        $a_sorted = join('', sort(split('', $A)));
        $b_max = 10 ** length($A);
         
        # loop over possible witness and B values
        for $witness (2 .. 9) {
            $B = $A * $witness;
            last if $B >= $b_max;
            
            # check if A and B are anagrams
            $b_sorted = join('', sort(split('', $B)));
            if ($a_sorted eq $b_sorted) {
                $occurs{$A} ++;
                $results{$A} .= qq[$witness,$B; ];
            }
        }    
    }
    
    # report
    for $A (keys %results) {
        while ($results{$A} =~ m|(\d+),(\d+);|g) {
            ($witness, $B) = ($1, $2);
            $legend{$A} .= qq[ * $witness = $B;];
        }
    }
    $output = 0;
    for $A (keys %occurs) {
        next unless $occurs{$A} >= $count;
        $output ++;
        $explain .= qq[$A] . substr($legend{$A}, 0, -1) . 
            qq[\n];
    }
    
    say qq[\nInput:  \$from = $from, \$to = $to, \$count = $count];
    say qq[Output: $output];
    print $explain if $output;
}

Output

Input:  $from = 1, $to = 1000, 
		$count = 1
Output: 0

Input:  $from = 1500, $to = 2500, 
		$count = 1
Output: 3
1782 * 4 = 7128
2475 * 3 = 7425
2178 * 4 = 8712

Input:  $from = 1000000, $to = 1500000, 
		$count = 5
Output: 2
1428570 * 2 = 2857140; * 3 = 4285710; * 4 = 5714280; * 5 
   = 7142850; * 6 = 8571420
1429857 * 2 = 2859714; * 3 = 4289571; * 4 = 5719428; * 5 
   = 7149285; * 6 = 8579142

Input:  $from = 13427000, $to = 14100000, 
		$count = 2
Output: 11
14029857 * 2 = 28059714; * 3 = 42089571; * 5 = 70149285
13874526 * 3 = 41623578; * 6 = 83247156
13428567 * 2 = 26857134; * 4 = 53714268; * 5 = 67142835
14028597 * 2 = 28057194; * 3 = 42085791; * 5 = 70142985
13875246 * 3 = 41625738; * 6 = 83251476
13428657 * 2 = 26857314; * 4 = 53714628; * 5 = 67143285
13568427 * 2 = 27136854; * 5 = 67842135
14002857 * 2 = 28005714; * 3 = 42008571; * 5 = 70014285
13567842 * 2 = 27135684; * 4 = 54271368
14025897 * 2 = 28051794; * 5 = 70129485
14028570 * 2 = 28057140; * 3 = 42085710; * 5 = 70142850

Input:  $from = 1030, $to = 1130, 
		$count = 1
Output: 2
1035 * 3 = 3105
1089 * 9 = 9801